Biweekly Contest 161

欢迎大家加QQ群：623375442。这周题目难度不大比较套路

Q1. 按质数下标拆分数组

题目描述

给定一个整数数组 nums。

按照以下规则将 nums 拆分成两个数组 A 和 B：

• 数组 nums 中下标为质数的位置的元素必须放入数组 A。
• 其他位置的元素放入数组 B。

返回两个数组元素和的绝对差：(|sum(A) - sum(B)|)。

说明：空数组的元素和为 0。

示例：

输入：nums = \[2,3,4]
输出：1
解释：
只有下标 2 是质数，因此 nums\[2] = 4 放入数组 A。
其余元素 2 和 3 放入数组 B。
sum(A) = 4，sum(B) = 2 + 3 = 5，|4 - 5| = 1。

解题思路

1. 预先使用 "埃氏筛"（Sieve of Eratosthenes）算法，在 0 到 10^5 范围内计算出所有数是否为质数，存储在 isPrime 布尔数组中。
2. 遍历输入数组 nums，索引 i 如果 isPrime[i] 为 true，则将 nums[i] 累加到 a；否则累加到 b。
3. 最后返回 |a - b|。

class Solution {
    // 使用埃氏筛预处理质数，下标范围最多到 10^5
    private static boolean[] isPrime = new boolean[(int)(1e5) + 1];
    static {
        // 初始化标记数组，默认都认为是质数
        Arrays.fill(isPrime, true);
        // 0 和 1 不是质数
        isPrime[0] = false;
        isPrime[1] = false;
        // 开始筛选
        for (int i = 2; i * i < isPrime.length; ++i) {
            if (isPrime[i]) {
                // 从 i*i 开始，将所有 i 的倍数标记为非质数
                for (int j = i * i; j < isPrime.length; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }

    public long splitArray(int[] nums) {
        long a = 0, b = 0;
        // 遍历所有元素，根据下标质数性决定归属
        for (int i = 0; i < nums.length; ++i) {
            if (isPrime[i]) {
                // 质数下标，加到 A 的和
                a += nums[i];
            } else {
                // 非质数下标，加到 B 的和
                b += nums[i];
            }
        }
        // 返回绝对差
        return Math.abs(a - b);
    }
}

Q2. 统计总价值能被 K 整除的岛屿数量

题目描述

给定一个大小为 m x n 的矩阵 grid 和一个正整数 k。
其中 grid 中的正整数表示陆地，0 表示水域。

一个岛屿定义为所有 4 方向相邻的陆地（非 0）组成的连通区域。
岛屿的总价值等于该连通区域内所有格子值的和。

请返回 grid 中总价值能够被 k 整除的岛屿数目。

示例：

输入：grid = [[0,2,1,0,0],
               [0,5,0,0,5],
               [0,0,1,0,0],
               [0,1,4,7,0],
               [0,2,0,0,8]], k = 5
输出：2

解题思路

1. 使用二维布尔数组 isVisit 记录每个位置是否已经访问过。
2. 遍历每个格子，如果格子值非 0 且未访问，则以该格子为起点，使用 DFS 递归遍历整座岛屿，同时累加其格子值。
3. DFS 返回该岛屿的总价值，判断该价值 % k == 0，若是则计数加一。
4. 最终返回计数。

class Solution {
    // 方向数组，依次表示向下、向右、向上、向左
    private static final int[] moves = {1, 0, -1, 0, 1};

    public int countIslands(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        // 访问标记
        boolean[][] isVisit = new boolean[m][n];
        int res = 0;
        // 遍历所有格子
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // 未访问且为陆地
                if (grid[i][j] != 0 && !isVisit[i][j]) {
                    // DFS 计算岛屿总价值，并判断能否被 k 整除
                    res += dfs(grid, isVisit, i, j) % k == 0 ? 1 : 0;
                }
            }
        }
        return res;
    }

    private int dfs(int[][] grid, boolean[][] isVisit, int x, int y) {
        int m = grid.length;
        int n = grid[0].length;
        // 越界或已访问或是水域，返回 0
        if (x < 0 || x >= m || y < 0 || y >= n) return 0;
        if (!isVisit[x][y] && grid[x][y] != 0) {
            // 标记已访问
            isVisit[x][y] = true;
            int res = grid[x][y];
            // 四个方向递归
            for (int i = 0; i < 4; ++i) {
                res += dfs(grid, isVisit, x + moves[i], y + moves[i + 1]);
            }
            return res;
        }
        return 0;
    }
}

Q3. 网络恢复路径

题目描述

给定一个有向无环图（DAG），包含 n 个节点（编号 0 到 n-1）。
使用一个长度为 m 的二维数组 edges 表示图的边，其中 edges[i] = [u_i, v_i, cost_i] 表示从 u_i 到 v_i 的有向边，恢复该边需要花费 cost_i。

部分节点可能处于离线状态，用布尔数组 online 表示，online[i] = true 表示节点 i 在线。节点 0 和 n-1 永远在线。

一条从 0 到 n-1 的路径是有效的需要满足：

1. 路径上所有中间节点（不包括起点和终点）都在线。
2. 路径上所有边的恢复成本总和不超过 k。

对于每一条有效路径，其分数定义为该路径上边权的最小值。
返回所有有效路径中分数的最大值，如果不存在有效路径，则返回 -1。

示例：

输入：edges = [[0,1,5],[1,3,10],[0,2,3],[2,3,4]],
      online = [true,true,true,true], k = 10
输出：3

解题思路

1. 排序 & 离散化边权：先按边权升序对 edges 排序，并使用 TreeMap 记录边权对应的首个位置，以支持二分。
2. 二分查找答案：令 length 为所有不同边权的升序列表，二分枚举答案在 length 中的位置 mid，判断以最小边权 length[mid] 为阈值可否存在有效路径。

3. 有效性判断：对于给定阈值，构造只保留边权 >= 当前阈值的子图，并对该子图做 Dijkstra 最短路（路径长度为恢复成本总和）从 0 到 n-1，同时跳过离线节点。

