欢迎大家加QQ群:623375442。今天的题目不算是很难。

100668. Smallest Index With Digit Sum Equal to Index

给你一个整数数组 nums 。

返回满足 nums[i] 的数位和(每一位数字相加求和)等于 i 的 最小 下标 i 。

如果不存在满足要求的下标,返回 -1 。

测试样例:

输入:nums = [1,3,2]

输出:2

解释:nums[2] = 2,其数位和等于 2 ,与其下标 i = 2 相等。因此,输出为 2 。

解答:遍历数组 nums 的每个下标 i,计算 nums[i] 的数位和,如果等于 i,则返回该下标。若遍历结束后仍未找到,返回 -1。

class Solution {
    public int smallestIndex(int[] nums) {
        // 从下标 0 开始遍历
        for (int i = 0; i < nums.length; ++i) {
            // 当数位和等于当前下标时,立即返回该下标
            if (sumDigit(nums[i]) == i) return i;
        }
        // 若无符合条件的下标,则返回 -1
        return -1;
    }

    // 计算整数 n 的数位和
    private int sumDigit(int n) {
        int res = 0;
        // 持续取出最低位累加
        while (n > 0) {
            res += n % 10;
            n /= 10;
        }
        return res;
    }
}

100649. Minimum Swaps to Sort by Digit Sum

给你一个由 互不相同 的正整数组成的数组 nums,需要根据每个数字的数位和(即每一位数字相加求和)按 升序 对数组进行排序。如果两个数字的数位和相等,则较小的数字排在前面。

返回将 nums 排列为上述排序顺序所需的 最小 交换次数。

一次 交换 定义为交换数组中两个不同位置的值。

测试样例:

输入:nums = [37,100]

输出:1

解释: 计算每个整数的数位和:[3 + 7 = 10, 1 + 0 + 0 = 1] → [10, 1]。根据数位和排序:[100, 37]。将 37 与 100 交换,得到排序后的数组。因此,将 nums 排列为排序顺序所需的最小交换次数为 1。

解答

  1. 先计算每个元素的数位和 digits[i];
  2. 构造一个下标数组 sort,按数位和升序排序;若数位和相同,则按数值大小排序;
  3. 将当前下标和目标下标视为并查集中的一条“需要交换”的连接,统计每个连通分量的大小,答案即为各分量大小减一的和。
class Solution {
    public int minSwaps(int[] nums) {
        int n = nums.length;
        // digits[i] 存储 nums[i] 的数位和
        int[] digits = new int[n];
        // sort 数组存储原始下标,后面按自定义规则排序
        Integer[] sort = new Integer[n];
        for (int i = 0; i < n; ++i) {
            digits[i] = sumDigit(nums[i]);
            sort[i] = i;
        }
        // 按数位和升序;若相等,则按数字大小升序
        Arrays.sort(sort, (a, b) ->
            digits[a] == digits[b]
                ? Integer.compare(nums[a], nums[b])
                : Integer.compare(digits[a], digits[b])
        );
        // 并查集:将每个下标与其排序后的位置下标 union
        DSU uf = new DSU(n);
        for (int i = 0; i < n; ++i) {
            uf.union(i, sort[i]);
        }
        // 统计每个根节点对应的分量大小
        int[] count = new int[n];
        for (int i = 0; i < n; ++i) {
            count[uf.find(i)] += 1;
        }
        int res = 0;
        // 每个连通分量内至少需要 size-1 次交换
        for (int i = 0; i < n; ++i) {
            if (count[i] > 0) {
                res += count[i] - 1;
            }
        }
        return res;
    }

    // 计算数位和
    private int sumDigit(int n) {
        int res = 0;
        while (n > 0) {
            res += n % 10;
            n /= 10;
        }
        return res;
    }
}

// 并查集模板
class DSU {
    int[] parent;

    public DSU(int N) {
        parent = new int[N];
        // 初始时,每个节点的父节点是自己
        for (int i = 0; i < N; ++i) {
            parent[i] = i;
        }
    }

    // 查找根节点,路径压缩
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    // 合并 x 所在集合和 y 所在集合
    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}

100639. Grid Teleportation Traversal

给你一个大小为 m x n 的二维字符网格 matrix,用字符串数组表示,其中 matrix[i][j] 表示第 i 行和第 j 列处的单元格。每个单元格可以是以下几种字符之一:

  • '.' 表示一个空单元格。
  • '#' 表示一个障碍物。
  • 一个大写字母('A' 到 'Z')表示一个传送门。

你从左上角单元格 (0, 0) 出发,目标是到达右下角单元格 (m - 1, n - 1)。你可以从当前位置移动到相邻的单元格(上、下、左、右),移动后的单元格必须在网格边界内且不是障碍物。

