Leetcode刷題筆記 45. 跳躍遊戲 II

45. 跳躍遊戲 II

時間：2020年12月3日

知識點：貪心

題目連結：https://leetcode-cn.com/problems/jump-game-ii/

題目

給定一個非負整數數組，你最初位于數組的第一個位置。

數組中的每個元素代表你在該位置可以跳躍的最大長度。

你的目标是使用最少的跳躍次數到達數組的最後一個位置。

示例:

輸入: [2,3,1,1,4]

輸出: 2

解釋: 跳到最後一個位置的最小跳躍數是 2。

從下标為 0 跳到下标為 1 的位置，跳 1 步，然後跳 3 步到達數組的最後一個位置。

說明:

假設你總是可以到達數組的最後一個位置。

解法：

1. 看起來是一道動态規劃的題，實際上是貪心
2. 這裡要搞明白 什麼時候需要步數+1 這裡維護兩個數
3. 第一個是在目前情況下 能走到的最大距離
4. 第二個是 下一步能走到的最大距離
5. 首先看第一個數 目前能走到最大的距離為0 下一步能走的距離範圍在[0,i+nums[i]]
6. 必須走這一步 ans++ 更新目前能走距離為[0,i+nums[i]] 如果目前能走到的距離 > 最後一個 就傳回
7. 否則 繼續走 在目前能走的距離中 更新下一步能走的最大值 确定在[0,i+nums[i]] 到底選哪個地方走 該題不需要 能走到就行
8. 重點： 每次走到目前能走的距離末尾 需要更新最大能走的地方
9. 注意末尾的判斷

代碼

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int jump(vector<int>& nums) {
        int end = nums.size()-1;
        int cur_max_idx = 0;
        int next_max_idx = 0;
        int ans = 0;
        for(int i = 0; i < nums.size(); i++){
            next_max_idx = max(i+nums[i],next_max_idx);
            if(cur_max_idx >= end)
                break;
            if(i == cur_max_idx){
                ans ++;
                cur_max_idx = next_max_idx;
            }
        }
        return ans;
    }
};
int main()
{
    vector<int> nums{2,3,1,1,4};
    Solution s;
    cout<<s.jump(nums)<<endl;
    return 0;
}

           

今天也是愛zz的一天哦！