LeetCode 45 跳跃游戏||

1.递归+贪心算法

class Solution { public int jump(int[] nums) { if(nums.length==1) return 0; return cJ(nums,0,0); } public int cJ(int[] nums,int begin,int count){ if(begin+nums[begin]>=nums.length-1) return count+1; int max=0,pos=begin; for(int i=begin+1;i<nums.length&&i<=begin+nums[begin];i++){ if(nums[i]+i>max){ max=nums[i]+i; pos=i; } } if(pos==begin){ return count; }else if(pos==nums.length-1){ return count+1; }else{ return cJ(nums,pos,count+1); } } }

如果55 跳跃游戏用的这种做法，只需要做一下小改动，就可以直接用了，就是这个判断条件需要好好看仔细

为了测试例子[0]  if(nums.length==1) return 0;

下面的是改进了一下判断条件

class Solution { public int jump(int[] nums) { if(nums.length==1) return 0; return cJ(nums,0,0); } public int cJ(int[] nums,int begin,int count){ if(begin+nums[begin]>=nums.length-1) return count+1; int max=0,pos=begin; for(int i=begin+1;i<nums.length&&i<=begin+nums[begin];i++){ if(nums[i]+i>max){ max=nums[i]+i; pos=i; } } return cJ(nums,pos,count+1); } }

 

 2.题解

class Solution { public int jump(int[] nums) { int max=0,pos=0,count=0; for(int i=0;i<nums.length-1;i++){ max=Math.max(max,nums[i]+i); if(i==pos){ pos=max; count++; } } return count; } }

这个题解吧，

1.i<nums.length-1  这个地方我才开始是没太懂的，感觉它限制住了测试例子[0]，那对其他的呢，其实i本来也不用走到最后位置，这个count++,是在这个位置能往下跳，就++，而不是已经跳过了，再++，所以i不需要循环到最后位置之前

2.题解这种遍历的方法，是这么个意思，举例 2 3 1 1 4

第一次跳到i=2 nums[i]=1  也就是让pos=2，

之后在遍历是不是在0~2，找出max，如果在nums[i]=3能跳的位置比nums[i]=1跳的位置远，就跳到nums[i]=3能跳的位置，从次数上来说，是没有影响的，下面这个图大概表示了我的意思，那和从2-->1-->6次数不是一样么？