以下是 LeetCode 3534. 针对图的路径存在性查询 II 的完整 Python3 实现。---核心思路1. 排序将节点按 nums 值排序。排序后同一连通分量内的节点必然连续。2. 双指针求最远跳对每个位置 i求出一步能到达的最远位置 nxt[i]。3. 倍增预处理jump[i][k] 表示从 i 连续做 2^k 次最远跳到达的位置。4. 查询先判断是否在同一连通分量再用倍增贪心求最少步数。时间复杂度O(n log n q log n)空间复杂度O(n log n)。---Python3 代码pythonfrom typing import Listclass Solution:def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) - List[int]:# 1. 按 nums 值排序记录原始下标 - 排序后位置的映射order sorted(range(n), keylambda x: nums[x])sorted_nums [nums[i] for i in order]pos [0] * n # pos[originalIndex] sortedPositionfor i, idx in enumerate(order):pos[idx] i# 2. 计算连通分量编号排序后连续段comp [0] * nfor i in range(1, n):comp[i] comp[i - 1]if sorted_nums[i] - sorted_nums[i - 1] maxDiff:comp[i] 1# 3. 双指针求 nxt[i]从排序后位置 i 一步能跳到的最远位置nxt [0] * nr 0for i in range(n):while r 1 n and sorted_nums[r 1] - sorted_nums[i] maxDiff:r 1nxt[i] r# 4. 倍增数组jump[i][k] 表示从 i 连续跳 2^k 次最远跳到达的位置LOG (n 1).bit_length()jump [[0] * LOG for _ in range(n)]for i in range(n):jump[i][0] nxt[i]for k in range(1, LOG):for i in range(n):jump[i][k] jump[jump[i][k - 1]][k - 1]# 5. 回答查询ans []for u, v in queries:if u v:ans.append(0)continuepu, pv pos[u], pos[v]if pu pv:pu, pv pv, pu# 不在同一连通分量不可达if comp[pu] ! comp[pv]:ans.append(-1)continue# 倍增贪心从高位到低位能跳就跳求最少步数cur pusteps 0for k in range(LOG - 1, -1, -1):if jump[cur][k] pv:steps 1 kcur jump[cur][k]# 最后一步一定能到达 pvans.append(steps 1)return ans---关键点说明步骤 说明排序映射 pos[u] 将原始节点编号映射到排序后的位置后续操作都在排序后的数组上进行。连通分量 排序后若相邻元素差 maxDiff则开启新连通分量。查询时先判断 comp[pu] comp[pv]。最远跳 nxt 由于数组已排序双指针可在 O(n) 内求出每个位置一步能覆盖的最远范围。nxt[i] 单调不降。倍增 jump 类似树上倍增但这里是区间最远跳的倍增。jump[i][k] 表示从 i 出发连续做 2^k 次贪心最远跳到达的位置。查询贪心 从 pu 到 pv从高位到低位尝试如果跳 2^k 步后仍到不了 pv就先跳这 2^k 步。最终剩余距离只需一步即可覆盖。
