[LeetCode周赛复盘] 第 318 场周赛20221107

一、本周周赛总结

• 感觉挺难的，被暴打。
• T2 定长带限制滑窗。
• T3 最小堆。
• T4 二维DP。
  

二、 [Easy] 2460. 对数组执行操作

链接: 2460. 对数组执行操作

1. 题目描述

2. 思路分析

按题意模拟即可。

• 比赛时读了半天题，最后发现是模拟，做完四分钟过去了。
• 这仿佛预示着这次要被暴打。

3. 代码实现

class Solution:
    def applyOperations(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(n-1):
            if nums[i] == nums[i+1]:
                nums[i]*=2
                nums[i+1] = 0
        ans = [0]*n
        t = 0
        for x in nums:
            if x:
                ans[t] = x
                t += 1
        return ans            
1
2
3
4
5
6
7
8
9
10
11
12
13
14

三、[Medium] 2461. 长度为 K 子数组中的最大和

链接: 2461. 长度为 K 子数组中的最大和

1. 题目描述

2. 思路分析

• 由于是连续且定长的子数组，自然想到滑窗。
• 这里求得是和，需要定义一个前缀和，或者直接s跟着滑动计算即可。
• 限制是元素出现次数，那么定义一个cnt即可。
• lc上的滑窗我习惯用队列，这样就不用费心去判断窗口左右的下标以及长度。

---

• 具体做法是：
• 窗口向右扩张，计数出现的元素，如果元素个数超过1，窗左侧缩减直到元素个数变回1。这个操作能保证窗口内所有元素个数都小于1。
• 扩张时，判断 窗口大小，大了也要缩减。
• 扩张/缩减时，注意s同步增减。
• 当窗口大小正好是k，更新答案。

3. 代码实现

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        ans = 0
        cnt = Counter()
        q = deque()
        s = 0
        for r,v in enumerate(nums):
            q.append(r)
            s += v
            cnt[v] += 1
            while cnt[v]>1 or len(q)>k:
                l = q.popleft()
                cnt[nums[l]]-=1
                s -= nums[l]
            if len(q) == k:
                ans = max(ans,s)
        return ans                                                      
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

四、[Medium] 2462. 雇佣 K 位工人的总代价

链接: 2462. 雇佣 K 位工人的总代价

1. 题目描述

2. 思路分析

• 本题实际的操作是每次找到一个最小值，然后干掉它，然后增加一个值进来。
• 显然是用堆。
• 比赛时用了1个堆，然后设置了vis数组防止重复入堆，左右指针记录是从头还是尾进的堆，以便入堆时选择左右。
• 其实2个堆的话更好写，因为比较堆顶后天然的知道左右。

3. 代码实现

class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        n = len(costs)
        if n == k:
            return sum(costs)
        from sortedcontainers import SortedSet
        vis = set()
        h = []
        l = candidates
        r = n - candidates -1
        for i in range(candidates):
            j = n - 1 - i
            if i not in vis:
                heapq.heappush(h,(costs[i],i))
                vis.add(i)
            if j not in vis:
                heapq.heappush(h,(costs[j],j))
                vis.add(j)
            # h.append((costs[i],i))
            # h.append((costs[j],j))
            
        # heapq.heapify(h)
        ans = 0
        
        for _ in range(k):
            v,i = heapq.heappop(h)
            ans += v
            if i < l and l < n:
                if l not in vis:
                    heapq.heappush(h,(costs[l],l))
                    # h.add((cost[l],l))
                    vis.add(l)
                    l+=1
            elif i > r and r>=0:
                if r not in vis:
                    # h.add((cost[r],r))
                    heapq.heappush(h,(costs[r],r))
                    vis.add(r)
                    r -= 1
        return ans                    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

五、[Hard] 2463. 最小移动总距离

链接: 2463. 最小移动总距离

1. 题目描述

2. 思路分析

• 比赛时没做出来，主要是状态设计不会。
• 其实这题做法很多：dp、网络流最大流、二分图最大匹配。
• dp的话可以记忆化搜索或者递推都可以。
• 如果递推的话，可以仿照01背包空间压缩，第二层逆序推。

---

• 首先有个结论，最优的方案中，每个工厂管辖的机器人一定是连续的。
• 那么状态设计就可以是:
  • f(i,j) 代表前i个工厂管辖前j个机器的最小花费。
• 在这个设计下，转移：
  • 只需考虑第i个工厂管了最后的几个机器人，前边的所有机器人显然是前i-1个工厂管的,即：
  • f(i,j) = min{f(i-1,j-k)+cost(i,j-k+1~j)| k<=limit} ，cost是第i个工厂管辖机器的消耗 。
• 初始(边界) 没有机器人就是0；只剩一个工厂，他要修全部。

3. 代码实现

class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        robot.sort()
        factory.sort()
        # @cache
        # def f(i,j):  # 前i个工厂修理前j个机器人的最小花费,ij均从1开始计数
        #     if j == 0:  # 没有机器人了
        #         return 0
        #     pos,limit = factory[i-1]
        #     if i == 1:
        #         if limit < j:
        #             return inf 
        #         else:
        #             return sum(abs(x-pos) for x in robot[:j])
        #     ans = f(i-1,j)
        #     s = 0
        #     for k in range(1,min(limit+1, j+1)):                
        #         s += abs(pos-robot[j-k])
        #         ans = min(ans, s+f(i-1,j-k))
        #     return ans 
        # return f(len(factory),len(robot))
        
        # 空间压缩dp
        n = len(robot)
        f = [inf] * (n+1)
        f[0] = 0
        pre = 0
        for pos, limit in factory:
            pre += limit
            for j in range(min(n,pre),0,-1):
                s = 0
                for k in range(1,min(limit+1,j+1)):
                    s += abs(pos-robot[j-k])
                    f[j] = min(f[j],s+f[j-k])
        return f[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

六、1478. 安排邮筒(类T4)

链接: 1478. 安排邮筒

1. 题目描述

2. 思路分析

• 这题和T4有点像，因此补了一下。
• 不同的是邮筒没有limit，并且可以任意放位置(即也没有position)。
• 我们令f(i,j)为前i个邮筒管辖前j个房子的最小花费。
• 类似的考虑最后一个邮筒管辖最后k个房子，剩下的j-k个房子是由i-1管，即f(i-1,j-k)。
• 那最后k个房子的花费是多少呢，显然邮筒要放在中位数的房子上，花费是最小的。
• 这里取中位数暴力也能做，因为n是100，记忆化的话，也可以暴力或者递归记忆化，差的不多。
• 枚举k时可以优化一些：正常是k in range(1,j+1)其实不需要到j+1，因为前i-1个房子可以各1个邮筒，代价已经是0了，因此最后一个邮筒只最多管j-i+1个房子即可，再继续多没意义。

3. 代码实现

class Solution:
    def minDistance(self, houses: List[int], k: int) -> int:
        n = len(houses)
        houses.sort()
        # @cache
        # def get_median_cost(l,r):  # 获取在[l,r]这些房子里放一个邮箱的最小代价，显然邮箱应该放在中位数(中间那个房子)上。
        #     m = l+(r-l+1)//2
        #     return sum(abs(houses[x] - houses[m]) for x in range(l,r+1))
        @cache
        def get_median_cost(l,r):  # 获取在[l,r]这些房子里放一个邮箱的最小代价，显然邮箱应该放在中位数(中间那个房子)上。
            if l == r:
                return 0
            if l + 2 >= r:
                return houses[r] - houses[l]
            return houses[r] - houses[l] + get_median_cost(l+1,r-1)
        @cache 
        def f(i,j):  # 前i个邮筒管前j个房子的代价(给前j个房子安排i个邮筒的代价)
            if j == 0 or i >= j:
                return 0
            if i == 1:
                # m = j // 2
                # return sum(abs(houses[x] - houses[m]) for x in range(j))
                return get_median_cost(0,j-1)
            
            ans = f(i-1,j)  # 枚举第i个邮筒管几个房子;本行指管0个
            for k in range(1, j-i+2):  # 这上限可以优化到j-i+1+1，因为前i-1个房子分配i-1个邮筒即可，代价是0，本邮筒继续向前没有意义。
                # m = j-k+k//2
                # ans = min(ans,f(i-1,j-k)+sum(abs(houses[x]-houses[m]) for x in range(j-k,j)))
                ans = min(ans,f(i-1,j-k)+get_median_cost(j-k,j-1))
            return ans 
        
        return f(k,len(houses))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32