以下是 LeetCode 3534. 针对图的路径存在性查询 II 的完整 Rust 实现。---核心思路与 Java/Python 版本一致1. 排序按 nums 值排序记录原始下标到排序后位置的映射。2. 双指针求最远跳nxt[i] 表示从排序后位置 i 一步能到达的最远位置。3. 倍增预处理jump[i][k] 表示从 i 连续做 2^k 次最远跳到达的位置。4. 查询贪心同一连通分量内从高位到低位尝试跳跃求最少步数。时间复杂度O(n log n q log n)空间复杂度O(n log n)。---Rust 代码rustuse std::collections::HashMap;impl Solution {pub fn path_existence_queries(n: i32, nums: Veci32, max_diff: i32, queries: VecVeci32) - Veci32 {let n n as usize;let max_diff max_diff as i64;// 1. 按 nums 值排序记录原始下标 - 排序后位置的映射let mut order: Vecusize (0..n).collect();order.sort_by_key(|i| nums[i]);let mut sorted_nums vec![0i64; n];let mut pos vec![0usize; n];for (i, idx) in order.iter().enumerate() {sorted_nums[i] nums[idx] as i64;pos[idx] i;}// 2. 计算连通分量编号排序后连续段let mut comp vec![0usize; n];for i in 1..n {comp[i] comp[i - 1];if sorted_nums[i] - sorted_nums[i - 1] max_diff {comp[i] 1;}}// 3. 双指针求 nxt[i]从排序后位置 i 一步能跳到的最远位置let mut nxt vec![0usize; n];let mut r 0usize;for i in 0..n {while r 1 n sorted_nums[r 1] - sorted_nums[i] max_diff {r 1;}nxt[i] r;}// 4. 倍增数组jump[i][k] 表示从 i 连续跳 2^k 次最远跳到达的位置let log (n 1).next_power_of_two().trailing_zeros() as usize;let mut jump vec![vec![0usize; log]; n];for i in 0..n {jump[i][0] nxt[i];}for k in 1..log {for i in 0..n {jump[i][k] jump[jump[i][k - 1]][k - 1];}}// 5. 回答查询let mut ans Vec::with_capacity(queries.len());for q in queries {let u q[0] as usize;let v q[1] as usize;if u v {ans.push(0);continue;}let mut pu pos[u];let mut pv pos[v];if pu pv {std::mem::swap(mut pu, mut pv);}// 不在同一连通分量不可达if comp[pu] ! comp[pv] {ans.push(-1);continue;}// 倍增贪心从高位到低位能跳就跳求最少步数let mut cur pu;let mut steps 0i32;for k in (0..log).rev() {if jump[cur][k] pv {steps (1 k) as i32;cur jump[cur][k];}}// 最后一步一定能到达 pvans.push(steps 1);}ans}}---关键点说明步骤 说明排序映射 pos[u] 将原始节点编号映射到排序后的位置。Rust 中需小心 usize 与 i32 的类型转换。连通分量 排序后若相邻元素差 max_diff则开启新连通分量。查询时先判断 comp[pu] comp[pv]。最远跳 nxt 双指针在 O(n) 内求出每个位置一步能覆盖的最远范围。nxt[i] 单调不降。倍增 jump jump[i][k] 表示从 i 出发连续做 2^k 次贪心最远跳到达的位置。利用 next_power_of_two().trailing_zeros() 计算所需层数。查询贪心 从 pu 到 pv从高位到低位尝试如果跳 2^k 步后仍到不了 pv就先跳这 2^k 步。最终剩余距离只需一步即可覆盖。 注意Rust 中 nums 值差可能溢出 i32因此内部计算时转换为 i64 处理。
以下是 LeetCode 3534. 针对图的路径存在性查询 II 的完整 Rust 实现。---核心思路与 Java/Python 版本一致1. 排序按 nums 值排序记录原始下标到排序后位置的映射。2. 双指针求最远跳nxt[i] 表示从排序后位置 i 一步能到达的最远位置。3. 倍增预处理jump[i][k] 表示从 i 连续做 2^k 次最远跳到达的位置。4. 查询贪心同一连通分量内从高位到低位尝试跳跃求最少步数。时间复杂度O(n log n q log n)空间复杂度O(n log n)。---Rust 代码rustuse std::collections::HashMap;impl Solution {pub fn path_existence_queries(n: i32, nums: Veci32, max_diff: i32, queries: VecVeci32) - Veci32 {let n n as usize;let max_diff max_diff as i64;// 1. 按 nums 值排序记录原始下标 - 排序后位置的映射let mut order: Vecusize (0..n).collect();order.sort_by_key(|i| nums[i]);let mut sorted_nums vec![0i64; n];let mut pos vec![0usize; n];for (i, idx) in order.iter().enumerate() {sorted_nums[i] nums[idx] as i64;pos[idx] i;}// 2. 计算连通分量编号排序后连续段let mut comp vec![0usize; n];for i in 1..n {comp[i] comp[i - 1];if sorted_nums[i] - sorted_nums[i - 1] max_diff {comp[i] 1;}}// 3. 双指针求 nxt[i]从排序后位置 i 一步能跳到的最远位置let mut nxt vec![0usize; n];let mut r 0usize;for i in 0..n {while r 1 n sorted_nums[r 1] - sorted_nums[i] max_diff {r 1;}nxt[i] r;}// 4. 倍增数组jump[i][k] 表示从 i 连续跳 2^k 次最远跳到达的位置let log (n 1).next_power_of_two().trailing_zeros() as usize;let mut jump vec![vec![0usize; log]; n];for i in 0..n {jump[i][0] nxt[i];}for k in 1..log {for i in 0..n {jump[i][k] jump[jump[i][k - 1]][k - 1];}}// 5. 回答查询let mut ans Vec::with_capacity(queries.len());for q in queries {let u q[0] as usize;let v q[1] as usize;if u v {ans.push(0);continue;}let mut pu pos[u];let mut pv pos[v];if pu pv {std::mem::swap(mut pu, mut pv);}// 不在同一连通分量不可达if comp[pu] ! comp[pv] {ans.push(-1);continue;}// 倍增贪心从高位到低位能跳就跳求最少步数let mut cur pu;let mut steps 0i32;for k in (0..log).rev() {if jump[cur][k] pv {steps (1 k) as i32;cur jump[cur][k];}}// 最后一步一定能到达 pvans.push(steps 1);}ans}}---关键点说明步骤 说明排序映射 pos[u] 将原始节点编号映射到排序后的位置。Rust 中需小心 usize 与 i32 的类型转换。连通分量 排序后若相邻元素差 max_diff则开启新连通分量。查询时先判断 comp[pu] comp[pv]。最远跳 nxt 双指针在 O(n) 内求出每个位置一步能覆盖的最远范围。nxt[i] 单调不降。倍增 jump jump[i][k] 表示从 i 出发连续做 2^k 次贪心最远跳到达的位置。利用 next_power_of_two().trailing_zeros() 计算所需层数。查询贪心 从 pu 到 pv从高位到低位尝试如果跳 2^k 步后仍到不了 pv就先跳这 2^k 步。最终剩余距离只需一步即可覆盖。 注意Rust 中 nums 值差可能溢出 i32因此内部计算时转换为 i64 处理。
