55. 跳躍游戲

力扣題目鏈接(opens new window)

給定一個(gè)非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個(gè)位置。

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

判斷你是否能夠到達(dá)最后一個(gè)位置。

示例 ?1:

• 輸入: [2,3,1,1,4]
• 輸出: true
• 解釋: 我們可以先跳 1 步，從位置 0 到達(dá) 位置 1, 然后再從位置 1 跳 3 步到達(dá)最后一個(gè)位置。

示例 ?2:

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

代碼如下：

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

45.跳躍游戲 II

力扣題目鏈接(opens new window)

給定一個(gè)非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個(gè)位置。

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

你的目標(biāo)是使用最少的跳躍次數(shù)到達(dá)數(shù)組的最后一個(gè)位置。

示例:

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

說明: 假設(shè)你總是可以到達(dá)數(shù)組的最后一個(gè)位置。

代碼如下：

class  Solution {
public:
    int jump(vector<int>& num) {
        if (num.size() == 1) return 0;
        int curdistance = 0;//記錄當(dāng)前距離最遠(yuǎn)下標(biāo)
        int ans = 0;//記錄走的最大步數(shù)
        int nextdistance = 0;//記錄下一個(gè)距離的最遠(yuǎn)下標(biāo)號(hào)
        for (int i = 0; i < num.size(); i++) {
           
                nextdistance = max(i + num[i], nextdistance);// 更新下一步覆蓋最遠(yuǎn)距離下標(biāo)
                if (i == curdistance) {                                      // 遇到當(dāng)前覆蓋最遠(yuǎn)距離下標(biāo)
                    ans++;                                                          // 需要走下一步
                    curdistance = nextdistance;
                    if (curdistance >= num.size() - 1) {
                        break;
                    }// 當(dāng)前覆蓋最遠(yuǎn)距到達(dá)集合終點(diǎn)，不用做ans++操作了，直接結(jié)束
                }
            }
           return ans;
        }
};

122.買賣股票的最佳時(shí)機(jī) II

力扣題目鏈接(opens new window)

給定一個(gè)數(shù)組，它的第 ?i 個(gè)元素是一支給定股票第 i 天的價(jià)格。

設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1:

• 輸入: [7,1,5,3,6,4]
• 輸出: 7
• 解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤 = 5-1 = 4。隨后，在第 4 天（股票價(jià)格 = 3）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。

示例 2:

• 輸入: [1,2,3,4,5]
• 輸出: 4
• 解釋: 在第 1 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出。因?yàn)檫@樣屬于同時(shí)參與了多筆交易，你必須在再次購買前出售掉之前的股票。

示例 ?3:

• 輸入: [7,6,4,3,1]
• 輸出: 0
• 解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。

提示：

• 1 <= prices.length <= 3 * 10 ^ 4
• 0 <= prices[i] <= 10 ^ 4

代碼如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result = 0;
        for (int i = 1; i < prices.size(); i++) {
            result += max(prices[i] - prices[i - 1], 0);
        }
        return result;
    }
};

?文章來源地址http://www.zghlxwxcb.cn/news/detail-609388.html

到了這里，關(guān)于代碼隨想錄 第三十二天 45.跳躍游戲 II||122.買賣股票的最佳時(shí)機(jī) II55. 跳躍游戲的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！