首页 » 编程之美 » 正文

[leetcode_55]Jump Game

从前往后一个一个标记会超时,后来想了下 某些情况下复杂度是o(n^2)
但是从后往前标记,不一样,近似于o(n)

class Solution {
public:
    void FindMin(int A[],int n,bool flag[]) {
        if(n <= 0)return;
        int min = 0xffff;
        for(int i = n-1;i >= 0;i--) {
            if(A[i] + i >= n) {
                flag[i] = true;
                if(min > i)
                    min = i;
            }
        }
        if(min == 0xffff || flag[0] == true)return;
        FindMin(A,min,flag);
    }
    bool canJump(int A[], int n) {
        bool * flag = new bool[n+1];
        if(n == 1)return true;
        for(int i = 0;i < n;i++) {
            flag[i] = false;
        }
        FindMin(A,n-1,flag);
        return flag[0];
    }
};

发表评论