Leetcode55 & 45 jump game

class Solution {
    // Recursion + memory set
    public boolean canJump(int[] nums) {
        return recur(0,nums,new int[nums.length])==1?true:false;
    }

    public int recur(int n,int[] nums,int[] visited){
        if(n==nums.length-1 || visited[n]==1) return 1;
        if(n<0||n>nums.length-1 || visited[n]==-1) return -1;
        visited[n] = -1;
        for(int i=1; i<=nums[n]; i++){if(recur(n+i,nums,visited)==1) {
                visited[n] = 1;
                return 1; }}return -1;
    }

    // Greedy algorithm
    public boolean canJump(int[] nums) {
        int max=nums[0];
        for(int i=0; i<nums.length; i++){if(i>max) return false;
            if(max>=nums.length-1) return true;
            max = Math.max(max,i+nums[i]);
        }
        return false; }}Copy the code

The difference with the previous Leetcode55 problem is to add a minimum number of jumps, still using greedy algorithm

class Solution {
    public int jump(int[] nums) {
        int endPosision = 0,maxPosition = 0,steps = 0;
        for(int i=0; i<nums.length-1; i++){ maxPosition = Math.max(maxPosition,nums[i]+i);if(i==endPosision){ endPosision = maxPosition; steps++; }}returnsteps; }}Copy the code