55. 跳跃游戏

典型的贪心问题。对于一个可跳的序列：[2,3,1,1,4]存在一个问题就是，比如在位置1，可达区域就为1..=1+3，因此我只需要遍历当前可达区域内存在的跳跃能量是否支持我继续扩大可达区域，直到覆盖最后一个位置即可。

  1. /// 55. 跳跃游戏
  2. pub fn can_jump(nums: Vec<i32>) -> bool {
  3.     let mut max_arrive = 0;
  4.     for x in 0..nums.len() {
  5.         // 超过了可达区域，直接寄
  6.         if x > max_arrive { return false; }
  7.         max_arrive = max_arrive.max(x + nums[x] as usize);
  8.     }
  9.     true
  10. }

45. 跳跃游戏 II

相比上一题，这一题多了一个测算跳跃的最少步数。思路还是大体一样，找到当前的可达区域，探寻可达区域内能够跳到的最远位置，那么就从这个位置起跳。
看题解的图：
image.png

  1. // 该题解的作者的代码
  2. int jump(vector<int> &nums)
  3. {
  4.     int ans = 0;
  5.     int start = 0;
  6.     int end = 1;
  7.     while (end < nums.size())
  8.     {
  9.         int maxPos = 0;
  10.         for (int i = start; i < end; i++)
  11.         {
  12.             // 能跳到最远的距离
  13.             maxPos = max(maxPos, i + nums[i]);
  14.         }
  15.         start = end;      // 下一次起跳点范围开始的格子
  16.         end = maxPos + 1; // 下一次起跳点范围结束的格子
  17.         ans++;            // 跳跃次数
  18.     }
  19.     return ans;
  20. }
  21. /// 45. 跳跃游戏 II
  22. pub fn jump(nums: Vec<i32>) -> i32 {
  23.     let (mut ans, mut start, mut end) = (0, 0, 1);
  24.     while end < nums.len() {
  25.         // 最大可达区间
  26.         let mut max_arrive = 0;
  27.         for i in start..end {
  28.             max_arrive = max_arrive.max(i + nums[i]);
  29.         }
  30.         // 更新搜索区间
  31.         start = end;
  32.         end = max_arrive + 1;
  33.         ans += 1;
  34.     }
  35.     ans
  36. }

优化一下：
image.png

  1. /// 45. 跳跃游戏 II
  2. pub fn jump(nums: Vec<i32>) -> i32 {
  3.     let (mut ans, mut max_arrive, mut end) = (0, 0, 0);
  4.     // 注意这个-1，不然在最后一个位置会多算一次
  5.     for i in 0..nums.len()-1 {
  6.         max_arrive = max_arrive.max(i + nums[i] as usize);
  7.         if i == end {
  8.             // 走到了上一个可达区间的末尾，更新为新的可达区间末尾
  9.             end = max_arrive;
  10.             ans += 1;
  11.         }
  12.     }
  13.     ans
  14. }

1345. 跳跃游戏 IV

这一题已经进化为了图搜索问题，看图那一章