LeetCode--55--medium--JumpGame

package com.app.main.LeetCode;

/**
 * 55
 *
 * medium
 *
 * https://leetcode.com/problems/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.
 *
 * Example 1:
 *
 * Input: [2,3,1,1,4]
 * Output: true
 * Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
 *
 *
 * Example 2:
 *
 * Input: [3,2,1,0,4]
 * Output: false
 * Explanation: You will always arrive at index 3 no matter what. Its maximum
 *              jump length is 0, which makes it impossible to reach the last index.
 *
 *
 * Created with IDEA
 * author:Dingsheng Huang
 * Date:2019/10/22
 * Time:下午5:07
 */
public class JumpGame {

    public boolean canJump(int[] nums) {

        return backtrack(nums, 0);
    }

    private boolean backtrack(int[] nums, int currIndex) {

        if (currIndex == nums.length - 1) {
            return true;
        }

        if (currIndex > nums.length - 1) {
            return false;
        }

        if (nums[currIndex] == 0) {
            return false;
        }
        for (int i = nums[currIndex]; i > 0; i--) {

            if (backtrack(nums, currIndex + i)) {
                return true;
            }

        }

        return false;

    }

    // [2,3,1,1,4]
    public boolean canJump2(int[] nums) {

        if (nums.length <= 1) {
            return true;
        }

        int target = nums.length - 1;
        int start = target - 1;
        while (start >= 0) {
            if (canAccess(target, start, nums)) {
                if (start == 0) {
                    return true;
                }
                target = start;
                start--;
            } else {
                start--;
            }
        }
        return false;
    }

    private boolean canAccess(int target, int start, int[] nums) {
        if (nums[start] >= (target - start)) {
            return true;
        }
        return false;
    }
}