LeetCode Contest 447

欢迎大家加QQ群：623375442。最后一题这个倍增法好久没写了，写麻了。

100623. Count Covered Buildings

给你一个正整数 n，表示一个 n x n 的城市，同时给定一个二维数组 buildings，其中 buildings[i] = [x, y] 表示位于坐标 [x, y] 的一个 唯一 建筑。

如果一个建筑在四个方向（左、右、上、下）中每个方向上都至少存在一个建筑，则称该建筑 被覆盖 。

返回 被覆盖 的建筑数量。

测试样例：

输入：n = 3, buildings = [[1,2],[2,2],[3,2],[2,1],[2,3]]

输出：1

解释：只有建筑 [2,2] 被覆盖，因为它在每个方向上都至少存在一个建筑：

• 上方 ([1,2])
• 下方 ([3,2])
• 左方 ([2,1])
• 右方 ([2,3])

因此，被覆盖的建筑数量是 1。

解答：

1. 对于每一行 x，记录该行上所有建筑的最小列号 xMin[x] 和最大列号 xMax[x]；
2. 对于每一列 y，记录该列上所有建筑的最小行号 yMin[y] 和最大行号 yMax[y]；
3. 遍历每个建筑 [x,y]，如果 xMin[x] < y < xMax[x]（即左右各有至少一个建筑）且 yMin[y] < x < yMax[y]（即上下各有至少一个建筑），则该建筑被“覆盖”，计数加一。

class Solution {
    public int countCoveredBuildings(int n, int[][] buildings) {
        // xMax[x]：行 x 上建筑的最大 y 值（最右侧）
        // xMin[x]：行 x 上建筑的最小 y 值（最左侧）
        int[] xMax = new int[n + 1], yMax = new int[n + 1];
        int[] xMin = new int[n + 1], yMin = new int[n + 1];
        // 初始化最小值为极大，方便后续取最小
        Arrays.fill(xMin, Integer.MAX_VALUE);
        Arrays.fill(yMin, Integer.MAX_VALUE);

        // 第一次遍历，统计每行和每列的最小/最大坐标
        for (int[] b : buildings) {
            int x = b[0], y = b[1];
            // 更新行 x 的左右边界
            xMax[x] = Math.max(xMax[x], y);
            xMin[x] = Math.min(xMin[x], y);
            // 更新列 y 的上下边界
            yMax[y] = Math.max(yMax[y], x);
            yMin[y] = Math.min(yMin[y], x);
        }

        int res = 0;
        // 第二次遍历，判断每个建筑是否在四个方向上都被“覆盖”
        for (int[] b : buildings) {
            int x = b[0], y = b[1];
            // xMin[x] < y < xMax[x] 表示左右方向各至少有一个
            // yMin[y] < x < yMax[y] 表示上下方向各至少有一个
            if (xMin[x] < y && y < xMax[x] && yMin[y] < x && x < yMax[y]) {
                ++res;
            }
        }
        return res;
    }
}

100640. Path Existence Queries in a Graph I

给你一个整数 n，表示图中的节点数量，这些节点按从 0 到 n - 1 编号。

同时给你一个长度为 n 的整数数组 nums，该数组按 非递减 顺序排序，以及一个整数 maxDiff。

如果满足 |nums[i] - nums[j]| <= maxDiff（即 nums[i] 和 nums[j] 的 绝对差 至多为 maxDiff），则节点 i 和节点 j 之间存在一条 无向边 。

此外，给你一个二维整数数组 queries。对于每个 queries[i] = [ui, vi]，需要判断节点 ui 和 vi 之间是否存在路径。

返回一个布尔数组 answer，其中 answer[i] 等于 true 表示在第 i 个查询中节点 ui 和 vi 之间存在路径，否则为 false。

测试样例：

输入：n = 2, nums = [1,3], maxDiff = 1, queries = [[0,0],[0,1]]

输出：[true,false]

解释: 查询 [0,0]：节点 0 有一条到自己的显然路径。查询 [0,1]：节点 0 和节点 1 之间没有边，因为 |nums[0] - nums[1]| = |1 - 3| = 2，大于 maxDiff。因此，在处理完所有查询后，最终答案为 [true, false]。

解答：

1. 将节点按 nums[i] 的值从小到大排序，得到排序后的下标数组 sort[]，并记录每个原下标在排序数组中的位置 map[i]；
2. 构造一个一维“连通分量编号”数组 cc[]，从左到右遍历排序后的 nums，只要相邻两数差值 > maxDiff，就意味着新的连通分量，否则保持在原分量；
3. 对于每个查询 [u,v]，只需比较 map[u] 和 map[v] 是否在同一个分量（即 cc[map[u]] == cc[map[v]]），若相同则可达，否则不可达；自环查询单独处理。

