22.11.6 LC周赛 字典、堆+DFS

22.11.6 LC周赛 字典、堆+DFS+计数器删除元素 - ct.pop(nums[i-k])

   这次周赛仍然只做出1道题，而且第二题绊住好久，字典哈希表的删除操作不熟悉，这周竟忙着做实验了，没怎么做题，题感很差，只做了做每日一题，还是不太够的！不多说了，保持激昂的精神继续努力啊！这次学到不少知识，分享记录一下，如果朋友看得喜欢麻烦点赞收藏哦！本周就仅分享一下 学习到的代码内容吧！
  部分代码参考了其他选手的代码，提前说一声，这并不都是我自己码出来的。~~

6229. 对数组执行操作

题目链接：6229. 对数组执行操作
题目大意：给你一个下标从 0 开始的数组 nums ，数组大小为 n ，且由 非负 整数组成。

你需要对数组执行 n - 1 步操作，其中第 i 步操作（从 0 开始计数）要求对 nums 中第 i 个元素执行下述指令：

如果 nums[i] == nums[i + 1] ，则 nums[i] 的值变成原来的 2 倍，nums[i + 1] 的值变成 0 。否则，跳过这步操作。
在执行完 全部 操作后，将所有 0 移动 到数组的 末尾 。

例如，数组 [1,0,2,0,0,1] 将所有 0 移动到末尾后变为 [1,2,1,0,0,0] 。
返回结果数组。

注意 操作应当 依次有序 执行，而不是一次性全部执行。

例如：

输入：nums = [1,2,2,1,1,0]
输出：[1,4,2,0,0,0]
解释：执行以下操作：
- i = 0: nums[0] 和 nums[1] 不相等，跳过这步操作。
- i = 1: nums[1] 和 nums[2] 相等，nums[1] 的值变成原来的 2 倍，nums[2] 的值变成 0 。数组变成 [1,4,0,1,1,0] 。
- i = 2: nums[2] 和 nums[3] 不相等，所以跳过这步操作。
- i = 3: nums[3] 和 nums[4] 相等，nums[3] 的值变成原来的 2 倍，nums[4] 的值变成 0 。数组变成 [1,4,0,2,0,0] 。
- i = 4: nums[4] 和 nums[5] 相等，nums[4] 的值变成原来的 2 倍，nums[5] 的值变成 0 。数组变成 [1,4,0,2,0,0] 。
执行完所有操作后，将 0 全部移动到数组末尾，得到结果数组 [1,4,2,0,0,0] 。
示例 2：

输入：nums = [0,1]
输出：[1,0]
解释：无法执行任何操作，只需要将 0 移动到末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 解题思路：简单题不说了
• 时间复杂度： $O(N)$ $N$为$\text{nums}$的长度
• 空间复杂度： $O(1)$

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] += nums[i]
                nums[i+1] = 0
        ans = [0]*n
        i = 0
        for num in nums:
            if num != 0:
                ans[i] = num
                i += 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14

 

6230. 长度为 K 子数组中的最大和

题目链接：6230. 长度为 K 子数组中的最大和
题目大意：
给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：

• 子数组的长度是 k，且
• 子数组中的所有元素 各不相同 。
• 返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。

子数组 是数组中一段连续非空的元素序列。

例如：

输入：nums = [1,5,4,2,9,9,9], k = 3
输出：15
解释：nums 中长度为 3 的子数组是：
- [1,5,4] 满足全部条件，和为 10 。
- [5,4,2] 满足全部条件，和为 11 。
- [4,2,9] 满足全部条件，和为 15 。
- [2,9,9] 不满足全部条件，因为元素 9 出现重复。
- [9,9,9] 不满足全部条件，因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。

输入：nums = [4,4,4], k = 3
输出：0
解释：nums 中长度为 3 的子数组是：
- [4,4,4] 不满足全部条件，因为元素 4 出现重复。
因为不存在满足全部条件的子数组，所以返回 0 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 解题思路：Counter 可以 pop(), hash_map 可以 del。
• 时间复杂度：构造函数复杂度为 $O(N)$ ，$N$为$\text{nums}$的长度
• 空间复杂度：构造函数复杂度为 $O(K)$

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        ans,n = 0,len(nums)
        ct = collections.Counter(nums[:k])
        st = sum(nums[:k])
        if len(ct) == k:
            ans = st
        for i in range(k,n):
            # updata the two continer
            st += nums[i]-nums[i-k]
            ct[nums[i]] += 1
            ct[nums[i-k]] -= 1
            if ct[nums[i-k]] == 0:
                # This is so important step
                # dict can use 'pop()' 
                ct.pop(nums[i-k])
            if len(ct) == k:
                ans = max(ans,st)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

 

6231. 雇佣 K 位工人的总代价

题目链接：6231. 雇佣 K 位工人的总代价
题目大意：给你一个下标从 0 开始的整数数组 costs ，其中 costs[i] 是雇佣第 i 位工人的代价。
同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人：

• 总共进行 k 轮雇佣，且每一轮恰好雇佣一位工人。在每一轮雇佣中，从最前面 candidates 和最后面 candidates 人中选出代价最小的一位工人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
• 比方说，costs = [3,2,7,7,1,2] 且 candidates = 2 ，第一轮雇佣中，我们选择第 4 位工人，因为他的代价最小 [3,2,7,7,1,2] 。
• 第二轮雇佣，我们选择第 1 位工人，因为他们的代价与第 4 位工人一样都是最小代价，而且下标更小，[3,2,7,7,2] 。注意每一轮雇佣后，剩余工人的下标可能会发生变化。如果剩余员工数目不足 candidates 人，那么下一轮雇佣他们中代价最小的一人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。一位工人只能被选择一次。

