Simple Java BFS solution with greedy


  • 0
    D
    SOLUTION!
    
    public class Solution {
        public int jump(int[] nums) {
            if(nums.length<2) return 0;
            int level=0;        //count the level            
            int curmax=0;       //help the cur
            int nextmax=0;      //record the value of curmax for further use
            int cur=0;          //working point of code
            while(nextmax>=cur){  //how many numbers of point in this level ,then whether it can reach this level
                level++;
                for(;cur<=nextmax;cur++){                   //loop to this level, to get the max number of next level
                    curmax=Math.max(curmax,nums[cur]+cur);  
                    if(curmax>=nums.length-1) return level; //decide whether reach end
                }
                nextmax=curmax;
            }
            return 0;           //return 0 if can't reach end
        }
    }
    
    SOLUTION2
    
    public class Solution {
        public int jump(int[] nums) {
            int level=0;        //count the level            
            int max=0;    
            int end=0;          
            for(int i=0;i<nums.length-1;i++){
                max=Math.max(max,nums[i]+i);  
                if(i==end){
                    level++;
                    end=max;
                }
            }
            return level;
        }
    }

Log in to reply
 

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