lc贪心问题：55 && 45

• 55.跳跃游戏
• • 思路分析
  • 代码
• 45.跳跃游戏||
• • 思路分析
  • 代码

55.跳跃游戏

链接直达

思路分析

• 思路清晰：我们可以在任何一个点停下，所以将这个点+这个点的num[i]，也就是表示这个点是否可以达到数组最后一个元素
• 只要两者之和大于等于数组最后一个元素下标就算成功

代码

class Solution {    public boolean canJump(int[] nums) { if(nums.length == 1) return true; int distance = 0; for(int i = 0; i <= distance; i++){     distance = Math.max(distance, i + nums[i]);     if(distance >= nums.length - 1){  return true;     } } return false;    }}

45.跳跃游戏||

链接直达

思路分析

• ||肯定是要难一点的。
• 错误分析：思考循环，考虑到【2，3，1，1，4】中下标为0的2，可以跳一步，也可以跳两步。其他点也是如此，瞬间想到了回溯。for-back开始一顿狂写。。。
• 思考与上题的关联，我们依旧是可能在任意点停下，i+nums[i]是肯定需要的，只要这个值大于数组下标长度，那么这条跳跃的路线一定是成立的，所以我们只需要找到使用跳跃次数最短的这种路线。
• 维护一个count表示次数，贪心，在迫到不得已的情况下，我们才选择跳一下~~~
• 什么情况下是迫不得已，当前所在的跳跃范围已经到了极限了，我们就需要跳一下了！

代码

class Solution {    public int jump(int[] nums) {if(nums.length == 0 || nums.length == 1 || nums == null){     return 0; } int count = 0;//走的步数 int curdistance = 0;//当前跳跃范围 int maxdistance = 0;//最大跳跃范围 for(int i = 0; i < nums.length; i++){     //更新最大跳跃范围     maxdistance = Math.max(maxdistance, i + nums[i]);     if(maxdistance >= nums.length - 1){  //此时表示加上当前的num[i]可以跳到末尾乐，需要count++，更新count  count++;  break;     }     if(i == curdistance){  //表示即将超出当前的跳跃范围，那么就count++，扩大范围  count++;  curdistance = maxdistance;     } } return count;    }}