134. 加油站
-
题目链接：134. 加油站
-
思路：
- 由题意可得，需要能够走完所有的加油站，就需要保证车到达每一个加油站的时候有油，故先对gas和cost数组做差，得到每个加油站的油差，正代表着车在这里能加油，负代表着车要耗油；
- 做差之后就有两种思考方向，一种是滑动窗口做法，滑动窗口的最大长度为n-1，从第一个战开始模拟，累计油差和，如果油差和小于0，则需要更新起点，很容易想到，当油差和为负时，在这之前的所有加油站都不能作为起点，油差一定为负，如果油差和不为负，窗口大小为n-1时，找到了符合条件的起点，返回即可；
- 贪心思考方向，遍历数组保证油差和为正即可，油差和为负，更新起点和滑动窗口类似，同时记录，总的油差和，总的油差和为正代表着车能走完所有的加油站，具体思路见 卡哥讲解
- 画图法，如下图所示，每一条水平线的第一个交点为每次选择的汽车的起点，由图可以看到示例1，只能选择从起点3开始走，因为从图中可以看到，起点3为整个过程中汽车油耗能到达的最低位置，从油耗最低位置开始出发，就能保证整个过程油耗不会低于0，除非整体油差和为负；灵神讲解
-
代码：
class Solution {
public:// 方法1，滑动窗口int f1(vector<int>& gas, vector<int>& cost) {int n = gas.size();for(int i = 0; i < n; ++i) {gas[i] = gas[i] - cost[i];} int sum = 0, ans = 0;for(int i = 0; i < 2 * n; ++i) {sum += gas[i % n];if(sum < 0) {ans = i + 1;sum = 0;}if(i - ans >= n - 1)return ans;}return -1;}// 方法2，贪心思路int f2(vector<int>& gas, vector<int>& cost) { int curSum = 0;int totalSum = 0;int start = 0;for (int i = 0; i < gas.size(); i++) {curSum += gas[i] - cost[i];totalSum += gas[i] - cost[i];if (curSum < 0) { // 当前累加rest[i]和 curSum一旦小于0start = i + 1; // 起始位置更新为i+1curSum = 0; // curSum从0开始}}if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了return start;}// 方法3，画图思路int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size(), sum = 0, min_s = 0, ans = 0;for(int i = 0; i < n; ++i) {sum += gas[i] - cost[i];if(sum < min_s) { // 更新最小油耗位置min_s = sum; ans = i + 1; // 确定起点}} // 如果油差和为负，代表着不可能走完，为正才能走完return sum < 0 ? -1 : ans;}};
135. 分发糖果
- 题目链接：135. 分发糖果
- 思路：
- 分发糖果，每个孩子都需要分到至少1个糖果，并且保证相邻孩子，评分高的孩子糖果要多；
- 相邻其实就是左右两边，保证孩子和左右两边相比分发的糖果要符合题意；
- 实际操作时，不能同时考虑左右两边的情况，所以先考虑一边，然后考虑另一边的情况，即先只看孩子和左边的孩子比较，保证评分高的多分发1个糖果，分发完了之后，再看右边，两次操作即可；
- 这里有个优化的点，考虑完左边之后，再从后往前考虑右边的时候，分发糖果时记录前一个孩子分发的糖果的数量即可，因为每次比较只比较 i 和 i + 1两个孩子，记录i + 1孩子分发糖果的数量，比较评分就能直接得到第 i 个孩子要分发糖果的数量，得到之后，和从左往右分发的糖果比较，取最大值就是最终的这个孩子要分发的糖果数量
- 代码：
class Solution {
public:// 两次操作，从前往后只考虑左边，从后往前只考虑右边int candy(vector<int>& ratings) {vector<int> candyVec(ratings.size(), 1);// 从前向后for (int i = 1; i < ratings.size(); i++) {if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;}// 从后向前for (int i = ratings.size() - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1] ) {candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);}}// 统计结果int result = 0;for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];return result;}int f1(vector<int>& ratings) {int n = ratings.size();int ans = 0;vector<int> candy(n, 0);for(int i = 0; i < n; i++) {if(i > 0 && ratings[i] > ratings[i-1]) { // 从前往后只考虑左边，记录每个孩子分发糖果数量candy[i] = candy[i-1] + 1;} else {candy[i] = 1;}}// 从后往前，只记录前一个孩子分发糖果数量int right = 0, ret = 0;for (int i = n - 1; i >= 0; i--) {if (i < n - 1 && ratings[i] > ratings[i + 1]) {right++; // 评分高，分发糖果数量比右边要多一个} else {right = 1;}// candy[i]保证符合左边要求，right保证符合右边要求，最大值保证符合两边要求ret += max(candy[i], right);}return ret;}
};
860.柠檬水找零
- 题目链接：860.柠檬水找零
- 思路：记录每卖出一瓶柠檬水获取的币值的数量，枚举需要找零的三种情况，每种情况需要减去5和10两种币值的数量，判断币值数量是否大于 >= 0，不符合则无法正确找零
- 代码：
class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five = 0, ten = 0;for (int b : bills) {if (b == 5) { // 无需找零five++;} else if (b == 10) { // 返还 5five--;ten++;} else if (ten > 0) { // 此时 b=20，返还 10+5five--;ten--;} else { // 此时 b=20，返还 5+5+5five -= 3;}if (five < 0) { // 无法正确找零return false;}}return true;}
};
406.根据身高重建队列
- 题目链接：406.根据身高重建队列
- 思路：本题需要找到每个人的正确位置，题目给的条件是记录了每个人前面比当前身高大的人的数量，所以按照每次找一个人，放入到队列的正确位置的这种思考方向，每次先找身高高的，这样等到身高低的能够直接确定位置，身高一样的，按照前面比他身高高的数量排序，这样就能找到正确顺序
- 代码：
class Solution {
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {// 按照身高排序，降序排序ranges::sort(people, [](vector<int> a, vector<int> b) {if(a[0] == b[0]) return a[1] < b[1];return a[0] > b[0];});list<vector<int>> qe;for(int i = 0; i < people.size(); ++i) {int idx = people[i][1];std::list<vector<int>>::iterator it = qe.begin();while (idx--) { // 寻找在插入位置it++;}qe.insert(it, people[i]);}return vector<vector<int>> (qe.begin(), qe.end());}
};
