訓練營打卡Day32

文章目錄

• 訓練營打卡Day32
• • 題79：[122. 買賣股票的最佳時機 II](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/)
  • • 思路
    • 代碼
  • 題80：[55. 跳躍遊戲](https://leetcode.cn/problems/jump-game/)
  • • 思路
    • 代碼
  • 題81：[45. 跳躍遊戲 II](https://leetcode.cn/problems/jump-game-ii/)
  • • 思路
    • 代碼

題79：122. 買賣股票的最佳時機 II

思路

• 定義一個變量result來存儲最大收益，初始值為0。
• 使用一個循環周遊所有的股票價格，從第二天開始周遊（因為不可能在第一天就賣出股票）。
• 對于每一天，計算當天賣出股票所能獲得的收益。收益等于當天賣出股票的價格減去前一天買入的價格。
• 如果收益大于0，就将result加上收益；否則，result不變。
• 最後，傳回result

代碼

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

題80：55. 跳躍遊戲

思路

• 定義一個變量cover來存儲能跳到的最遠位置，初始值為0。
• 使用一個循環周遊所有的位置，從第一個位置開始周遊。
• 對于每一個位置，更新cover。新的cover是目前位置加上目前位置的跳力和原來的cover的最大值。
• 如果新的cover大于等于數組的長度減一，就說明能夠跳到最後一個位置，傳回true。
• 如果循環結束，傳回false。

代碼

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

題81：45. 跳躍遊戲 II

思路

• 定義三個變量：curDistance表示目前能跳到的最遠位置，ans表示跳到最後一個位置所需的最少步數，nextDistance表示下一步能跳到的最遠位置，初始值分别為0、0和0。
• 使用一個循環周遊所有的位置，從第一個位置開始周遊，循環條件是目前位置小于數組的長度減一（因為最後一個位置不用跳）。
• 對于每一個位置，更新nextDistance。新的nextDistance是目前位置加上目前位置的跳力和原來的nextDistance的最大值。
• 如果目前位置等于curDistance，就說明已經跳到了能跳到的最遠位置，需要再次跳躍。此時，将curDistance更新為nextDistance，并将ans加一。
• 最後，傳回ans。

代碼

class Solution {
public:
    int jump(vector<int>& nums) {
        int curDistance = 0;
        int ans = 0;
        int nextDistance = 0;
        for(int i = 0; i < nums.size() - 1 ; i++)
        {
            nextDistance = max(nums[i]+i, nextDistance);
            if(i == curDistance)
            {
                curDistance = nextDistance;
                ans++;
            }
        }
        return ans;
    }
};