Java Greedy Solution


  • 0
    P

    贪婪算法:在每次跳的时候,选择再下一跳时能跳的更远的。
    Greedy Algorithm: Every time when you want to jump, please jump to the place that can let you jump further next time. Why not?

    public class Solution {
        public boolean canJump(int[] nums) {
            int i = 0;
            while(i<nums.length)
            {
                if(nums[i] == 0&&i!=nums.length-1)
                {
                    return false;
                }
                int max = Integer.MIN_VALUE;
                int next = i+1;
                for(int j = 1;j<nums[i]+1;j++)
                {
                    if(i+j>nums.length-1)
                    {
                        return true;
                    }
                    if(nums[i+j]+j-1>max)
                    {
                        max = nums[i+j]+j-1;
                        next = i+j;
                    }
                }
                i = next;
            }
            return true;
        }
    }
    

Log in to reply
 

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