【Day25 LeetCode】贪心Ⅲ

一、贪心Ⅲ

1、加油站 134

这道题直接想法是采用二重循环暴力搜索，简单粗暴但是会超时，是因为以每个点为起点最坏的情况可能都要遍历完全部的序列，有大量重复的操作，那有没有优化的地方呢？有一个结论：如果以$i$位置出发最远可达$j$位置，那么在在这段区间里的任意一点出发都不可能达到比$j$位置更远的地方。反证法可以得出。可以通过这个结论避免大量重复搜索，每个位置只会经过一次。
代码如下：

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size(), s = 0;for(int i=0; i<n; ++i){s = gas[i] - cost[i];int j = (i + 1) % n;while(s >= 0 && i != j){s += gas[j] - cost[j];j = (j + 1) % n;}if(j==i && s >= 0)return i;if(j <= i)return -1;i = j - 1;}return -1;}
};

2、分发糖果 135

分发糖果需要满足其左右孩子的评分高低，直接想着满足两边的条件比较困难，可以先满足一边的条件，在此基础上再满足另一边的条件。
先满足与左边孩子的条件，从前往后看，如果当前孩子评分高于左孩子，则当前孩子的糖果是左孩子的糖果数加1，如果不高于，则给最少的糖果，1个。
在此基础上，再去从后往前看每个孩子的右孩子，如果当前孩子评分高于右孩子，则 当前孩子糖果是在已有糖果 和 右孩子糖果+1之间取最大值，这样可以满足左右孩子两个条件。
代码如下：

class Solution {
public:int candy(vector<int>& ratings) {int n = ratings.size();vector<int> ans(n, 1);// 从前往后for(int i=1; i<n; ++i)if(ratings[i] > ratings[i-1])ans[i] = ans[i-1] + 1;// 从后往前int s = ans[n-1];for(int i=n-2; i>=0; --i){if(ratings[i] > ratings[i+1])ans[i] = max(ans[i], ans[i+1] + 1);s += ans[i];}return s;}
};

3、柠檬水找零 860

这题逻辑比较清楚，10美元只能用5美元找零，20美元可以用3个5美元 或者 1个5美元1个10美元找零。但10美元只能用于20美元找零，5美元可用于10、20美元找零，用处更多，所以应该优先使用10美元5美元去找零20美元，如果没有10美元再全用5美元找零。

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int num_5 = 0, num_10 = 0; // 5/10美元数量for(int bill : bills){switch(bill){case 5:num_5++;break;case 10:{num_5--;num_10++;break;}case 20:{// 优先使用10美元if(num_10 > 0)num_10--;elsenum_5 -= 2;num_5--;}}if(num_10 < 0 || num_5 < 0)return false;}return true;}
};

4、根据身高重建队列 406

有两个元素，一个是身高h，一个是前面不小于当前高度的人数k。可以先按考虑按身高h排序，确定之后再按 k进行插入

class Solution {static bool cmp(const vector<int>& a, const vector<int>& b) {if (a[0] == b[0]) return a[1] < b[1];return a[0] > b[0];}
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(), people.end(), cmp);vector<vector<int>> ans;for(auto p : people)ans.insert(ans.begin()+p[1], p);return ans;}
};

二、写在后面

加油站这题比较巧妙，如果能想到那个结论就很容易进行优化。分发糖果和根据身高重建队列这题主要是当需要满足两边条件时，同时兼顾两边处理起来麻烦， 可以先处理一边，再处理另一边。