跳跃游戏系列总结

55 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

class Solution {
    public boolean canJump(int[] nums) {
//能跳到的位置一定是连续的一段
//j标记当前能跳到的最大下标
      for(int i=0,j=0;i<nums.length;i++){
          if(j<i) return false;
          j=Math.max(j,i+nums[i]);
      }
      return true;
    }
}

45跳跃游戏||

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

//关键在于f[i]的值是一段一段1,2,3单调的，如果i<=last+nums[last]说明i的位置可以从last跳过去，那么i就是从last
//那段跳过来的，值就比f[last]大一，从last这一点后面跳过去肯定是距离更长或相等的，所以就不用考虑last后面的位
//置跳到位置i的情况，也不可能出现从last之前的位置跳到i的情况，因为last比当前last小的时候都是符合while里面的
//条件的，也就是说跳不到超过或等于i的范围。
//i也在增大，如果之前的last连之前的i都到不了更到不了当前这个增大了的i，所以不用回头讨论last(这样就优化掉一重循环)
//可以看成有向图，求的是起点到终点最少经过几条边，但是有n^2条边，所以会超时
//f[i]表示从i到终点的最短距离（最小边数），也会超时
//必须将dp优化，f[i]的性质：单调
//f[i]表示起点到当前点的最小步数，有一段跳一步可以到，有一段跳两步可以到
class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        f[0] = 0;
        int last = 0;

        for (int i = 1; i < n; i++) {
            // 依次求 f[i] 的值。
            while (i > last + nums[last]) // 根据 i 来更新 last。
                last++;

            f[i] = f[last] + 1; // 根据 f[last] 更新 f[i]。
        }

        return f[n - 1];
    }
};

//此法需和lc 1024一起理解
class Solution {
<!--在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。
我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。-->

<!--在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，
我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。
如果访问最后一个元素，在边界正好为最后一个位置的情况下，
我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。-->

    public int jump(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0; 
        int steps = 0;
        //这题和1024的区别是是闭区间end是能跳到的
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]); 
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/jump-game-ii/solutions/230241/tiao-yue-you-xi-ii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1024视频拼接

不一定能到达且要求最小步数

class Solution {
    public int videoStitching(int[][] clips, int time) {
        int[] maxn = new int[time];
        int last = 0, ret = 0, pre = 0;
        for (int[] clip : clips) {
            if (clip[0] < time) {
                maxn[clip[0]] = Math.max(maxn[clip[0]], clip[1]);
            }
        }
        for (int i = 0; i < time; i++) {
            last = Math.max(last, maxn[i]);
            if (i == last) { //last 当前段 段1能跳到的最远点
                return -1;
            }
            if (i == pre) { //pre 段0能跳到的最远点（开区间pre本身跳不到）到了pre说明进入段2了
                ret++;
                pre = last;
            }
        }
        return ret;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/video-stitching/solutions/458461/shi-pin-pin-jie-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1306. 跳跃游戏 III

这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。

请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。

注意，不管是什么情况下，你都无法跳到数组之外。
图论 简单DFS/BFS

class Solution {
public:
    bool dfs(vector<int>& a, int k) {
        if (!a[k]) return true;
        int pos[] = {k - a[k], k + a[k]};
        a[k] = -1;
        for (auto x: pos) {
            if (x >= 0 && x < a.size() && a[x] != -1) {
                if (dfs(a, x)) return true;
            }
        }
        return false;
    }

    bool canReach(vector<int>& arr, int start) {
        return dfs(arr, start);
    }
};

1345. 跳跃游戏 IV

困难BFS

1340

dp记忆化搜索

1696

dp加单调队列

1871

dp加滑窗/前缀和

2297

dp加单调栈