class Solution {
    public boolean[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
        // sort：存储按 nums 值排序后的原始下标
        Integer[] sort = new Integer[n];
        for (int i = 0; i < n; i++) sort[i] = i;
        // 按 nums 的值对下标进行排序
        Arrays.sort(sort, (a, b) -> Integer.compare(nums[a], nums[b]));

        // map[i]：节点 i 在排序后数组中的位置
        int[] map = new int[n];
        // sortedVals：排序后对应位置的数值
        int[] sortedVals = new int[n];
        for (int i = 0; i < n; i++) {
            sortedVals[i] = nums[sort[i]];
            map[sort[i]] = i;
        }

        // cc[i]：排序后位置 i 所在的连通分量编号
        int[] cc = new int[n];
        cc[0] = 0;  // 第 0 个位置从分量 0 开始
        for (int i = 1; i < n; i++) {
            // 如果相邻两数差值大于 maxDiff，则分量编号 +1
            cc[i] = cc[i - 1] + (sortedVals[i] - sortedVals[i - 1] > maxDiff ? 1 : 0);
        }

        int q = queries.length;
        boolean[] res = new boolean[q];
        // 处理每个查询
        for (int i = 0; i < q; i++) {
            int u = queries[i][0], v = queries[i][1];
            int pu = map[u], pv = map[v];
            // 如果同一节点，显然可达
            if (u == v) {
                res[i] = true;
            } else {
                // 只有同一连通分量才可达
                res[i] = (cc[pu] == cc[pv]);
            }
        }
        return res;
    }
}

100643. Concatenated Divisibility

给你一个正整数数组 nums 和一个正整数 k。

当 nums 的一个排列中的所有数字，按照排列顺序 连接其十进制表示 后形成的数可以 被 k 整除时，我们称该排列形成了一个 可整除连接 。

返回能够形成 可整除连接 且 字典序最小 的排列（按整数列表的形式表示）。如果不存在这样的排列，返回一个空列表。

排列 是数组所有元素的一种重排。

如果在数组 a 和数组 b 第一个位置不同的地方，a 的元素小于对应位置上 b 的元素，那么数组 a 的 字典序小于 数组 b 。

如果前 min(a.length, b.length) 个元素均相同，则较短的数组字典序更小。

测试样例：

输入：nums = [3,12,45], k = 5

输出：[3,12,45]

解释: 可以形成可整除连接且字典序最小的排列是 [3,12,45]。

解答：

1. 预处理每个 nums[i] 的十进制长度 strLen[i]，以及预先计算好 10^k % k 的乘数数组 multiply[]；
2. 使用记忆化 DFS（状态为 key（位掩码）和当前余数 remain），在所有未使用的数字上尝试拼接，更新余数 (remain * 10^len[i] + nums[i]) % k；
3. DFS 返回一个 Node，其中保存字典序最小的后续排列；在合并多个可行结果时，通过 replace 函数取字典序更小的那一个；
4. 最终状态 key == (1<<n)-1 且 remain == 0 时表示成功，返回拼接结果；否则返回空列表。

class Solution {
    // DFS 返回的包装节点，list 为当前状态下的最小字典序排列
    static class Node {
        List<Integer> list;
        public Node(List<Integer> list) {
            this.list = list;
        }
        // 将 List<Integer> 转为 int[]
        public int[] trans() {
            int[] res = new int[list.size()];
            for (int i = 0; i < res.length; ++i) {
                res[i] = list.get(i);
            }
            return res;
        }
    }

    private static final int[] failed = new int[0];           // 失败返回空数组
    private static final int[] multiply = {1, 10, 100, 1000, 10000, 100000, 1000000};
    private static final Node successDFS = new Node(new ArrayList<>());
    private static final Node failedDFS = new Node(null);

    public int[] concatenatedDivisibility(int[] nums, int k) {
        int n = nums.length;
        // strLen[i]：nums[i] 的十进制长度
        int[] strLen = new int[n];
        for (int i = 0; i < n; ++i) {
            strLen[i] = String.valueOf(nums[i]).length();
        }
        // dp[key][remain]：记忆化存储对应状态下的 Node
        Node[][] dp = new Node[1 << n][k];
        // 从空掩码、余数 0 开始 DFS
        Node result = dfs(nums, strLen, dp, 0, 0, k);
        // 若失败则返回空数组，否则返回排列
        return result == failedDFS ? failed : result.trans();
    }

    private Node dfs(int[] nums, int[] strLen, Node[][] dp, int key, int remain, int k) {
        // 全部数字都被使用时，检查余数是否为 0 以判定成功
        if (key == (1 << nums.length) - 1) {
            return remain == 0 ? successDFS : failedDFS;
        }
        // 如果该状态已计算过，直接返回
        if (dp[key][remain] == null) {
            dp[key][remain] = failedDFS;  // 默认标记为失败
            // 枚举所有未使用的数字
            for (int i = 0; i < nums.length; ++i) {
                if (!isUsed(key, i)) {
                    // 拼接后新余数
                    int newRem = (remain * multiply[strLen[i]] % k + nums[i]) % k;
                    Node tmp = dfs(nums, strLen, dp, key | (1 << i), newRem, k);
                    if (tmp != failedDFS) {
                        // 若当前还无解则直接更新，否则比较字典序取更小
                        List<Integer> cand = new ArrayList<>();
                        cand.add(nums[i]);
                        cand.addAll(tmp.list);
                        if (dp[key][remain] == failedDFS ||
                            replace(cand, dp[key][remain].list)) {
                            dp[key][remain] = new Node(cand);
                        }
                    }
                }
            }
        }
        return dp[key][remain];
    }