   • 如果最短路长度 <= k，则说明存在有效路径，移动二分右边界；否则缩小右边界。
4. 最后根据二分结果找到最大可行的最小边权。

class Solution {
    public int findMaxPathScore(int[][] edges, boolean[] online, long k) {
        // 按边权升序排序
        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
        // TreeMap 用于记录每个边权首次出现的索引
        TreeMap<Integer, Integer> sort = new TreeMap<>();
        for (int i = 0; i < edges.length; ++i) {
            int cost = edges[i][2];
            if (!sort.containsKey(cost)) {
                sort.put(cost, i);
            }
        }
        // 不同边权列表，用于二分
        List<Integer> length = new ArrayList<>(sort.keySet());
        int st = 0, ed = length.size();
        // 二分查找最大的可行 mid
        while (st < ed) {
            int mid = (st + ed) / 2;
            // 从 sort.get(length.get(mid)) 开始构建子图并判断
            if (isValid(edges, online, sort.get(length.get(mid)), k)) {
                st = mid + 1;
            } else {
                ed = mid;
            }
        }
        // 调整二分结果
        --st;
        return st >= 0 ? length.get(st) : -1;
    }

    private boolean isValid(int[][] edges, boolean[] online, int stPos, long k) {
        int n = online.length;
        // 构建邻接表，只保留从 stPos 到末尾的边（边权 >= 当前阈值）
        List<int[]>[] graph = new List[n];
        for (int i = 0; i < n; ++i) {
            graph[i] = new ArrayList<>();
        }
        for (int i = stPos; i < edges.length; ++i) {
            int u = edges[i][0], v = edges[i][1], cost = edges[i][2];
            graph[u].add(new int[]{v, cost});
        }
        // Dijkstra 最短路模板，minPos[i] 表示从 0 到 i 的最小总成本
        long[] minPos = new long[n];
        Arrays.fill(minPos, Long.MAX_VALUE);
        minPos[0] = 0;
        // 优先队列按当前最小成本排序
        TreeSet<Integer> queue = new TreeSet<>((a, b) -> (minPos[a] == minPos[b] ? Integer.compare(a, b) : Long.compare(minPos[a], minPos[b])));
        queue.add(0);
        while (!queue.isEmpty()) {
            int u = queue.pollFirst();
            long currCost = minPos[u];
            // 遍历可到达的邻居
            for (int[] next : graph[u]) {
                int v = next[0], c = next[1];
                // 跳过离线节点，并检查成本是否越界或优化
                if (online[v] && currCost + c <= k && currCost + c < minPos[v]) {
                    queue.remove(v);
                    minPos[v] = currCost + c;
                    queue.add(v);
                }
            }
        }
        // 判断终点最小成本是否 <= k
        return minPos[n - 1] <= k;
    }
}

Q4. 二进制 1 的个数-深度等于 K 的整数数量 I

题目描述

给定两个整数 n 和 k。

对于任何正整数 x，定义序列：

p0 = x
pi+1 = popcount(pi)

其中 popcount(y) 表示 y 的二进制表示中 1 的个数。该序列最终会达到 1。

定义正整数 x 的 "popcount-深度" 为达到 1 所需的最小步数 d，即 p_d = 1。

例如，x = 7（二进制 "111"），序列为：7 → 3 → 2 → 1，深度为 3。

请统计区间 [1, n] 中具有 "popcount-深度" 恰好等于 k 的整数个数，并返回该数量。

示例：

输入：n = 4, k = 1
输出：2
解释：
区间 [1,4] 中深度为 1 的数为 2 ("10" → 1) 和 4 ("100" → 1)，共 2 个。

解题思路

1. 预处理深度：由于 popcount(x) 的结果最多是 log2(x) 范围内的值（<=63），预先计算 1 到 63 的每个数转换到 1 所需的深度 depth[i]。
2. 组合数表：构造 C[n][k] 的组合数表 combine[i][j]，用于后续按位 DP 计算。
3. 按位 DP 统计：将 n 转为二进制字符串 max，依次枚举目标中间值 i（即第一次 popcount 的结果）满足 depth[i] == k，调用 cal(max, i) 计算二进制长度约束条件下不超过 n 的满足 popcount(x) = i 的数目。
4. cal 函数先统计与 n 前缀相同的情况，再累加短于 n 位长的情况。

class Solution {
    // 预先计算 0-63 范围内各个数的 popcount-深度
    private static final int[] depth = {0, 1, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 3,
                                        2, 3, 3, 4, 3, 4, 4, 3, 3, 4, 4, 3, 4, 3, 3, 4,
                                        2, 3, 3, 4, 3, 4, 4, 3, 3, 4, 4, 3, 4, 3, 3, 4,
                                        3, 4, 4, 3, 4, 3, 3, 4, 4, 3, 3, 4, 3, 4, 4, 4};

