1.跳跃游戏

image.png

思路1：

构建boolean数组
遍历nums，遍历到索引i时，
我们对i之前的位置进行遍历，比如存在这样的位置j（0<=j满足boolean数组[j]为true而且j+nums[j]>=i
则说明i位置可以到达，即设置boolean数组[i]=true
遍历nums结束后
我们返回boolean数组的最后一个元素即可，false则不可到达，true则可以到达

  1. public boolean canJump(int[] nums) {
  2.         int n=nums.length;
  3.         boolean[] b=new boolean[n];
  4.         Arrays.fill(b,false);
  5.          if(n==1){//当只有一个元素时，无论如何都会到达
  6.             return true;         
  7.         }else{//当不只一个元素时且第一个元素为0时直接返回false，否则将第一个元素boolean设置为true
  8.             if(nums[0]>0){
  9.                 b[0]=true; 
  10.             }else{
  11.                 return false;
  12.             }
  13.         }
  14.         int j=0;
  15.         for(int i=1;i<n;i++){
  16.             j=i-1;
  17.             while(j>=0){
  18.                 if(nums[j]>=i-j&&b[j]){//核心判断条件
  19.                     b[i]=true;
  20.                     break;
  21.                 }
  22.                 j--;
  23.             }
  24.         }
  25.         return b[n-1];
  26.     }

思路2：

遍历数组nums
维护一个变量max，表示最远到达的位置
如果当前i在max范围内，则将max更新为i+nums[i]和max的最大值
遍历结束后判断max是否大于或等于n-1，n为数组长度
true则可以到达，false则不行

  1. public boolean canJump(int[] nums) {
  2.         int n=nums.length;
  3.         int max=0;
  4.         for(int i=0;i<n;i++){
  5.             if(i<=max){
  6.                 max=Math.max(max,i+nums[i]);
  7.             }
  8.         }
  9.         return max>=n-1;
  10.     }

上面非得全部遍历一遍才return
可以在循环的时候就进行提前return

  1. class Solution {
  2.     public boolean canJump(int[] nums) {
  3.         int n=nums.length;
  4.         int max=0;
  5.         for(int i=0;i<n;i++){
  6.             if(i<=max){
  7.                 max=Math.max(max,i+nums[i]);
  8.                 if(max>=n-1){
  9.                     return true;
  10.                 }
  11.             }
  12.         }
  13.         return false;
  14.     }

疑惑：

为什么思路2是贪心算法？

2.跳跃游戏II

image.png

思路1:

本题有一个假设 ：即给出的用例是一定可以到达数组最后一个位置
这个假设也是官方题解的大前提

遍历nums
更新最远到达距离和边界
我们用最远到达距离来更新边界
即当i等于边界时，
边界=最远到达距离

  1. class Solution {
  2.     public int jump(int[] nums) {
  3.     int end = 0;
  4.     int maxPosition = 0; 
  5.     int steps = 0;
  6.     for(int i = 0; i < nums.length - 1; i++){
  7.         //找能跳的最远的
  8.         maxPosition = Math.max(maxPosition, nums[i] + i); 
  9.         if( i == end){ //遇到边界，就更新边界，并且步数加一
  10.             end = maxPosition;
  11.             steps++;
  12.         }
  13.     }
  14.     return steps;

由于题目的假设，所以我们完全不需要考虑能不能到达最后一个位置
即循环结束后的maxPosition是一定大于或等于n-1
注意这里i在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。(还是基于上面的假设)
比如【1,2】
如果用i<nums.length,则会进入if条件两次，其实只需要一次即可

疑惑：

这道题如果没有该假设，那这样写根本不行
看评论里说华为的类似笔试题只能对50%，我觉得应该是华为没有相关假设

怎么确保过程中的边界可以跳跃到？？
边界就是范围的最大值，并不是是说跳跃的时候一定要正好经过边界
即在这个范围内必须跳一次，至于具体哪个位置就不管了
如果不跳后面无法进行
比如从2开始，第一个边界是0+2，当i遍历到索引2时，最晚这个时候就得跳了，否则后面无法继续；
要是这么理解感觉这道题
image.png