55. Jump Game

# Medium

From end to beginning of the list to record True status. Two pointer: start, end. start move from previous of end until the element of the list can reach end, record True or False status until start out of index.

Solution:

1. Initilize all variables. end = len(nums)-1, start = len(nums)-2, flag = True (because current status is: from last element to last element, it must be True)

2. Two pointer: start and end move. If distance(end-start) <= nums[start], end jumps to start, start move to pre-element, set flat=True

3. Using while loop to control the index of start until out of index.

4. return result=flag

Python

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        l = len(nums)
        end = l-1    # last True index in nums
        start = l-2 # index of start in nums, from start to end to see if possible
        flag = True # current status, List[l-1] -> List[l-1]
        
        while start >= 0:
            if nums[start] >= end - start: # 需要的步数是否能够到达end
                end = start
                flag = True
            else:
                flag = False
            start = start-1
        
        return flag

Java(笨DP)

class Solution {
    public boolean canJump(int[] nums) {
        boolean[] canReach = new boolean[nums.length];
        Arrays.fill(canReach, false);
        canReach[0] = true;
        
        for(int i = 0; i < nums.length; i ++) {
            if(!canReach[i])
                continue;
            for(int x = 1; x <= nums[i] && i+x < nums.length; x ++) {
                canReach[i+x] = true;
                if(i+x == nums.length - 1)
                    return true;                      
            }
        }
        
        return canReach[nums.length - 1];
    }
}

Java(O(n))

class Solution {
    public boolean canJump(int[] nums) {
        int lastPosi = nums.length - 1;
        for(int i = nums.length - 1; i >= 0; i --) {
            if(i + nums[i] >= lastPosi)
                lastPosi = i;
        }
        return lastPosi == 0;
    }
}