欢迎大家加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。
解答：
- 先计算每个元素的数位和 digits[i]；
- 构造一个下标数组 sort，按数位和升序排序；若数位和相同，则按数值大小排序；
- 将当前下标和目标下标视为并查集中的一条“需要交换”的连接，统计每个连通分量的大小，答案即为各分量大小减一的和。
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，即这三点在原树上所需的最小连通子图总权重。对于树，这等价于求三条路径权重之和的一半（因为三条路径各自走过的公共边会被重复计算两次）。
- 以节点 0 为根，预处理得到每个节点到根的距离 dist2zero[u] 及倍增祖先表 ancestors[u].up[k]；
- 对任意两节点 (u,v)，通过 LCA 算法计算它们之间的距离；
- 对查询 [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];
}
}