返回雇佣恰好 k 位工人的总代价。

输入：costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
输出：11
解释：我们总共雇佣 3 位工人。总代价一开始为 0 。
- 第一轮雇佣，我们从 [17,12,10,2,7,2,11,20,8] 中选择。最小代价是 2 ，有两位工人，我们选择下标更小的一位工人，即第 3 位工人。总代价是 0 + 2 = 2 。
- 第二轮雇佣，我们从 [17,12,10,7,2,11,20,8] 中选择。最小代价是 2 ，下标为 4 ，总代价是 2 + 2 = 4 。
- 第三轮雇佣，我们从 [17,12,10,7,11,20,8] 中选择，最小代价是 7 ，下标为 3 ，总代价是 4 + 7 = 11 。注意下标为 3 的工人同时在最前面和最后面 4 位工人中。
总雇佣代价是 11 。

输入：costs = [1,2,4,1], k = 3, candidates = 3
输出：4
解释：我们总共雇佣 3 位工人。总代价一开始为 0 。
- 第一轮雇佣，我们从 [1,2,4,1] 中选择。最小代价为 1 ，有两位工人，我们选择下标更小的一位工人，即第 0 位工人，总代价是 0 + 1 = 1 。注意，下标为 1 和 2 的工人同时在最前面和最后面 3 位工人中。
- 第二轮雇佣，我们从 [2,4,1] 中选择。最小代价为 1 ，下标为 2 ，总代价是 1 + 1 = 2 。
- 第三轮雇佣，少于 3 位工人，我们从剩余工人 [2,4] 中选择。最小代价是 2 ，下标为 0 。总代价为 2 + 2 = 4 。
总雇佣代价是 4 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 解题思路：堆 处理这种堆数组索引要求不严格的情况 最好了。
• 时间复杂度：$O(N\log N)$，其中 $N$ 为 $\text{costs}$ 的长度。
• 空间复杂度：$O(N)$

class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        hs,he = 0,len(costs)-1
        heap = list()
        for i in range(candidates):
            if he<hs: break
            heapq.heappush(heap,[costs[hs],hs])
            hs += 1
            if he<hs: break
            heapq.heappush(heap,[costs[he],he])
            he -= 1
        
        ans = 0
        for _ in range(k):
            v,pv = heapq.heappop(heap)
            ans += v
            if he<hs: 
                continue
            elif pv<hs:
                heapq.heappush(heap,[costs[hs],hs])
                hs += 1
            else:
                # assert pv>he
                heapq.heappush(heap,[costs[he],he])
                he -= 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

 

6232. 最小移动总距离

题目链接：6232. 最小移动总距离
题目大意：X 轴上有一些机器人和工厂。给你一个整数数组 robot ，其中 robot[i] 是第 i 个机器人的位置。再给你一个二维整数数组 factory ，其中 factory[j] = [position_j, limit_j] ，表示第 j 个工厂的位置在 position_j ，且第 j 个工厂最多可以修理 limit_j 个机器人。
每个机器人所在的位置 互不相同 。每个工厂所在的位置也 互不相同 。注意一个机器人可能一开始跟一个工厂在 相同的位置 。
所有机器人一开始都是坏的，他们会沿着设定的方向一直移动。设定的方向要么是 X 轴的正方向，要么是 X 轴的负方向。当一个机器人经过一个没达到上限的工厂时，这个工厂会维修这个机器人，且机器人停止移动。
任何时刻，你都可以设置 部分 机器人的移动方向。你的目标是最小化所有机器人总的移动距离。
请你返回所有机器人移动的最小总距离。测试数据保证所有机器人都可以被维修。

注意：

• 所有机器人移动速度相同。
• 如果两个机器人移动方向相同，它们永远不会碰撞。
• 如果两个机器人迎面相遇，它们也不会碰撞，它们彼此之间会擦肩而过。
• 如果一个机器人经过了一个已经达到上限的工厂，机器人会当作工厂不存在，继续移动。
• 机器人从位置 x 到位置 y 的移动距离为 |y - x| 。

输入：robot = [0,4,6], factory = [[2,2],[6,2]]
输出：4
解释：如上图所示：
- 第一个机器人从位置 0 沿着正方向移动，在第一个工厂处维修。
- 第二个机器人从位置 4 沿着负方向移动，在第一个工厂处维修。
- 第三个机器人在位置 6 被第二个工厂维修，它不需要移动。
第一个工厂的维修上限是 2 ，它维修了 2 个机器人。
第二个工厂的维修上限是 2 ，它维修了 1 个机器人。
总移动距离是 |2 - 0| + |2 - 4| + |6 - 6| = 4 。没有办法得到比 4 更少的总移动距离。
1
2
3
4
5
6
7
8
9

• 解题思路：DFS 需要缓存加速一下。
• 时间复杂度：$O(n{m}^2)$，其中 $n$ 为 $\text{factory}$的长度，$m$为 $\text{robot}$的长度。
• 空间复杂度：$O(nm)$

class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        robot = sorted(robot)
        factory = sorted(factory)

        @functools.lru_cache(None)
        def solve(pr=0,pf=0,tf=0):
            if pr == len(robot):
                return 0
            if pf == len(factory):
                return 1e99
            if tf == factory[pf][1]:
                return solve(pr,pf+1,0)
            ans = abs(robot[pr]-factory[pf][0])+solve(pr+1,pf,tf+1)
            ans = min(ans,solve(pr,pf+1,0))
            return ans
        return solve()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

总结

   努力 奋斗！通过1道，又要掉分了，不过这次还是学到好多有用的东西，继续吧！