代码随想录算法训练营第二十九天 | 134. 加油站，135. 分发糖果，860.柠檬水找零，406.根据身高重建队列
二十九天打卡，贪心还是比较难，由局部最优推出全局最优的过程比较难想
134.加油站
题目链接
做题过程
- 没找到贪心的思路，想着暴力的做法，循环也比较难写，遇到有数组循环的用
while写即可
知识点
- 局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
贪心算法
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum = 0;int totalSum = 0;int result = 0;for (int i = 0; i < gas.size(); i++) {curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (curSum < 0) {curSum = 0;result = i + 1;}}if (totalSum < 0) return -1;return result;}
};
135.分发糖果
题目链接
解题过程
- 想到用两个方向的比较，但是后面一次比较左边分数高的不用比右边分数高的糖果数再多1，这样前一个方向的比较就失效了，取一个最大的糖果数就行。
知识点
-
先确定右边评分大于左边的情况（也就是从前向后遍历）
此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
局部最优可以推出全局最优。
如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个，所以贪心：candyVec[i] = candyVec[i - 1] + 1
-
再确定左孩子大于右孩子的情况（从后向前遍历）
如果 ratings[i] > ratings[i + 1]，此时candyVec[i]（第i个小孩的糖果数量）就有两个选择了，一个是candyVec[i + 1] + 1（从右边这个加1得到的糖果数量），一个是candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量）。
那么又要贪心了，局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。
局部最优可以推出全局最优。
-
所以就取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多，也比右边candyVec[i + 1]的糖果多。这样避免少发糖果
贪心法
class Solution {
public:int candy(vector<int>& ratings) {int result = 0;vector<int> nums(ratings.size(), 1);for (int i = 1; i < ratings.size(); i++) {if (ratings[i] > ratings[i - 1]) {nums[i] = nums[i - 1] + 1;}}for (int i = nums.size() - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {nums[i] = max(nums[i], nums[i + 1] + 1);}}for (int n : nums) result += n;return result;}
};
860.柠檬水找零
题目链接
做题过程
- 局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。
贪心算法
class Solution {
public:bool lemonadeChange(vector<int>& bills) {int dollar5 = 0;int dollar10 = 0;for (int bill : bills) {if (bill == 5) dollar5++;else if (bill == 10) {dollar10++;dollar5--;} else if (bill == 20) {if (dollar10 > 0) {dollar10--;dollar5--;} else if (dollar10 == 0) {dollar5 -= 3;}}if (dollar5 < 0) return false;}return true;}
};
406.根据身高重建队列
题目链接
做题过程
- 想到先排序，但后面要插入的操作忘记了
知识点
-
在按照身高从大到小排序后：
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优：最后都做完插入操作，整个队列满足题目队列属性
-
频繁的插入操作使用链表效率高
贪心算法
class Solution {
public:static bool cmp(vector<int>& l, vector<int>& r) {if (l[0] == r[0]) return l[1] < r[1];return l[0] > r[0];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(), people.end(), cmp);vector<vector<int>>result;for (int i = 0; i < people.size(); i++) {auto it = result.begin() + people[i][1];result.insert(it, people[i]);}return result;}
};