本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
3541. 找到频率最高的元音和辅音 - 力扣（LeetCode）
解题思路
哈希表，遍历字符串即可
示例代码
python
class Solution:
def maxFreqSum(self, s: str) -> int:
t = 'aeiou'
cnt = Counter(s)
mx1 = mx2 = 0
for k, v in cnt.items():
if k in t:
mx1 = max(mx1, v)
else:
mx2 = max(mx2, v)
return mx1 + mx23542. 将所有元素变为 0 的最少操作次数 - 力扣（LeetCode）
解题思路
赛时用树状数组做的，正解用栈就可以实现
火箭毛毛虫，直接起飞
按大小遍历元素，两两遍历下标，若存在差值，说明之间操作过，之后的操作次数要分开计算
还是正解吧，只有必须操作时才更新答案
x == st[-1] 不入栈，相当于替换，等到有更小数时再操作，只用操作一次
示例代码
python
class Solution:
def minOperations(self, nums: List[int]) -> int:
n = len(nums)
f = FenwickTree(n + 1)
d = defaultdict(list)
for i, x in enumerate(nums, 1):
d[x].append(i)
ans = 0
for x in sorted(d.keys()):
if x == 0:
for i in d[x]:
f.update(i, 1)
continue
ans += 1
for i, j in pairwise(d[x]):
if f.query(j) != f.query(i):
ans += 1
f.update(i, 1)
f.update(d[x][-1], 1)
return anspy
class Fenwick:
__slots__ = ["n", "c"]
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)
def update(self, x: int, delta: int):
while x <= self.n:
self.c[x] += delta
x += x & -x
def query(self, x: int) -> int:
s = 0
while x > 0:
s += self.c[x]
x -= x & -x
return spython
class Solution:
def minOperations(self, nums: List[int]) -> int:
st = []
ans = 0
for x in nums:
while st and x < st[-1]:
st.pop()
ans += 1
if not st or x != st[-1]:
st.append(x)
return ans + len(st) - (st[0] == 0)3543. K 条边路径的最大边权和 - 力扣（LeetCode）
解题思路
记忆化搜索，赛时是从入度为 0 的节点开始的，其实是搞错了，从任一点开始都行，最多遍历 k 个节点，还可以剪枝的，自己搞复杂了
拓扑排序 DP，用刷表法转移
注：在动态规划中，用转移来源更新当前状态叫查表法，用当前状态更新其他状态叫刷表法。
示例代码
python
class Solution:
def maxWeight(self, n: int, edges: List[List[int]], k: int, t: int) -> int:
fmax = lambda x, y: x if x > y else y
g = defaultdict(list)
for x, y, w in edges:
g[x].append((y, w))
@cache
def dfs(x, cnt, s):
if cnt == k:
nonlocal ans
ans = fmax(ans, s)
res = -1
for y, w in g[x]:
if s + w < t:
dfs(y, cnt + 1, s + w)
ans = -1
for x in range(n):
dfs(x, 0, 0)
dfs.cache_clear()
return anspython
class Solution:
def maxWeight(self, n: int, edges: List[List[int]], k: int, t: int) -> int:
d = [0] * n
g = defaultdict(list)
for x, y, w in edges:
g[x].append((y, w))
d[y] += 1
ans = -1
f = [[set() for _ in range(k + 1)] for _ in range(n)]
q = deque(i for i, x in enumerate(d) if x == 0)
while q:
x = q.popleft()
f[x][0].add(0)
if f[x][k]:
ans = max(ans, max(f[x][k]))
for y, w in g[x]:
for i in range(k):
for s in f[x][i]:
if s + w < t:
f[y][i + 1].add(s + w)
d[y] -= 1
if d[y] == 0:
q.append(y)
return ans3544. 子树反转和 - 力扣（LeetCode）
解题思路
记忆化搜索，反转或不反转，要手写记忆化搜索，memo 数组
优化，树形 DP，有点难度，以后再攻破吧
示例代码
python
class Solution:
def subtreeInversionSum(self, edges: List[List[int]], nums: List[int], k: int) -> int:
g = defaultdict(list)
for x, y in edges:
g[x].append(y)
g[y].append(x)
memo = {}
def dfs(x: int, fa: int, d: int, r: bool) -> int:
t = (x, d, r)
if t in memo:
return memo[t]
res = nums[x] if r else -nums[x]
for y in g[x]:
if y == fa: continue
res += dfs(y, x, d - 1 if d else 0, r)
if d == 0:
s = nums[x] if not r else -nums[x]
for y in g[x]:
if y == fa: continue
s += dfs(y, x, k - 1, not r)
if s > res:
res = s
memo[t] = res
return res
ans = dfs(0, -1, 0, True)
return ans