My Simple C++ code (with explaination )


  • 0
    J

    It is a simple greedy algorithm. Define d[i] which means somewhere j ( j>=0&&j< i )

    can reach i when it is true.

    Steps:

    1. Initial d[0]=true.
    2. do a loop from 0 to n-1 to update d[i] (i>=0&&i<=n-1) when d[i] is true because when you update d[j] (j>i) you have to make sure location i can be reached.
    3. return d[n-1];
    
    
        class Solution {
            public:
            bool canJump(vector<int>& nums) {
                int i,j;
                int n=nums.size();
                vector<bool> d(n,0);
                d[0]=true;
                for(i=0;i<n-1;i++)
                {
                    if(d[i])
                    {
                        if(i+nums[i]>=n-1)return true;
                        if(i==0)for(j=i;j<=i+nums[i];j++)d[j]=true;
                        else for(j=i-1+nums[i-1];j<=i+nums[i];j++)d[j]=true;
                    }
                }
                return d[n-1];
            }
        };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.