01.跳躍游戲 II

題目鏈接：https://leetcode.cn/problems/jump-game-ii/

給定一個(gè)長度為 n 的 0 索引整數(shù)數(shù)組 nums。初始位置為 nums[0]。

每個(gè)元素 nums[i] 表示從索引 i 向前跳轉(zhuǎn)的最大長度。換句話說，如果你在 nums[i] 處，你可以跳轉(zhuǎn)到任意 nums[i + j] 處:

• 0 <= j <= nums[i]
• i + j < n

返回到達(dá) nums[n - 1] 的最小跳躍次數(shù)。生成的測試用例可以到達(dá) nums[n - 1]。

示例 1:

輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個(gè)位置的最小跳躍數(shù)是 2。
     從下標(biāo)為 0 跳到下標(biāo)為 1 的位置，跳 1 步，然后跳 3 步到達(dá)數(shù)組的最后一個(gè)位置。

示例 2:

輸入: nums = [2,3,0,1,4]
輸出: 2

提示:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000
• 題目保證可以到達(dá) nums[n-1]

思路

這里我們可以利用層序遍歷的思想進(jìn)行數(shù)組遍歷，從第一步開始，計(jì)算每一步能跨出的范圍內(nèi)最大的那個(gè)數(shù)字的步數(shù)，這樣我們就可以找到需要使用的最小的跳躍步數(shù)。

代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-847194.html

class Solution {
public:
    int jump(vector<int>& nums) {
        int left=0,right=0,maxPos=0,count=0,n=nums.size();
        while(left<=right){
            if(maxPos>=n-1) return count;
            for(int i=left;i<=right;i++) maxPos=max(maxPos,nums[i]+i);
            left=right+1;
            right=maxPos;
            count++;
        }
        return -1;
    }
};

02.跳躍游戲

題目鏈接：https://leetcode.cn/problems/jump-game/

給你一個(gè)非負(fù)整數(shù)數(shù)組 nums ，你最初位于數(shù)組的 第一個(gè)下標(biāo) 。數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達(dá)最后一個(gè)下標(biāo)，如果可以，返回 true ；否則，返回 false 。

示例 1：

輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標(biāo) 0 到達(dá)下標(biāo) 1, 然后再從下標(biāo) 1 跳 3 步到達(dá)最后一個(gè)下標(biāo)。

示例 2：

輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣，總會(huì)到達(dá)下標(biāo)為 3 的位置。但該下標(biāo)的最大跳躍長度是 0 ， 所以永遠(yuǎn)不可能到達(dá)最后一個(gè)下標(biāo)。

提示：

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

思路

這道題可以借用上面的思想，只需修改返回值即可。

代碼

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int left=0,right=0,maxPos=0,count=0,n=nums.size();
        while(left<=right){
            if(maxPos>=n-1) return true;
            for(int i=left;i<=right;i++) maxPos=max(maxPos,nums[i]+i);
            left=right+1;
            right=maxPos;
            count++;
        }
        return false;
    }
};

03.加油站

題目鏈接：https://leetcode.cn/problems/gas-station/

在一條環(huán)路上有 n 個(gè)加油站，其中第 i 個(gè)加油站有汽油 gas[i] 升。

你有一輛油箱容量無限的的汽車，從第 i 個(gè)加油站開往第 i+1 個(gè)加油站需要消耗汽油 cost[i] 升。你從其中的一個(gè)加油站出發(fā)，開始時(shí)油箱為空。

給定兩個(gè)整數(shù)數(shù)組 gas 和 cost ，如果你可以按順序繞環(huán)路行駛一周，則返回出發(fā)時(shí)加油站的編號(hào)，否則返回 -1 。如果存在解，則 保證 它是 唯一 的。

示例 1:

