欢迎大家加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];
}
}