笔记1 第11课 贪心初步 ——柠檬水找零，分发饼干，跳跃游戏，完成所有任务所需最小能量——极客时间算法

之前收藏了极客时间的算法训练营3期 共21课，计划每一课写博客来记录学习，主要形式为

方法类型1

题1

题解

题2

题解

方法类型2

题1

题解

……

题目大体来自leetcode 和 acwing

主要记录和理解代码，所以基本完全搬运了视频题解代码，

个人学习感受体现在大致思路的总结和注释上。

---

第一题

860. 柠檬水找零

本题满足贪心的正确性，因为20,10，5这些数都是向下兼容的，所以可以直接使用贪心算法。

class Solution {
public:bool lemonadeChange(vector<int>& bills) {coins[5] = coins[10] = coins[20] = 0;for (int bill : bills) {coins[bill]++;if (!exchange(bill - 5)) return false;}return true;}
private:unordered_map<int, int> coins;bool exchange(int bill) {while (coins[20] > 0 && bill >= 20) {coins[20]--;bill -= 20;}while (coins[10] > 0 && bill >= 10) {coins[10]--;bill -= 10;}while (coins[5] > 0 && bill >= 5) {coins[5]--;bill -= 5;}return bill == 0;}
};

第二题

​​​​​​455. 分发饼干

发刚好够吃的或者相对而言浪费最少的饼干，肯定最合适、

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int j = 0;int ans = 0;for (int child : g) {//s数组也排序了，j不满足小胃口的孩子，大胃口的就更不用说了while (j < s.size() && child > s[j]) j++;if (j < s.size() && child <= s[j]) {ans++;j++;}}return ans;}
};

第三题

122. 买卖股票的最佳时机 II

动规的特例

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

第四题

​​​​​​45. 跳跃游戏 II

每一步要跳到，能跳最远下一步，的位置

class Solution {
public:int jump(vector<int>& nums) {int curr = 0;int cnt = 0;while (curr < nums.size() - 1) {int maxStep = 0;int next = curr;for (int i = 1; i <= nums[curr]; i++) {//到达if (curr + i >= nums.size() - 1) return ++cnt;//要找到能走最大的下一步的位置。if (i + nums[curr + i] >= maxStep) {maxStep = i + nums[curr + i];next = curr + i;}}curr = next;cnt++;}return cnt;}
};

第五题

​​​​​​1665. 完成所有任务的最少初始能量

完成某个任务后，剩余能量多的，排在前面做。

class Solution {
public:int minimumEffort(vector<vector<int>>& tasks) {sort (tasks.begin(), tasks.end(),[](vector<int>& A, vector<int>& B) {//肯定是剩余能量多的排在前面。return  A[1] - A[0] < B[1] - B[0];});int ans = 0;for (vector<int> task : tasks) {ans = max(ans + task[0], task[1]);}return ans;}
};