LeetCode Weekly Contest 455

703
Contest
LeetCode
本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。

3591. 检查元素频次是否为质数 - 力扣（LeetCode） ​

解题思路 ​

暴力，判断一下是否每个值的个数是否为质数即可

示例代码 ​

python
class Solution:
    def checkPrimeFrequency(self, nums: List[int]) -> bool:
        @cache
        def is_prime(x):
            if x == 1:
                return False
            for y in range(2, int(sqrt(x)) + 1):
                if x % y == 0:
                    return False
            return True
        for v in Counter(nums).values():
            if is_prime(v):
                return True
        return False

3592. 硬币面值还原 - 力扣（LeetCode） ​

解题思路 ​

完全背包，好久没做，不记得这个知识点了

参考：完全背包（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def findCoins(self, numWays: List[int]) -> List[int]:
        mx = max(numWays)
        n = len(numWays)
        f = [1] + [0] * n
        ans = []
        for i, w in enumerate(numWays, 1):
            if w == f[i]:
                continue
            if w - 1 != f[i]:
                return []
            ans.append(i)
            for j in range(i, n + 1):
                f[j] += f[j - i]
        return ans

3593. 使叶子路径成本相等的最小增量 - 力扣（LeetCode） ​

解题思路 ​

递归，我的想法是通过查找代价的最大值，再次递归代价等于最大值的叶节点不计算，次大值只计算一次

另外一种是灵神的做法，一次递归，自底向上传递最大代价

参考：统计最大路径和的出现次数，两种写法（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def minIncrease(self, n: int, edges: List[List[int]], cost: List[int]) -> int:
        g = defaultdict(list)
        degree = [0] * n
        for x, y in edges:
            degree[x] += 1
            g[x].append(y)
            g[y].append(x)
        
        def dfs(x, fa):
            if degree[x] == 0:
                return cost[x]
            res = 0
            for y in g[x]:
                if y == fa:
                    continue
                cost[y] += cost[x]
                res = max(res, dfs(y, x))
            return res

        def dfs2(x, fa):
            if degree[x] == 0:
                return mx - cost[x], int(mx != cost[x])
            mn = inf
            cnt = res = 0
            for y in g[x]:
                if y == fa:
                    continue
                delta, s = dfs2(y, x)
                if delta < mn:
                    mn = delta
                    cnt = 1
                elif delta == mn:
                    cnt += 1
                res += s
            return mn, res - (cnt - 1 if mn else 0)
        mx = dfs(0, -1)
        _, ans = dfs2(0, -1)
        return ans
python
class Solution:
    def minIncrease(self, n: int, edges: List[List[int]], cost: List[int]) -> int:
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
        g[0].append(-1)

        def dfs(x, fa):
            max_cost = cnt = 0
            for y in g[x]:
                if y == fa:
                    continue
                mx = dfs(y, x)
                if mx > max_cost:
                    max_cost = mx
                    cnt = 1
                elif mx == max_cost:
                    cnt += 1

            nonlocal ans
            ans += len(g[x]) - 1 - cnt
            return max_cost + cost[x]

        ans = 0
        dfs(0, -1)
        return ans

3594. 所有人渡河所需的最短时间 - 力扣（LeetCode） ​

解题思路 ​

参考：这道题很神秘，以后再来解决吧！

示例代码 ​

python
TODO
Test Module
LeetCode Weekly Contest 453