第十課 貪心

lc 322.零錢兌換–中等

題目描述

給你一個整數(shù)數(shù)組 coins ，表示不同面額的硬幣；以及一個整數(shù) amount ，表示總金額。

計算并返回可以湊成總金額所需的 最少的硬幣個數(shù) 。如果沒有任何一種硬幣組合能組成總金額，返回 -1 。

你可以認為每種硬幣的數(shù)量是無限的。

示例 1：

輸入：coins = [1, 2, 5], amount = 11
輸出：3 
解釋：11 = 5 + 5 + 1

示例 2：

輸入：coins = [2], amount = 3
輸出：-1

示例 3：

輸入：coins = [1], amount = 0
輸出：0

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

代碼展示

class Solution {public int coinChange(int[] coins, int amount) {int INF = (int)1e9; // 定義一個無窮大的值，用于初始化 dp 數(shù)組int[] opt = new int[amount + 1]; // 創(chuàng)建一個 dp 數(shù)組，用于存儲湊成各個金額所需的最小硬幣數(shù)量opt[0] = 0; // 初始化金額為 0 時的硬幣數(shù)量為 0// 從金額 1 開始逐步計算到 amountfor (int i = 1; i <= amount; i++) {opt[i] = INF; // 初始化為無窮大，表示無法湊成該金額for (int j = 0; j < coins.length; j++) {if (i - coins[j] >= 0) {// 嘗試使用每個硬幣來湊成金額 i，并更新 dp[i] 的最小值opt[i] = Math.min(opt[i], opt[i - coins[j]] + 1);}}}// 如果 opt[amount] 仍然等于 INF，表示無法湊成總金額，返回 -1；否則返回 opt[amount]if (opt[amount] >= INF) {opt[amount] = -1;}return opt[amount];}
}

lc860.檸檬水找零–簡單

題目描述

在檸檬水攤上，每一杯檸檬水的售價為 5 美元。顧客排隊購買你的產(chǎn)品，（按賬單 bills 支付的順序）一次購買一杯。

每位顧客只買一杯檸檬水，然后向你付 5 美元、10 美元或 20 美元。你必須給每個顧客正確找零，也就是說凈交易是每位顧客向你支付 5 美元。

注意，一開始你手頭沒有任何零錢。

給你一個整數(shù)數(shù)組 bills ，其中 bills[i] 是第 i 位顧客付的賬。如果你能給每位顧客正確找零，返回 true ，否則返回 false 。

示例 1：

輸入：bills = [5,5,5,10,20]
輸出：true
解釋：
前 3 位顧客那里，我們按順序收取 3 張 5 美元的鈔票。
第 4 位顧客那里，我們收取一張 10 美元的鈔票，并返還 5 美元。
第 5 位顧客那里，我們找還一張 10 美元的鈔票和一張 5 美元的鈔票。
由于所有客戶都得到了正確的找零，所以我們輸出 true。

示例 2：

輸入：bills = [5,5,10,10,20]
輸出：false
解釋：
前 2 位顧客那里，我們按順序收取 2 張 5 美元的鈔票。
對于接下來的 2 位顧客，我們收取一張 10 美元的鈔票，然后返還 5 美元。
對于最后一位顧客，我們無法退回 15 美元，因為我們現(xiàn)在只有兩張 10 美元的鈔票。
由于不是每位顧客都得到了正確的找零，所以答案是 false。

提示：

• 1 <= bills.length <= 105
• bills[i] 不是 5 就是 10 或是 20

代碼展示

class Solution {public boolean lemonadeChange(int[] bills) {int fiveCount = 0;int tenCount = 0;for (int bill : bills) {if (bill == 5) {fiveCount++;} else if (bill == 10) {if (fiveCount > 0) {fiveCount--;tenCount++;} else {return false;}} else { // 當賬單為20美元時if (tenCount > 0 && fiveCount > 0) {tenCount--;fiveCount--;} else if (fiveCount >= 3) {fiveCount -= 3;} else {return false;}}}return true;}
}

lc455.分發(fā)餅干–簡單

題目描述

假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。

對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j] 。如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標是盡可能滿足越多數(shù)量的孩子，并輸出這個最大數(shù)值。

示例 1:

輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋: 
你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
所以你應該輸出1。

示例 2:

輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋: 
你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2。
你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。
所以你應該輸出2.

提示：

• 1 <= g.length <= 3 * 104
• 0 <= s.length <= 3 * 104
• 1 <= g[i], s[j] <= 231 - 1

代碼展示

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int i = 0, j = 0;int satisfied = 0;while (i < g.size() && j < s.size()) {if (s[j] >= g[i]) {satisfied++;i++;}j++;}return satisfied;}
};

lc122.買賣股票的最佳時機II–中等

題目描述

給你一個整數(shù)數(shù)組 prices ，其中 prices[i] 表示某支股票第 i 天的價格。

在每一天，你可以決定是否購買和/或出售股票。你在任何時候 最多 只能持有 一股 股票。你也可以先購買，然后在 同一天 出售。

返回 你能獲得的 最大 利潤 。

示例 1：

輸入：prices = [7,1,5,3,6,4]
輸出：7
解釋：在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4 。隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6 - 3 = 3 。總利潤為 4 + 3 = 7 。

示例 2：

輸入：prices = [1,2,3,4,5]
輸出：4
解釋：在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4 ?？偫麧櫈?4 。

示例 3：

輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 交易無法獲得正利潤，所以不參與交易可以獲得最大利潤，最大利潤為 0 。

提示：

• 1 <= prices.length <= 3 * 104
• 0 <= prices[i] <= 104

代碼展示

class Solution {
public:int maxProfit(vector<int>& prices) {   int ans = 0;         // 初始化最大利潤為0int n = prices.size(); // 獲取股票價格數(shù)組的長度for (int i = 1; i < n; ++i) { // 遍歷股票價格數(shù)組ans += max(0, prices[i] - prices[i - 1]); // 計算并累加利潤，如果是負數(shù)則不累加}return ans; // 返回最大利潤}
};

lc45.跳躍游戲II–中等

題目描述

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

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

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

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

示例 1:

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

示例 2:

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

提示:

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

代碼展示

class Solution {
public:int jump(vector<int>& nums) {int n = nums.size();int jumps = 0;int farthest = 0;int currentEnd = 0;for (int i = 0; i < n - 1; i++) {farthest = max(farthest, i + nums[i]); // 更新當前能夠跳到的最遠位置if (i == currentEnd) { // 如果到達當前能夠跳的最遠位置jumps++; // 增加跳躍次數(shù)currentEnd = farthest; // 更新當前能夠跳到的最遠位置}}return jumps;}
};

lc1665.完成所有任務的最少初始能量–困難

題目描述

給你一個任務數(shù)組 tasks ，其中 tasks[i] = [actuali, minimumi] ：

• actuali 是完成第 i 個任務 需要耗費 的實際能量。
• minimumi 是開始第 i 個任務前需要達到的最低能量。

比方說，如果任務為 [10, 12] 且你當前的能量為 11 ，那么你不能開始這個任務。如果你當前的能量為 13 ，你可以完成這個任務，且完成它后剩余能量為 3 。

你可以按照 任意順序 完成任務。

請你返回完成所有任務的 最少 初始能量。

示例 1：

輸入：tasks = [[1,2],[2,4],[4,8]]
輸出：8
解釋：
一開始有 8 能量，我們按照如下順序完成任務：- 完成第 3 個任務，剩余能量為 8 - 4 = 4 。- 完成第 2 個任務，剩余能量為 4 - 2 = 2 。- 完成第 1 個任務，剩余能量為 2 - 1 = 1 。
注意到盡管我們有能量剩余，但是如果一開始只有 7 能量是不能完成所有任務的，因為我們無法開始第 3 個任務。

示例 2：

輸入：tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
輸出：32
解釋：
一開始有 32 能量，我們按照如下順序完成任務：- 完成第 1 個任務，剩余能量為 32 - 1 = 31 。- 完成第 2 個任務，剩余能量為 31 - 2 = 29 。- 完成第 3 個任務，剩余能量為 29 - 10 = 19 。- 完成第 4 個任務，剩余能量為 19 - 10 = 9 。- 完成第 5 個任務，剩余能量為 9 - 8 = 1 。

示例 3：

輸入：tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
輸出：27
解釋：
一開始有 27 能量，我們按照如下順序完成任務：- 完成第 5 個任務，剩余能量為 27 - 5 = 22 。- 完成第 2 個任務，剩余能量為 22 - 2 = 20 。- 完成第 3 個任務，剩余能量為 20 - 3 = 17 。- 完成第 1 個任務，剩余能量為 17 - 1 = 16 。- 完成第 4 個任務，剩余能量為 16 - 4 = 12 。- 完成第 6 個任務，剩余能量為 12 - 6 = 6 。

提示：

• 1 <= tasks.length <= 105
• 1 <= actuali <= minimumi <= 104

代碼展示

class Solution {
public:int minimumEffort(vector<vector<int>>& tasks) {/*消耗(actual)小，門檻（minimum）大，是先做的條件按actual + (-minimum)排序*/sort(tasks.begin(), tasks.end(),[](vector<int>& a, vector<int>& b) {return a[0] - a[1] < b[0] - b[1];});// 正序做任務，但計算要倒序int energy = 0; // 任務全部做完（什么也不用再做了）的時候，還需要0的能量for (int i = tasks.size() - 1; i >= 0; i--) {//           minimum        energy + actualenergy = max(tasks[i][1], energy + tasks[i][0]);}return energy;}
};