    // 组合数表，combine[n][k] = C(n, k)
    private static final long[][] combine = new long[64][64];
    static {
        combine[0][0] = 1;
        for (int i = 1; i <= 63; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    combine[i][j] = 1;
                } else {
                    combine[i][j] = combine[i - 1][j] + combine[i - 1][j - 1];
                }
            }
        }
    }

    public long popcountDepth(long n, int k) {
        // 特殊情况：k=0 时，只有 x=1 可以直接满足
        if (k == 0) return 1;
        // mem[i] 用于记录 popcount-depth 中间结果（可选，此处未使用）
        int[] mem = new int[64];
        mem[1] = 1;
        for (int i = 2; i <= 63; ++i) {
            mem[i] = mem[Long.bitCount(i)] + 1;
        }
        long res = 0;
        // 将 n 转为二进制字符串
        String max = Long.toBinaryString(n);
        // 枚举第一次 popcount 结果 i，深度为 k 的
        for (int i = 1; i <= 63; ++i) {
            if (depth[i] == k) {
                res += cal(max, i);
            }
        }
        return res;
    }

    // 计算不超过二进制上界 max 的，且 popcount = digit 的正整数个数
    private long cal(String max, int digit) {
        long res = currentValid(max, digit);
        // 统计位数短于 max.length() 的全组合数
        for (int i = 2; i < max.length(); ++i) {
            if (i - 1 >= digit - 1) {
                res += combine[i - 1][digit - 1];
            }
        }
        // 处理与 max 前缀相同的情况
        int remainDigit = digit - 1;
        for (int i = 1; i < max.length(); ++i) {
            if (max.charAt(i) == '1') {
                int remain = max.length() - i - 1;
                if (remain >= remainDigit) {
                    res += combine[remain][remainDigit];
                }
                remainDigit--;
                if (remainDigit < 0) break;
            }
        }
        return res;
    }

    // 判断二进制字符串 max 本身是否符合 popcount = digit
    private int currentValid(String max, int digit) {
        if ("1".equals(max) && digit != 0) return 0;
        for (char c : max.toCharArray()) {
            digit -= (c - '0');
        }
        return digit == 0 ? 1 : 0;
    }
}