My greedy solution (c++)


  • 0
    F
    int jump(vector<int>& nums) {
    	if (nums.size() == 1) return 0;
    	int res = 1;
    	int l = 0, r = nums[0];
    	int maxL = r;
    	while(maxL < nums.size() - 1){
    		int newL = -1;
    		for(int i = l; i <=r; i++){
    			if (i + nums[i] > maxL){
    				maxL = i + nums[i];
    				newL = i;
    				if (maxL >= (nums.size()-1)){return res + 1;}  //will reach in next step
    			}
    		}
    		l = newL;
    		r = maxL;
    		res++; //ready for next step
    	}
    	return res;
    }

Log in to reply
 

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