如果你踏入一个包含传送门字母的单元格,并且你之前没有使用过该传送门字母,你可以立即传送到网格中另一个具有相同字母的单元格。这次传送不计入移动次数,但每个字母对应的传送门在旅程中 最多 只能使用一次。

返回到达右下角单元格所需的 最少 移动次数。如果无法到达目的地,则返回 -1。

测试样例:

输入:matrix = ["A..",".A.","..."]

输出:2

解释: 在第一次移动之前,从 (0, 0) 传送到 (1, 1)。第一次移动,从 (1, 1) 移动到 (1, 2)。第二次移动,从 (1, 2) 移动到 (2, 2)。

解答:使用 0-1 BFS(双端队列)维护当前位置到各点的最短步数,其中普通移动代价为 1,传送代价为 0;每个字母传送门只能使用一次,因此用 used 数组标记某字母是否已被使用过,使用后立即清空该字母列表以避免重复计算。

class Solution {
    // 定义移动方向:右、下、左、上
    private static final int[] moves = {1, 0, -1, 0, 1};

    public int minMoves(String[] matrix) {
        int m = matrix.length, n = matrix[0].length();
        // 存储每个字母对应的所有传送门坐标
        List<int[]>[] teleportation = new ArrayList[26];
        for (int i = 0; i < 26; ++i) {
            teleportation[i] = new ArrayList<>();
        }
        // 预处理,将所有大写字母坐标加入对应列表
        for (int i = 0; i < m; ++i) {
            String row = matrix[i];
            for (int j = 0; j < n; ++j) {
                char c = row.charAt(j);
                if (Character.isUpperCase(c)) {
                    teleportation[c - 'A'].add(new int[]{i, j});
                }
            }
        }
        // distance[i][j] 记录 (i,j) 的最短移动次数,初始化为 INF
        int[][] distance = new int[m][n];
        for (int i = 0; i < m; ++i) {
            Arrays.fill(distance[i], Integer.MAX_VALUE);
        }
        // used[k] 表示字母 'A'+k 的传送门是否已使用
        boolean[] used = new boolean[26];
        Deque<int[]> queue = new ArrayDeque<>();
        // 起点距离设为 0,加入队列头
        distance[0][0] = 0;
        queue.addFirst(new int[]{0, 0});

        while (!queue.isEmpty()) {
            int[] cur = queue.removeFirst();
            int x = cur[0], y = cur[1], d = distance[x][y];
            // 若到达终点,可提前退出
            if (x == m - 1 && y == n - 1) break;

            // 处理传送门:如果当前位置是大写字母,且未使用过该字母的传送
            char c = matrix[x].charAt(y);
            if (Character.isUpperCase(c)) {
                int idx = c - 'A';
                if (!used[idx]) {
                    used[idx] = true;
                    // 将所有同字母位置以同样的距离加入队列头(0-1 BFS 中的“0 代价”)
                    for (int[] p : teleportation[idx]) {
                        int px = p[0], py = p[1];
                        if (distance[px][py] > d) {
                            distance[px][py] = d;
                            queue.addFirst(new int[]{px, py});
                        }
                    }
                    // 清空该列表,避免重复传送
                    teleportation[idx].clear();
                }
            }

            // 普通四方向移动
            for (int k = 0; k < 4; ++k) {
                int nx = x + moves[k], ny = y + moves[k + 1];
                // 检查边界与障碍物,并更新距离
                if (nx >= 0 && nx < m && ny >= 0 && ny < n
                        && matrix[nx].charAt(ny) != '#'
                        && distance[nx][ny] > d + 1) {
                    distance[nx][ny] = d + 1;
                    queue.addLast(new int[]{nx, ny});
                }
            }
        }
        int res = distance[m - 1][n - 1];
        // 若仍为 INF,则不可达,返回 -1
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

100654. Minimum Weighted Subgraph With the Required Paths II

给你一个 无向带权 树,共有 n 个节点,编号从 0 到 n - 1。这棵树由一个二维整数数组 edges 表示,长度为 n - 1,其中 edges[i] = [ui, vi, wi] 表示存在一条连接节点 ui 和 vi 的边,权重为 wi。

此外,给你一个二维整数数组 queries,其中 queries[j] = [src1j, src2j, destj]。

返回一个长度等于 queries.length 的数组 answer,其中 answer[j] 表示一个子树的 最小总权重 ,使用该子树的边可以从 src1j 和 src2j 到达 destj 。

这里的 子树 是指原树中任意节点和边组成的连通子集形成的一棵有效树。

测试样例:

输入:edges = [[0,1,2],[1,2,3],[1,3,5],[1,4,4],[2,5,6]], queries = [[2,3,4],[0,2,5]]

输出:[12,11]

解释: answer[0]:在选出的子树中,从 src1 = 2 和 src2 = 3 到 dest = 4 的路径总权重为 3 + 5 + 4 = 12。answer[1]:在选出的子树中,从 src1 = 0 和 src2 = 2 到 dest = 5 的路径总权重为 2 + 3 + 6 = 11。

解答:本题在树上回答多组查询,每个查询要求在一个“子树”中同时连通 src1、src2 到 dest,即这三点在原树上所需的最小连通子图总权重。对于树,这等价于求三条路径权重之和的一半(因为三条路径各自走过的公共边会被重复计算两次)。

  1. 以节点 0 为根,预处理得到每个节点到根的距离 dist2zero[u] 及倍增祖先表 ancestors[u].up[k];
  2. 对任意两节点 (u,v),通过 LCA 算法计算它们之间的距离;
  3. 对查询 [src1, src2, dest],令三段距离分别为 duv, dvw, duw,答案即 (duv + dvw + duw) / 2。
class Solution {
    // Ancestor 用于存储倍增祖先 up[k] 及节点深度 depth
    class Ancestor {
        int[] up;
        int depth;
        public Ancestor(int maxLength) {
            up = new int[maxLength];
        }
    }

    public int[] minimumWeight(int[][] edges, int[][] queries) {
        int n = edges.length + 1;
        // 计算倍增表最大层数(足以覆盖深度至 n)
        int maxLength = 32 - Integer.numberOfLeadingZeros(n);

        // 构建邻接表
        List<int[]>[] graph = new List[n];
        Ancestor[] ancestors = new Ancestor[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
            ancestors[i] = new Ancestor(maxLength);
        }
        // 将边加入无向图
        for (int[] e : edges) {
            graph[e[0]].add(new int[]{e[1], e[2]});
            graph[e[1]].add(new int[]{e[0], e[2]});
        }

        // dist2zero[u] 存储从根(0)到 u 的累计权重
        int[] dist2zero = new int[n];
        // DFS 初始化 depth、up[0](父节点)和 dist2zero
        dfs(0, -1, 0, 0, graph, ancestors, dist2zero);

        // 构造完整的倍增祖先表
        for (int k = 1; k < maxLength; k++) {
            for (int v = 0; v < n; v++) {
                int mid = ancestors[v].up[k - 1];
                // 若中间祖先存在,则 up[k] 为 up[k-1] 的 up[k-1]
                ancestors[v].up[k] = (mid < 0 ? -1 : ancestors[mid].up[k - 1]);
            }
        }

        int[] res = new int[queries.length];
        // 逐条处理查询
        for (int i = 0; i < queries.length; i++) {
            int src1 = queries[i][0], src2 = queries[i][1], dest = queries[i][2];
            // 分别计算三对之间的距离
            long duv = distance(src1, src2, ancestors, dist2zero);
            long dvw = distance(src2, dest, ancestors, dist2zero);
            long duw = distance(src1, dest, ancestors, dist2zero);
            // 答案为三条路径和的一半
            res[i] = (int)((duv + dvw + duw) / 2);
        }

        return res;
    }

    // 从 u 开始 DFS,p 为父节点,depth 为深度,d 为累积距离
    private void dfs(int u, int p, int depth, int d,
                     List<int[]>[] graph, Ancestor[] ancestors, int[] dist) {
        ancestors[u].up[0] = p;          // 记录父节点
        ancestors[u].depth = depth;     // 记录深度
        dist[u] = d;                    // 记录从根到 u 的距离
        for (int[] nei : graph[u]) {
            int v = nei[0], w = nei[1];
            if (v == p) continue;       // 避免回到父节点
            dfs(v, u, depth + 1, d + w, graph, ancestors, dist);
        }
    }

    // 计算 u 和 v 的最低公共祖先
    private int lca(int u, int v, Ancestor[] ancestors) {
        // 保证 u 在更深的一侧
        if (ancestors[u].depth < ancestors[v].depth) {
            int t = u; u = v; v = t;
        }
        int diff = ancestors[u].depth - ancestors[v].depth;
        // 将 u 提升到与 v 同一深度
        for (int k = 0; k < ancestors[u].up.length; k++) {
            if ((diff & (1 << k)) != 0) {
                u = ancestors[u].up[k];
            }
        }
        if (u == v) return u;
        // 二分向上同时提升,找到 LCA
        for (int k = ancestors[u].up.length - 1; k >= 0; k--) {
            if (ancestors[u].up[k] != ancestors[v].up[k]) {
                u = ancestors[u].up[k];
                v = ancestors[v].up[k];
            }
        }
        return ancestors[u].up[0];
    }

    // 计算两节点间距离:dist(u,v) = dist2zero[u] + dist2zero[v] - 2 * dist2zero[lca]
    private int distance(int u, int v, Ancestor[] anc, int[] dist) {
        int a = lca(u, v, anc);
        return dist[u] + dist[v] - 2 * dist[a];
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *