Probably the simplest O(n) C++ solution for Jump Game.


  • 1
    A

    The method is a backward search.

    During the search, mark the possible jump stand which is closest to the current searching point among those found ones. If the closest stand is reachable from the current searching point, then the current point is another possible stand, v.v.

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

Log in to reply
 

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