輸入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
輸出: 3
解釋:
從 3 號(hào)加油站(索引為 3 處)出發(fā)，可獲得 4 升汽油。此時(shí)油箱有 = 0 + 4 = 4 升汽油
開往 4 號(hào)加油站，此時(shí)油箱有 4 - 1 + 5 = 8 升汽油
開往 0 號(hào)加油站，此時(shí)油箱有 8 - 2 + 1 = 7 升汽油
開往 1 號(hào)加油站，此時(shí)油箱有 7 - 3 + 2 = 6 升汽油
開往 2 號(hào)加油站，此時(shí)油箱有 6 - 4 + 3 = 5 升汽油
開往 3 號(hào)加油站，你需要消耗 5 升汽油，正好足夠你返回到 3 號(hào)加油站。
因此，3 可為起始索引。

示例 2:

輸入: gas = [2,3,4], cost = [3,4,3]
輸出: -1
解釋:
你不能從 0 號(hào)或 1 號(hào)加油站出發(fā)，因?yàn)闆]有足夠的汽油可以讓你行駛到下一個(gè)加油站。
我們從 2 號(hào)加油站出發(fā)，可以獲得 4 升汽油。 此時(shí)油箱有 = 0 + 4 = 4 升汽油
開往 0 號(hào)加油站，此時(shí)油箱有 4 - 3 + 2 = 3 升汽油
開往 1 號(hào)加油站，此時(shí)油箱有 3 - 3 + 3 = 3 升汽油
你無法返回 2 號(hào)加油站，因?yàn)榉党绦枰?4 升汽油，但是你的油箱只有 3 升汽油。
因此，無論怎樣，你都不可能繞環(huán)路行駛一周。

提示:

• gas.length == n
• cost.length == n
• 1 <= n <= 105
• 0 <= gas[i], cost[i] <= 104

思路

枚舉所有起點(diǎn)，模擬加油的流程，但在這里做一個(gè)優(yōu)化，就是貪心思想，我們?cè)诿杜e每一個(gè)點(diǎn)時(shí)，若該點(diǎn)不成功，就直接跳過中間所有點(diǎn)，這樣我們可以做很大的優(yōu)化。

代碼

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n=gas.size();
        for(int i=0;i<n;i++){
            int rest = 0, step = 0;
            while(step<n){
                int  index=(i+step)%n;
                rest+=gas[index]-cost[index];
                if(rest<0) break;
                step++;
            }
            if(rest>=0) return i;
            i+=step;
        }
        return -1;
    }
};

04.單調(diào)遞增的數(shù)字

題目鏈接：https://leetcode.cn/problems/monotone-increasing-digits/

當(dāng)且僅當(dāng)每個(gè)相鄰位數(shù)上的數(shù)字 x 和 y 滿足 x <= y 時(shí)，我們稱這個(gè)整數(shù)是單調(diào)遞增的。

給定一個(gè)整數(shù) n ，返回 小于或等于 n 的最大數(shù)字，且數(shù)字呈 單調(diào)遞增 。

示例 1:

輸入: n = 10
輸出: 9

示例 2:

輸入: n = 1234
輸出: 1234

示例 3:

輸入: n = 332
輸出: 299

提示:

• 0 <= n <= 109

思路

為了方便處理數(shù)字，我們可以先將整數(shù)轉(zhuǎn)換成字符串，然后從左往右掃描，找到第一個(gè)遞減的位置，然后從這個(gè)位置往前推，推到相同數(shù)字的最前端，該位置-1，后面所有數(shù)都改成9，這樣就得到最終結(jié)果

代碼

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string s=to_string(n);

        int i=0,m=s.size();
        while(i+1<m&&s[i]<=s[i+1]) i++;

        if(i+1==m) return n;

        while(i-1>=0&&s[i]==s[i-1]) i--;

        s[i]--;
        for(int j=i+1;j<m;j++) s[j]='9';
        return stoi(s);
    }
};

到了這里，關(guān)于算法沉淀——貪心算法五（leetcode真題剖析）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！