559 字
3 分钟
45. 跳跃游戏 II
45. 跳跃游戏 II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]i + j < n返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例
示例 1:
输入: nums = [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。示例 2:
输入: nums = [2,3,0,1,4]输出: 2思路
贪心，每次都跳最远，次数就是最少。每次从当前位置开始，统计当前窗口内可以跳到的最远位置。
遍历当前窗口结束后，更新窗口为当前可达最远位置。并且增加跳跃次数。
代码
class Solution {public: int jump(vector<int>& nums) { int ans = 0; int cur = 0; // 当前的可达最远位置 int next = 0; // 记录当前范围内，可达的最远位置 for(int i = 0; i + 1 < nums.size(); i++){ next = max(next, i + nums[i]); // 统计可达最远位置 // 遍历当前可达最远位置结束，更新数据。跳跃。 if(i == cur){ // 可达最远位置，无法超过当前范围，失败。（即无法到达下一个位置） if(cur == next){ return cur; // 返回最远可达位置 } cur = next; ans++; } } return ans; }};动态规划，笨方法
动态规划，笨方法。每次都遍历前面的所有位置，判断是否可以到达当前的位置。
如果可以到达，记录上一个最少次数。遍历结束后，跳跃次数+1。
class Solution {public: int jump(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 0x3f3f3f3f); dp[0] = 0; // 第一个位置为0 for(int i = 1; i < n; i++){ for(int j = 0; j < i; j++){ // 如果num[j]可以直接到达第i个位置 if(nums[j] + j >= i){ // 记录上一个最少次数 dp[i] = min(dp[i] , dp[j]); }
} // 遍历结束，跳跃次数+1 dp[i]++; } return dp[n - 1]; }};