    // 检查第 i 位是否被使用
    private boolean isUsed(int key, int i) {
        return ((key >> i) & 1) == 1;
    }

    // 比较两个列表的字典序，cur < pre 时返回 true
    private boolean replace(List<Integer> cur, List<Integer> pre) {
        for (int i = 0; i < cur.size(); ++i) {
            if (cur.get(i).compareTo(pre.get(i)) < 0) {
                return true;
            } else if (cur.get(i).compareTo(pre.get(i)) > 0) {
                return false;
            }
        }
        return false;
    }
}

100653. Path Existence Queries in a Graph II

给你一个整数 n，表示图中的节点数量，这些节点按从 0 到 n - 1 编号。

同时给你一个长度为 n 的整数数组 nums，以及一个整数 maxDiff。

如果满足 |nums[i] - nums[j]| <= maxDiff（即 nums[i] 和 nums[j] 的 绝对差 至多为 maxDiff），则节点 i 和节点 j 之间存在一条 无向边 。

此外，给你一个二维整数数组 queries。对于每个 queries[i] = [ui, vi]，找到节点 ui 和节点 vi 之间的 最短距离 。如果两节点之间不存在路径，则返回 -1。

返回一个数组 answer，其中 answer[i] 是第 i 个查询的结果。

注意：节点之间的边是无权重（unweighted）的。

测试样例：

输入：n = 5, nums = [1,8,3,4,2], maxDiff = 3, queries = [[0,3],[2,4]]

输出：[1,1]

解释:
查询 最短路径 最短距离
[0, 3] 0 → 3 1
[2, 4] 2 → 4 1
因此，输出为 [1, 1]。

解答：

1. 与第一问类似，先对节点按 nums[i] 值排序，得到 sort[] 和映射 map[]，并构造连通分量编号 cc[]，用于快速判断两个节点是否可达；
2. 为了求最短路径长度，引入“倍增”思想：先计算 jump[i]，表示从排序后位置 i 出发，能一步到达的最远位置（即最大 j 使得 sortedVals[j] - sortedVals[i] <= maxDiff）；
3. 构建 up[k][i] 数组，其中 up[0][i] = jump[i]，up[k][i] = up[k-1][ up[k-1][i] ]，用于二进制倍增跳跃；
4. 对于查询 [u,v]，先判断同分量；若同分量，令 l = map[u], r = map[v] 并保证 l < r，从最高位向下尝试倍增跳跃，统计跳跃次数，最终得到最少步数。

class Solution {
    public int[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
        // 1. 对节点按 nums 值排序，得到 sort[] 和 map[]
        Integer[] sort = new Integer[n];
        for (int i = 0; i < n; i++) sort[i] = i;
        Arrays.sort(sort, (a, b) -> Integer.compare(nums[a], nums[b]));
        int[] map = new int[n], sortedVals = new int[n];
        for (int i = 0; i < n; i++) {
            sortedVals[i] = nums[sort[i]];
            map[sort[i]] = i;
        }

        // 2. 构造连通分量编号 cc[]
        int[] cc = new int[n];
        cc[0] = 0;
        for (int i = 1; i < n; i++) {
            cc[i] = cc[i - 1] + (sortedVals[i] - sortedVals[i - 1] > maxDiff ? 1 : 0);
        }

        // 3. 预处理 jump[i]：从 i 能一步跳到的最远位置
        int[] jump = new int[n];
        int r = 0;
        for (int i = 0; i < n; ++i) {
            while (r + 1 < n && sortedVals[r + 1] - sortedVals[i] <= maxDiff) {
                r++;
            }
            jump[i] = r;
        }

        // 4. 构建倍增表 up[k][i]
        int jumpLog = 32 - Integer.numberOfLeadingZeros(n);
        int[][] up = new int[jumpLog][n];
        up[0] = jump;
        for (int k = 1; k < jumpLog; k++) {
            for (int i = 0; i < n; i++) {
                up[k][i] = up[k - 1][ up[k - 1][i] ];
            }
        }

        int q = queries.length;
        int[] res = new int[q];
        // 5. 处理每个查询
        for (int i = 0; i < q; i++) {
            int u = queries[i][0], v = queries[i][1];
            int pu = map[u], pv = map[v];
            // 同一节点距离为 0
            if (pu == pv) {
                res[i] = 0;
                continue;
            }
            // 不同连通分量，无路径
            if (cc[pu] != cc[pv]) {
                res[i] = -1;
                continue;
            }
            // 保证从小到大跳
            if (pu > pv) {
                int tmp = pu; pu = pv; pv = tmp;
            }
            // 从高位到低位尝试倍增跳跃，累加步数
            int cur = pu, cnt = 0;
            for (int k = jumpLog - 1; k >= 0; k--) {
                if (up[k][cur] < pv) {
                    cur = up[k][cur];
                    cnt += 1 << k;
                }
            }
            // 最后一步到达或超过 pv
            res[i] = cnt + 1;
        }
        return res;
    }
}