Java 98% Percentile Solution


  • 29

    The easiest way to think about this problem is to ask are the elements with a 0 value avoidable? this is the algorithm that I constructed to answer this question.Starting from the second to last element in the array we continue to decrement towards the start of the array. Only stopping if we hit an element with a value of 0; in this case we evaluate if there exist an element somewhere at the start of the array which has a jump value large enough to jump over this 0 value element.

    public class Solution {
        public boolean canJump(int[] nums) {
           if(nums.length < 2) return true;
           
           for(int curr = nums.length-2; curr>=0;curr--){
               if(nums[curr] == 0){
                   int neededJumps = 1;
                   while(neededJumps > nums[curr]){
                       neededJumps++;
                       curr--;
                       if(curr < 0) return false;
                   }
               }
           }
           return true;
        }
    }

  • 0
    T

    This is really awesome!


  • 1
    M

    That if condition is not needed I guess..


  • 1
    X

    Here is my code, trying to be more concise

    bool Solution::canJump_gap(vector<int>& nums) {
        // when cannot jump from i to i + 1, must find k < i that can jump to i + 1
    
        if (nums.size() <= 1)
            return true;
    
        int need_jumps = 1;
        for (int i = nums.size() - 2; i > 0; --i) {
            if (nums[i] < need_jumps) {
                ++need_jumps;
            } else {
                need_jumps = 1;
            }
        }
        if (nums[0] < need_jumps) {
            return false;
        } else {
            return true;
        }
    
    }
    

    I think it is similar to this solution, where it keeps the numbers of steps left, when going forward.
    However, here we keep the numbers of steps needed, when going backward.


  • 0
    E

    @xsh6528
    public boolean canJump(int[] nums) {
    int last=nums.length-1;
    int res=0;
    for(int i=0;i<last&&res>=i;i++ ){
    int tmp=i+nums[i];
    if(tmp>res) res=tmp;
    if(res>last) return true;
    }
    if(res<last) return false;
    return true;
    }


  • 0
    Z

    @mlblount45
    agree! here is my solution, but ...only 92.73%....sad

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

    for(int i = 0; i<len; i++) {
      if(nums[i]== 0) {
        if(i==0) return false;
        if(i==len-1) return true;
        for(int j = i-1;; j--) {
          if(nums[j]>(i-j)) break;
          if(j==0) return false;
        }
      }
    }
    

    return true;


  • 0
    B

    Great idea
    wrote a python version

    class Solution(object):
        def canJump(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            cur = len(nums)-1
            needed = 0
            while cur>0:
                cur-=1
                if nums[cur]<=needed: needed+=1
                else:needed=0
            return not needed
    

Log in to reply
 

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