[LeetCode周赛复盘] 第 318 场周赛20221107
-
- 一、本周周赛总结
- 二、 [Easy] 2460. 对数组执行操作
-
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 三、[Medium] 2461. 长度为 K 子数组中的最大和
-
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 四、[Medium] 2462. 雇佣 K 位工人的总代价
-
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 五、[Hard] 2463. 最小移动总距离
-
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 六、1478. 安排邮筒(类T4)
-
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
一、本周周赛总结
- 感觉挺难的，被暴打。
- T2 定长带限制滑窗。
- T3 最小堆。
- T4 二维DP。
[LeetCode周赛复盘] 第 318 场周赛20221107
二、 [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
三、[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
四、[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
五、[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]
六、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))