如何运用贪心思想玩跳跃游戏 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：如何运用贪心思想玩跳跃游戏

评论礼仪 见这里，违者直接拉黑。

[lingshaofu]

跳跃游戏 I 有瑕疵吧，【2，0，0】这个用例有问题

[chenggiant]

[Jump Game II]用BFS来解也是不错

[labuladong]

测试了一下，直接复制我的代码都可以通过的，可能是你们写错了

[deepbreath373]

文中i是0 ~ n-1，精妙精妙！

[taoziganbei]

贪心策略：每次在能到达的所有位置中，选择下一步跳跃能到达的最远位置

[zhongweiLeex]

1. 提示：

提示 ：本题中 i 一直在是逐步往前的哦， 不是 一下子更新到最远位置的， 可以想象成 i 一直在追逐 farest 这个最远索引。

2. 使用dp数组的动态规划方法

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        //dp[i] 表示从0 跳到 i 坐标 至少需要多少步
        //最终需要求 dp[n-1] 即 从 0 跳到 n-1 至少需要多少步
        int[] dp = new int[n];
        //base case
        for(int i = 1; i< n;i++){
            dp[i]=n;
        }
        dp[0] = 0;
        for(int i = 1; i<n;i++){
            for(int j = 0;j<i;j++){
                if(j+nums[j]>= i){//如果当前所在位置的index  + 其最远能跳的距离超过了 想要跳到的坐标i则可以更新 dp[i]
                    dp[i] = Math.min(dp[i],1+dp[j]);
                }
            }
        }
        return dp[n-1];
    }
}

[Alwin4Zhang]

45. 跳跃游戏 II python versions

dp动态规划 勉强通过，没有超时

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        # dp[i]表示从开头0位置到当前i的最小步数
        for i in range(1, n):
            sub_problems = []
            for j in range(0, i):
                if i - j > nums[j]:  # 有一个数组比较长的case不用这个会超时
                    continue
                # if i - j <= nums[j]:
                sub_problems.append(dp[j] + 1)
            dp[i] = min(sub_problems)
        return dp[-1]

[861130245]

贴波自己写的贪心

int jump(vector<int>& nums) {
        int index = 0, res = 0, n = nums.size();

        // 当前位置不是最后一个时
        while (index < n - 1) {
            // 当前位置能一次跳到最后一个则返回
            if (index + nums[index] >= n - 1) {
                return res + 1;
            } else {
                // 选在自己能跳到的范围中, 选下一次能跳最远的
                int mostFar = index + 2;
                int nextIndex = index + 1;
                for (int i = 1; i <= nums[index]; i++) {
                    if (mostFar < index + i + nums[index + i]) {
                        mostFar = index + i + nums[index + i];
                        nextIndex = index + i;
                    }
                }
                index = nextIndex;
                res++;
            }
        }
        return res;
    }

[lzh2580]

i < n-1 充分利用了题目的条件，假设能到最后。真特么我还特意加了一个end == n-1的判断，画蛇添足

[cheng-miao]

daka

[Maxiah]

讲的真的很明白，举一反三

[Plasticine-Yang]

跳跃游戏Ⅱ TypeScript贪心解法

/**
 * @description 贪心选择
 */
function jump(nums: number[]): number {
  const n = nums.length;
  // 当前可跳跃范围的终点
  let end = 0,
    // 总共的跳跃次数
    jumps = 0,
    // 可到达的最远地方
    farthest = 0;

  // 遍历所有选择
  for (let i = 0; i < n - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);

    // 当前的可跳跃范围遍历结束 进入下一个可跳跃范围
    if (i === end) {
      // 每遍历完一个可跳跃范围就相当于做了一次决策
      // 总跳跃次数增加一次
      jumps++;
      // 更新下一次可跳跃范围的终点
      end = farthest;
    }
  }

  return jumps;
}

[dreamyang-liu]

这个每次end 感觉有些像二叉树层序遍历中每层开始时 获取当前queue的size，都是用来圈定处理范围

[deepbreath373]

check in

[zhongweiLeex]

改了遍历终点 添加了注释 ， 可能更好理解一点

class Solution {
    public int jump(int[] nums) {
        int len = nums.length;
        if(len == 1) return 0;
        int curEnd = 0;
        int nextEnd = 0;
        int step = 0;
        for(int i = 0; i< len ; i++){
           // 下次能到的最大位置
            nextEnd = Math.max(nextEnd, nums[i] + i);
            if(nextEnd >= len-1){
                return step+1;
            }
            //到达预估最大位置， 则跳到下一个位置
            if(i == curEnd){
                step++;
                curEnd = nextEnd;
            }
        }
        return step;
    }
}

[Tiamow123]

to1楼，测试用例[2,0,0]无法通过，应该是索引边界问题，上界是小于n-1，而不是小于n。

[czhongwe]

我现在看啥都是树....

public boolean canJump(int[] nums, int curIndex) {
        if (nums[curIndex] == 0 && curIndex < nums.length - 1) {
            return false;
        } else if (nums[curIndex] >= nums.length - 1 - curIndex) {
            return true;
        }
        int num = nums[curIndex];
        boolean flag = Boolean.FALSE;
        for (int i = 1; i <= num; i++) {
            flag = flag || canJump(nums, curIndex + i);
        }
        return flag;
    }