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

By | 2012 年 9 月 29 日

最开始用

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];
    }
};

11 thoughts on “LeetCode题目:Jump Game,一维动态规划

    1. uniEagle Post author

      这里的用法具体问题是什么呢?
      初始化size为n,初值false
      后面的过程都是在修改或读取其中某项的值。

      Reply
    1. uniEagle Post author

      这个题贪心法就能解。题意是指,从i出发,最长能跳A[i]步,也就是说,从i到i + A[i] – 1,都能到达。而不是只能到i+A[i]-1这个位置。

      Reply
      1. traveller
        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;
            }
        };
        
        Reply

发表评论

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