力扣第 455 场周赛

2025年7月1日大约 3 分钟

力扣第 455 场周赛

比赛时间 2025-06-22。本场周赛国服共 64 人 AK。

六月的天空。

T1. 检查元素频次是否为质数（3 分）

解题思路

模拟 + 判断素数。

时间复杂度：O(n sqrt(n))。

参考代码

class Solution {
    public boolean checkPrimeFrequency(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int v : nums) cnt.merge(v, 1, Integer::sum);

        for (Integer c : cnt.values()) {
            if (isPrime(c)) return true;
        }
        return false;
    }

    private boolean isPrime(long num) {
        if (num < 2) {
            return false;
        }
        for (long i = 2; i * i <= num; ++i) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

T2. 硬币面值还原（5 分）

解题思路

完全背包逆运算。

时间复杂度：O(n^2)。

参考代码

class Solution {
    public List<Integer> findCoins(int[] numWays) {
        int n = numWays.length;
        long[] A = new long[n + 1];
        A[0] = 1;
        List<Integer> ans = new ArrayList<>();

        for (int i = 1; i <= n; i++) {
            long target = numWays[i - 1];
            if (A[i] > target) {
                return new ArrayList<>();
            }
            if (A[i] < target) {
                if (target - A[i] != 1) {
                    return new ArrayList<>();
                }
                ans.add(i);
                for (int j = i; j <= n; j++) {
                    A[j] += A[j - i];
                }
            }
        }
        return ans;
    }
}

T3. 使叶子路径成本相等的最小增量（5 分）

解题思路

自底向上贪心。

注意：为避免误把根节点（只有一个邻居的情况）认为是叶子，可以把 0 与 −1 相连，这样可以保证根至少有两个邻居。

时间复杂度：O(n)。

参考代码

class Solution {
    private int ans;
    private List<Integer>[] g;
    private long[] longCost;

    public int minIncrease(int n, int[][] edges, int[] cost) {
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int[] e : edges) {
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }
        g[0].add(-1); // 关键
        longCost = new long[cost.length];
        for (int i = 0; i < cost.length; i++) longCost[i] = cost[i];

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

    private void dfs(int x, int fa) {
        long maxS = 0;
        int maxS_cnt = 0;
        for (Integer y : g[x]) {
            if (y == fa) continue;
            dfs(y, x);
            if (longCost[y] > maxS) {
                maxS = longCost[y];
                maxS_cnt = 1;
            } else if (longCost[y] == maxS) {
                maxS_cnt++;
            }
        }
        ans += g[x].size() - maxS_cnt - 1;
        longCost[x] += maxS;
    }
}

T4. 所有人渡河所需的最短时间（6 分）

解题思路

状态压缩动态规划。

dp[mask][stage][boat] 存储达到该状态所需的最少时间，其中：

mask：二进制数，表示当前还在营地的人员（1 表示在营地，0 表示已到目的地）。
stage：当前环境阶段（0 到 m-1）。
boat：船的位置（0 在目的地，1 在营地）。

时间复杂度：O(2^n * m * 2)。

参考代码

class Solution3594 {
    public double minTime(int n, int k, int m, int[] time, double[] mul) {
        double[] maxTimeSub = new double[1 << n];
        for (int g = 0; g < (1 << n); g++) {
            double maxT = 0;
            for (int i = 0; i < n; i++) {
                if (((g >> i) & 1) == 1) {
                    if (time[i] > maxT) {
                        maxT = time[i];
                    }
                }
            }
            maxTimeSub[g] = maxT;
        }

        List<Integer>[] subsets = new ArrayList[1 << n];
        for (int mask = 0; mask < (1 << n); mask++) {
            subsets[mask] = new ArrayList<>();
            for (int g = mask; g > 0; g = (g - 1) & mask) {
                int cnt = Integer.bitCount(g);
                if (cnt >= 1 && cnt <= k) {
                    subsets[mask].add(g);
                }
            }
        }

        double[][][] dp = new double[1 << n][m][2];
        for (int i = 0; i < (1 << n); i++) {
            for (int j = 0; j < m; j++) {
                Arrays.fill(dp[i][j], Double.POSITIVE_INFINITY);
            }
        }

        Queue<int[]> q = new ArrayDeque<>();
        dp[(1 << n) - 1][0][1] = 0.0;
        q.add(new int[]{(1 << n) - 1, 0, 1});

        while (!q.isEmpty()) {
            int[] state = q.poll();
            int mask = state[0];
            int stage = state[1];
            int boat = state[2];
            double t = dp[mask][stage][boat];

            if (boat == 1) {
                for (int g : subsets[mask]) {
                    double maxT = maxTimeSub[g];
                    double d = maxT * mul[stage];
                    int time_floor = (int) Math.floor(d);
                    int new_stage = (stage + time_floor) % m;
                    int new_mask = mask ^ g;
                    int new_boat = 0;
                    double new_time = t + d;

                    if (new_time < dp[new_mask][new_stage][new_boat]) {
                        dp[new_mask][new_stage][new_boat] = new_time;
                        q.add(new int[]{new_mask, new_stage, new_boat});
                    }
                }
            } else {
                if (mask != 0) {
                    for (int i = 0; i < n; i++) {
                        if ((mask & (1 << i)) == 0) {
                            double d = time[i] * mul[stage];
                            int time_floor = (int) Math.floor(d);
                            int new_stage = (stage + time_floor) % m;
                            int new_mask = mask | (1 << i);
                            int new_boat = 1;
                            double new_time = t + d;

                            if (new_time < dp[new_mask][new_stage][new_boat]) {
                                dp[new_mask][new_stage][new_boat] = new_time;
                                q.add(new int[]{new_mask, new_stage, new_boat});
                            }
                        }
                    }
                }
            }
        }

        double minTotalTime = Double.POSITIVE_INFINITY;
        for (int stage = 0; stage < m; stage++) {
            if (dp[0][stage][0] < minTotalTime) {
                minTotalTime = dp[0][stage][0];
            }
        }

        return minTotalTime == Double.POSITIVE_INFINITY ? -1.0 : minTotalTime;
    }
}

（全文完）