Jump Game II leetcode

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.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

state:f[i] 表示从0到i点最少要跳几部

function： f[i] = f[j] +1 // j< i   j + a[j] >= i 取最小的j

initial：f[0] = 0

return f[a.length-1]
时间O(n^2) 空间O(n)

public class Solution {
    public int jump(int[] A) {
        int[] count = new int[A.length];
        count[0] = 0;
        for (int i = 1; i < A.length; i++) {
            count[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (count[j] != Integer.MAX_VALUE && A[j] + j >= i) {
                    count[i] = count[j] + 1;
                    break;
                }
            }
        }
        return count[A.length - 1];
    }
}

如果要输出所有解（从0点jump到i点的路径）

public class Solution {
    public int jump(int[] A) {
        int[] count = new int[A.length];
        int[] pre = new int[A.length];
        count[0] = 0;
        for (int i = 1; i < A.length; i++) {
            count[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (count[j] != Integer.MAX_VALUE && A[j] + j >= i) {
                    count[i] = count[j] + 1;
                    pre[i] = j;//记录到达i点的前一点j
                    break;
                }
            }
        }
        i = A.length - 1;
        while(i != 0) {
            path.add(i);//把i的值加入结果里
            i = pre[i];//i的值编程i前一点的值
        }
        path.add(0);
        path.reverse;//因为是倒着加的所以要reverse
        return path;
    }
}

greedy解法 在位置i可以跳的最远距离为nums[i] + i , 每次跳完更新max = max(max, num[i] + i)
时间O(n) 空间 O(1)

public class Solution {
    public int jump(int[] nums) {
        int max = 0;
        int lastmax = 0;
        int step = 0;
        for (int i = 0; i <= max && i < nums.length; i++) {
            if (i > lastmax) {//在第0位置 如果i大于0的话就至少走一步, 更新lastmax为0位置走一步最远能到的位置
                lastmax = max;
                step++;
            }
            max = Math.max(max, nums[i] + i);
        }
        if (max < nums.length - 1) {
            return 0;
        }
        return step;
    }
}

Jump game leetcode

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.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

state: f[i]表示能否从起点跳到i点

function： f[i] = 是否能从前面任意j点跳到i点

initial： f[0] = true

final : return f[n-1]

  时间O(n^2) 空间O(n)

public class Solution {
    
    public boolean canJump(int[] A) {
        boolean [] can = new boolean [A.length];// 每次都要创建长度为length的数组
        can[0] = true;
        for (int i = 1; i < A.length; i++) {//i的起始点应该为1
            for (int j = 0; j < i; j++) {
                if (can[j] && j + A[j] >= i) {
                    can[i] = true;
                    break;
                }
            }
        }
        return can[A.length - 1];
    }
}

贪心:
起始便利啊范围是0 ~ nums[0] 随着便利进行 范围会变为max的值  但是要小于nums长度
在位置i可以跳的最远距离为nums[i] + i , 维护一个max 记录能跳的最远距离
每次跳完更新max = max(max, num[i] + i)
时间是O(n) 空间O(1)

public class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length <= 1) {
            return true;
        }
        int max = 0;
        for (int i = 0; i <= max && i < nums.length; i++) {
            max = Math.max(max, nums[i] + i);
            if (max >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}