LeetCode 第 425 场周赛 个人题解
Q1. 最小正和子数组
原题链接
思路分析
签到题，暴力就行
时间复杂度：O(N^2)
AC代码
class Solution:
def minimumSumSubarray(self, nums: List[int], l: int, r: int) -> int:
n = len(nums)
res = -1
acc = list(accumulate(nums, initial=0))
for i in range(n):
for j in range(i + l - 1, min(n, i + r)):
if acc[j + 1] - acc[i] > 0:
if res == -1:
res = acc[j + 1] - acc[i]
else:
res = min(res, acc[j + 1] - acc[i])
return resQ2. 重排子字符串以形成目标字符串
原题链接
思路分析
存一下s中每个块的数目和t的每个块比对下数量够不够
时间复杂度：O(N)
AC代码
class Solution:
def isPossibleToRearrange(self, s: str, t: str, k: int) -> bool:
cnt = Counter()
n, m = len(s), len(t)
if n % k: return False
B = n // k
for i in range(0, n, B):
cnt[s[i:i+B]] += 1
for i in range(0, m, B):
if cnt[t[i:i+B]] == 0:
return False
cnt[t[i:i+B]] -= 1
return TrueQ3. 最小数组和
原题链接
思路分析
很典的dp
f(i, j, k) 为 [i, n - 1] 剩余 j 次 操作1，k次操作2的最小数组和
枚举当前的方案进行转移即可
时间复杂度：O(N OP1 OP 2)
AC代码
class Solution:
def minArraySum(self, nums: List[int], v: int, op1: int, op2: int) -> int:
n = len(nums)
@cache
def dfs(i: int, j: int, k: int):
if i == n: return 0
res = nums[i] + dfs(i + 1, j, k)
if j:
res = min(res, (nums[i] + 1) // 2 + dfs(i + 1, j - 1, k))
if k and nums[i] >= v:
res = min(res, nums[i] - v + dfs(i + 1, j, k - 1))
if j and k and nums[i] >= v:
t = (nums[i] - v + 1) // 2
if (nums[i] + 1) // 2 >= v:
t = min(t, (nums[i] + 1) // 2 - v)
res = min(res, t + dfs(i + 1, j - 1, k - 1))
return res
res = dfs(0, op1, op2)
dfs.cache_clear()
return resQ4. 移除边之后的权重最大和
原题链接
思路分析
树形dp + 贪心
每个边选或不选，容易想到树上背包
但是这个数据量，显然会炸掉，尝试优化
定义 f(u, lim) 为 u 所在子树最大合法化值，lim = true 说明<p, u> 的边被父节点拿掉了，否则没拿掉
所以 u 能够保存的边数目为 min(k - lim, adj[u] - 1)
我们假设 u 往下伸的所有边 都不拿，然后贪心的考虑拿谁
一条边 <u, v> 从不拿到拿的变化花费：f(v, true) + w - f(v, false)
即，按照f(v, true) + w - f(v, false) 从大到小拿即可
时间复杂度：O(nlogm)
AC代码
class Solution:
def maximizeSumOfWeights(self, edges: List[List[int]], k: int) -> int:
n = len(edges) + 1
adj = [[] for _ in range(n)]
for (u, v, w) in edges:
adj[u].append([v, w])
adj[v].append([u, w])
@cache
def dfs(u: int, p: int, lim: bool) -> int:
t = k - lim
h = []
res = 0
for (v, w) in adj[u]:
if v == p: continue
a = dfs(v, u, False)
b = w + dfs(v, u, True)
h.append(b - a)
res += a
h.sort(reverse=True)
for i in range(min(t, len(h))):
if h[i] <= 0: break
res += h[i]
return res
return dfs(0, -1, False)原文地址：https://blog.csdn.net/EQUINOX1/article/details/144005749
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！