[LeetCode] 55. Jump Game 跳跃游戏

2021年09月15日 阅读数:2
这篇文章主要向大家介绍[LeetCode] 55. Jump Game 跳跃游戏,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Given an array of non-negative integers, you are initially positioned at the first index of the array.html

Each element in the array represents your maximum jump length at that position.java

Determine if you are able to reach the last index.python

Example 1:算法

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:post

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

解法1:DPurl

解法2:贪婪算法Greedyhtm

Java:blog

class Solution {
    public boolean canJump(int[] A) {
        int max = 0;
        for(int i=0;i<A.length;i++){
            if(i>max) {return false;}
            max = Math.max(A[i]+i,max);
        }
        return true;
    }
}  

Python:游戏

class Solution:
    # @param A, a list of integers
    # @return a boolean
    def canJump(self, A):
        reachable = 0
        for i, length in enumerate(A):
            if i > reachable:
                break
            reachable = max(reachable, i + length)
        return reachable >= len(A) - 1

C++: Backtrackelement

class Solution {
public:
    bool canJump(int A[], int n) {
        int last=n-1,i,j;
        for(i=n-2;i>=0;i--){
            if(i+A[i]>=last)last=i;
        }
        return last<=0;
    }
};

C++: DP

class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        for (int i = 1; i < nums.size(); ++i) {
            dp[i] = max(dp[i - 1], nums[i - 1]) - 1;
            if (dp[i] < 0) return false;
        }
        return dp.back() >= 0;
    }
};

C++: Greedy

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size(), reach = 0;
        for (int i = 0; i < n; ++i) {
            if (i > reach || reach >= n - 1) break;
            reach = max(reach, i + nums[i]);
        }
        return reach >= n - 1;
    }
};

    

相似题目:

[LeetCode] 45. Jump Game II 跳跃游戏 II 

 

All LeetCode Questions List 题目汇总