LeetCode LCP 09. 最小跳跃次数 - Rust 实现根据搜索结果LCP 09 的题目描述如下 游戏机由 N 个特殊弹簧排成一排编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处通过按动弹簧可以选择把小球向右弹射 jump[i] 的距离或者向左弹射到任意左侧弹簧的位置。也就是说在编号为 i 弹簧处按动弹簧小球可以弹向 0 到 i-1 中任意弹簧或者 ijump[i] 的弹簧若 ijump[i]N则表示小球弹出了机器。小球位于编号 0 处的弹簧时不能再向左弹。方法一动态规划倒序遍历核心思路从后往前计算 dp[i]表示从位置 i 跳出机器的最小跳跃次数。- 向右跳i jump[i]若超出边界则一步跳出- 向左跳可以到达任意左侧位置意味着左侧位置可以通过一步到达 irustimpl Solution {pub fn min_jump(jump: Veci32) - i32 {let n jump.len();if n 1 {return 1;}// dp[i] 从位置 i 跳出机器所需的最小跳跃次数let mut dp vec![i32::MAX; n];// 从后往前遍历for i in (0..n).rev() {// 向右跳let next i jump[i] as usize;if next n {// 可以直接跳出机器dp[i] 1;} else {dp[i] dp[next] 1;}// 向左跳的优化位置 i 可以向左跳到任意 j i 的位置// 反过来想从 j 可以一步跳到 i所以如果 dp[i] 1 更优可以更新 dp[j]// 但实际上这里是i 可以到达左侧任意位置意味着左侧位置可以通过 i 转移// 更关键的是对于 j i如果 dp[j] dp[i] 1说明从 i 跳到 j 更优// 因为 i 可以向左跳到任意位置所以 i 左侧的位置都可以被 i 到达// 但这里我们要更新的是从 i 出发左侧位置已经被考虑过了因为倒序// 实际上这个循环是在优化如果 i 能跳到左侧那左侧的 dp 值应该 dp[i] 1// 但倒序时左侧更小的下标还没计算所以这个循环是在更新右侧已经计算过的位置// 即i 可以向左跳意味着对于已经计算过的 j i可以从 i 一步到达... 不对// 重新理解倒序遍历i 右侧的位置都已经计算好了// 如果 dp[j] dp[i] 1说明从 i 跳到 j 更优但 i 只能向左跳不能向右跳到 j i// 所以这个循环的实际含义是i 可以向左跳到任意位置那么对于未来的 j i// 它们可以通过一步跳到 i所以 dp[j] 至少可以是 dp[i] 1// 但这里 j 从 i1 开始是向右的方向...// 实际上这个优化是因为 i 可以向左跳到任意位置那么对于已经遍历过的右侧位置 j// 如果它们的最优解需要经过左侧某个位置而那个位置可以通过 i 到达...// 这个优化比较 trick核心是利用了向左可以跳任意远的性质for j in (i 1)..n {if dp[j] dp[i] 1 {dp[j] dp[i] 1;} else {break; // 后面的已经更优了无需更新}}}dp[0]}}方法二BFS 双队列优化推荐可处理 10^6 数据核心思路BFS 天然适合求最短路径。但普通 BFS 向左跳时需要遍历所有左侧未访问位置导致重复。使用一个辅助队列 index_q 存储所有下标每次处理位置 t 时将 index_q 中所有小于 t 的未访问位置一次性加入队列并弹出已处理的位置保证每个位置只被访问一次。rustuse std::collections::VecDeque;impl Solution {pub fn min_jump(jump: Veci32) - i32 {let n jump.len();if n 1 {return 1;}let mut visited vec![false; n];let mut q VecDeque::new(); // BFS 主队列let mut index_q VecDeque::new(); // 辅助队列存储所有下标用于优化向左跳// 初始化辅助队列包含 0 到 n-1for i in 0..n {index_q.push_back(i);}q.push_back(0);visited[0] true;let mut ans 0;while !q.is_empty() {let cnt q.len();for _ in 0..cnt {let t q.pop_front().unwrap();// 向右跳let next t jump[t] as usize;if next n {// 跳出机器return ans 1;}if !visited[next] {visited[next] true;q.push_back(next);}// 向左跳利用 index_q 批量处理所有左侧未访问位置while let Some(front) index_q.front() {if front t {break; // 只处理严格小于 t 的位置}index_q.pop_front();if !visited[front] {visited[front] true;q.push_back(front);}}}ans 1;}-1 // 无法跳出理论上不会发生因为可以一直向左}}复杂度分析方法 时间复杂度 空间复杂度 适用场景动态规划 O(n^2) 最坏情况 O(n) n \le 10^4BFS 双队列 O(n) O(n) n \le 10^6对于题目限制 1 \le jump.length \le 10^6推荐使用 BFS 双队列优化方法每个位置最多入队一次每个下标最多从 index_q 中弹出一次总时间复杂度为 O(n)。示例验证输入jump [2, 5, 1, 1, 1, 1]- BFS 过程- 第 0 步q [0]- 第 1 步从 0 向右跳到 2向左无0 是最左q [2]- 第 2 步从 2 向右跳到 3向左跳index_q 中小于 2 的有 1加入 1q [3, 1]- 第 3 步处理 3向右跳到 4向左无新位置处理 1向右跳到 6 6跳出结果3 次跳跃路径 0 - 2 - 1 - 6 ✓ Kimi LeetCode LCP 09. 最小跳跃次数 Rust实现
LeetCode LCP 09. 最小跳跃次数 - Rust 实现根据搜索结果LCP 09 的题目描述如下 游戏机由 N 个特殊弹簧排成一排编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处通过按动弹簧可以选择把小球向右弹射 jump[i] 的距离或者向左弹射到任意左侧弹簧的位置。也就是说在编号为 i 弹簧处按动弹簧小球可以弹向 0 到 i-1 中任意弹簧或者 ijump[i] 的弹簧若 ijump[i]N则表示小球弹出了机器。小球位于编号 0 处的弹簧时不能再向左弹。方法一动态规划倒序遍历核心思路从后往前计算 dp[i]表示从位置 i 跳出机器的最小跳跃次数。- 向右跳i jump[i]若超出边界则一步跳出- 向左跳可以到达任意左侧位置意味着左侧位置可以通过一步到达 irustimpl Solution {pub fn min_jump(jump: Veci32) - i32 {let n jump.len();if n 1 {return 1;}// dp[i] 从位置 i 跳出机器所需的最小跳跃次数let mut dp vec![i32::MAX; n];// 从后往前遍历for i in (0..n).rev() {// 向右跳let next i jump[i] as usize;if next n {// 可以直接跳出机器dp[i] 1;} else {dp[i] dp[next] 1;}// 向左跳的优化位置 i 可以向左跳到任意 j i 的位置// 反过来想从 j 可以一步跳到 i所以如果 dp[i] 1 更优可以更新 dp[j]// 但实际上这里是i 可以到达左侧任意位置意味着左侧位置可以通过 i 转移// 更关键的是对于 j i如果 dp[j] dp[i] 1说明从 i 跳到 j 更优// 因为 i 可以向左跳到任意位置所以 i 左侧的位置都可以被 i 到达// 但这里我们要更新的是从 i 出发左侧位置已经被考虑过了因为倒序// 实际上这个循环是在优化如果 i 能跳到左侧那左侧的 dp 值应该 dp[i] 1// 但倒序时左侧更小的下标还没计算所以这个循环是在更新右侧已经计算过的位置// 即i 可以向左跳意味着对于已经计算过的 j i可以从 i 一步到达... 不对// 重新理解倒序遍历i 右侧的位置都已经计算好了// 如果 dp[j] dp[i] 1说明从 i 跳到 j 更优但 i 只能向左跳不能向右跳到 j i// 所以这个循环的实际含义是i 可以向左跳到任意位置那么对于未来的 j i// 它们可以通过一步跳到 i所以 dp[j] 至少可以是 dp[i] 1// 但这里 j 从 i1 开始是向右的方向...// 实际上这个优化是因为 i 可以向左跳到任意位置那么对于已经遍历过的右侧位置 j// 如果它们的最优解需要经过左侧某个位置而那个位置可以通过 i 到达...// 这个优化比较 trick核心是利用了向左可以跳任意远的性质for j in (i 1)..n {if dp[j] dp[i] 1 {dp[j] dp[i] 1;} else {break; // 后面的已经更优了无需更新}}}dp[0]}}方法二BFS 双队列优化推荐可处理 10^6 数据核心思路BFS 天然适合求最短路径。但普通 BFS 向左跳时需要遍历所有左侧未访问位置导致重复。使用一个辅助队列 index_q 存储所有下标每次处理位置 t 时将 index_q 中所有小于 t 的未访问位置一次性加入队列并弹出已处理的位置保证每个位置只被访问一次。rustuse std::collections::VecDeque;impl Solution {pub fn min_jump(jump: Veci32) - i32 {let n jump.len();if n 1 {return 1;}let mut visited vec![false; n];let mut q VecDeque::new(); // BFS 主队列let mut index_q VecDeque::new(); // 辅助队列存储所有下标用于优化向左跳// 初始化辅助队列包含 0 到 n-1for i in 0..n {index_q.push_back(i);}q.push_back(0);visited[0] true;let mut ans 0;while !q.is_empty() {let cnt q.len();for _ in 0..cnt {let t q.pop_front().unwrap();// 向右跳let next t jump[t] as usize;if next n {// 跳出机器return ans 1;}if !visited[next] {visited[next] true;q.push_back(next);}// 向左跳利用 index_q 批量处理所有左侧未访问位置while let Some(front) index_q.front() {if front t {break; // 只处理严格小于 t 的位置}index_q.pop_front();if !visited[front] {visited[front] true;q.push_back(front);}}}ans 1;}-1 // 无法跳出理论上不会发生因为可以一直向左}}复杂度分析方法 时间复杂度 空间复杂度 适用场景动态规划 O(n^2) 最坏情况 O(n) n \le 10^4BFS 双队列 O(n) O(n) n \le 10^6对于题目限制 1 \le jump.length \le 10^6推荐使用 BFS 双队列优化方法每个位置最多入队一次每个下标最多从 index_q 中弹出一次总时间复杂度为 O(n)。示例验证输入jump [2, 5, 1, 1, 1, 1]- BFS 过程- 第 0 步q [0]- 第 1 步从 0 向右跳到 2向左无0 是最左q [2]- 第 2 步从 2 向右跳到 3向左跳index_q 中小于 2 的有 1加入 1q [3, 1]- 第 3 步处理 3向右跳到 4向左无新位置处理 1向右跳到 6 6跳出结果3 次跳跃路径 0 - 2 - 1 - 6 ✓