LeetCode 55. 跳跃游戏

55. 跳跃游戏

题目：给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
链接 https://leetcode.cn/problems/jump-game

个人思路

1. 刚开始没有思路，然后是想到用动态规划，但不知道该怎么用，然后灵光一现想到就是求当前位置能跳到的位置中所能到的最大位置，比如[3,1,4,2,4,2,1,1]，这时你有三个选择：
   ① 从下标 0 到达下标 1, 这时接下来最多能到下标2
   ② 从下标 0 到达下标 2, 这时接下来最多能到下标6
   ③ 从下标 0 到达下标 3, 这时接下来最多能到下标5
   显而易见，应该选择②，为什么这是可行的呢，因为我最多能到下标6，这已经包含了你前面的到下标5的选择，即我到下标2后，我可以不一定非得直接到下标6，我到下标5也是可以，也就是③接下来的选择其实已经包含在②中的
   代码实现：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        i = 0
        if nums[i] == 0 and len(nums) == 1:
            return True
        while i < len(nums):
            # 跳到了0的位置就没法跳
            if nums[i] == 0:
               return False
            # 跳的位置加上其接下来能跳的步数不小于数组长度，则一定能到
            if i + nums[i] >= len(nums)-1:
               return True
            # 找出该位置能跳最远的位置
            cur = 0   
            jump = i+1  # 记录其能跳最大位置的下标
            for j in range(i+1,i+nums[i]+1):
                temp = j + nums[j]
                if temp >= cur:
                    cur = temp 
                    jump = j
            i = jump
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

我这个是贪心还是动规？已经分不清了

官方思路

1. 贪心算法
   
   代码也优雅很多：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n, rightmost = len(nums), 0
        for i in range(n):
            if i <= rightmost:
                rightmost = max(rightmost, i + nums[i])
                if rightmost >= n - 1:
                    return True
        return False
1
2
3
4
5
6
7
8
9

复杂度分析
时间复杂度：O(n)，其中 n 为数组的大小。只需要访问 nums 数组一遍，共 n 个位置。
空间复杂度：O(1)，不需要额外的空间开销。

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/jump-game/solution/tiao-yue-you-xi-by-leetcode-solution/

其他思路

1. 全非0，就算一步一步跳，也一定能到！
   所以我们只需要特殊处理为0的，只要出现了0，我们就从0的位置往前去找满不满足可以跳过0的元素，如果不存在，那么直接G了啊，跳不过0就跳不到最后一个元素！

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        if(n == 1)return true;
        for(int i = n - 2; i >= 0; i--){
            if(nums[i] == 0){
                int j = i - 1;
                for(; j >= 0; j--){
                    if(nums[j] > i - j)break;
                }
                if(j < 0)return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. 动态规划
   

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        length = len(nums)
        if length == 1:
            return True
        dp = nums[0]
        if dp == 0:
            return False
        for i in range(1,length -1):
            a = max(dp,i+nums[i])
            if i == a:
                return False
            dp = a
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14

参照https://leetcode.cn/problems/jump-game/solution/dong-tai-gui-hua-by-lingyingdong-gbe7/修改的python代码