55 跳跃游戏

本文最后更新于：2021年2月25日 上午

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

1
2
3
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

1
2
3
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

Solution

参考：《算法小抄》5.7 、**@warlordy**

  • 贪心算法 
1
2
3
4
5
6
7
8
9
10
11
12
# @lc code=start
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        # 最远覆盖距离
        farthest = 0
        for i in range(n-1):
            farthest = max(farthest, i+nums[i])
            if farthest<= i:
                return False
        return farthest >= n-1
# @lc code=end
  • 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# @lc code=start
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        # 动态规划, dp[i] 表示从数组下标 0 出发, 是否可以到达数组下标 i
        dp = [0]*n
        dp[0] = 1
        
        # 状态转移方程, 对于 dp[i], 逆序遍历 [0,i-1] 的每个位置
        for i in range(1,n):
            # 能否从 j 到达 i
            for j in range(i-1, -1, -1):
                if dp[j] and (nums[j]>=i-j):
                    dp[i] = 1
                    break
        return dp[n-1]==1
# @lc code=end

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// @lc code=start
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();

        // dp[i] 表示从数组下标 0 出发, 是否可以到达数组下标 i;
        vector<bool> dp(n, false);
        dp[0] = true;
        for (int i = 1; i < n; ++i) {
            for (int j = i-1; j >= 0; --j) {
                if (dp[j] && (i-j <= nums[j])) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n-1];
    }
};
// @lc code=end
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！