跳跃游戏 II

题目链接

跳跃游戏 II

题目描述

注意点

• 题目保证可以到达 nums[n - 1]

解答思路

• 可以从后往前推出那些位置可以跳到目标点（最初是到终点），但是可能会有多个位置都能跳到目标点，此时可以贪心地取目标点最远的点作为新的目标点（一定保证步数最少），以此类推直到起点为止

代码

class Solution {
   
    public int jump(int[] nums) {
   
        int step = 0;
        int loc = nums.length - 1;
        while (loc > 0) {
   
            for (int i = 0; i < loc; i++) {
   
                if (i + nums[i] >= loc) {
   
                    loc = i;
                    step++;
                }
            }
        }
        return step;
    }
}

关键点

• 反向查找出发位置
• 贪心算法找到最小跳跃数