Kimi LeetCode 3534. 针对图的路径存在性查询 II Java实现
以下是 LeetCode 3534. 针对图的路径存在性查询 II 的完整 Java 实现及思路解析。---核心思路1. 排序将节点按 nums 值排序。排序后若两节点值差 ≤ maxDiff则它们在同一连通分量中且同一连通分量内的节点在排序数组中连续出现。2. 最远跳对排序后每个位置 i用双指针求出从 i 出发一步能到达的最远位置 nxt[i]即满足 sortedNums[nxt[i]] - sortedNums[i] ≤ maxDiff 的最大下标。3. 倍增预处理jump[i][k] 表示从 i 连续做 2^k 次最远跳到达的位置。利用 nxt 的单调性可在 O(n log n) 内完成预处理。4. 查询回答对每个查询 (u, v)先映射到排序后的位置判断是否在同一连通分量若在同一分量用倍增贪心从低位到高位尝试跳跃求出最少步数。时间复杂度O(n log n q log n)空间复杂度O(n log n)。---Java 代码javaimport java.util.*;class Solution {public int[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {// 1. 按 nums 值排序记录原始下标 - 排序后位置的映射Integer[] order new Integer[n];for (int i 0; i n; i) {order[i] i;}Arrays.sort(order, (a, b) - Integer.compare(nums[a], nums[b]));int[] sortedNums new int[n];int[] pos new int[n]; // pos[originalIndex] sortedPositionfor (int i 0; i n; i) {sortedNums[i] nums[order[i]];pos[order[i]] i;}// 2. 计算连通分量编号排序后连续段int[] comp new int[n];int cid 0;for (int i 1; i n; i) {if (sortedNums[i] - sortedNums[i - 1] maxDiff) {cid;}comp[i] cid;}// 3. 双指针求 nxt[i]从排序后位置 i 一步能跳到的最远位置int[] nxt new int[n];int r 0;for (int i 0; i n; i) {while (r 1 n sortedNums[r 1] - sortedNums[i] maxDiff) {r;}nxt[i] r;}// 4. 倍增数组jump[i][k] 表示从 i 连续跳 2^k 次最远跳到达的位置int LOG 32 - Integer.numberOfLeadingZeros(n);int[][] jump new int[n][LOG];for (int i 0; i n; i) {jump[i][0] nxt[i];}for (int k 1; k LOG; k) {for (int i 0; i n; i) {jump[i][k] jump[jump[i][k - 1]][k - 1];}}// 5. 回答查询int m queries.length;int[] ans new int[m];for (int i 0; i m; i) {int u queries[i][0];int v queries[i][1];if (u v) {ans[i] 0;continue;}int pu pos[u];int pv pos[v];if (pu pv) {int tmp pu;pu pv;pv tmp;}// 不在同一连通分量不可达if (comp[pu] ! comp[pv]) {ans[i] -1;continue;}// 倍增贪心从高位到低位能跳就跳求最少步数int cur pu;int steps 0;for (int k LOG - 1; k 0; k--) {if (jump[cur][k] pv) {steps 1 k;cur jump[cur][k];}}// 最后一步一定能到达 pvans[i] steps 1;}return ans;}}---关键点说明步骤 说明排序映射 pos[u] 将原始节点编号映射到排序后的位置所有后续操作都在排序后的数组上进行。连通分量 排序后若相邻元素差 maxDiff则开启新连通分量。查询时先判断 comp[pu] comp[pv]。最远跳 nxt 由于数组已排序双指针可在 O(n) 内求出每个位置一步能覆盖的最远范围。倍增 jump 类似树上倍增但这里是区间最远跳的倍增。jump[i][k] 表示从 i 出发连续做 2^k 次贪心最远跳到达的位置。查询贪心 从 pu 到 pv从高位到低位尝试如果跳 2^k 步后仍到不了 pv就先跳这 2^k 步。最终剩余距离只需一步即可覆盖。
