分类
C++ Develop 算法

LeetCode题目:Jump Game,一维动态规划

最开始用

vector

超时,想了想没法改进算法的阶,就把这个换成bool[],居然就过了。。。哎,该用数组还是用数组啊。



题目描述:Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.



大集合不超时了,不过貌似有一个testcase有问题,错误一个:[2,0,1,1,1,1],这应该返回true啊,不过系统给的答案是false

class Solution {
public:
    bool canJump(int A[], int n) {
        //if (n > 100) return false;
        if (n <= 1)
            return true;
        //vector canJump(n, false);
        bool *canJump = new bool[n];
        canJump[n - 1] = true;
        for( int i = n - 2; i >= 0; --i ) {
            int maxJump = A[i];
            for(int j = i + 1; j <= i + maxJump && j < n ; ++j) {
                if (canJump[j]) {
                    canJump[i] = true;
                    break;
                }
            }
        }
        return canJump[0];
    }
};



大集合超时

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

“LeetCode题目:Jump Game,一维动态规划”上的11条回复

class Solution {
public:
    bool canJump(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        for(int i=n-2;i>=0;i--){
            if(A[i]==0){
                int j=i-1;
                for(;j>=0;j--){
                    if((j+A[j])>i)
                        break;
                }
                if(j<0)return false;
            }
        }
        return true;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注