【134. 加油站】
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
链接：https://leetcode.cn/problems/gas-station/description/
如果x到达不了y+1，那么x-y之间的点也不可能到达y+1，因为中间任何一点的油都是拥有前面的余量的，所以下次遍历直接从y+1开始。
class Solution {public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int sum = 0;int total = 0;int index = -1;for (int i = 0; i < gas.size(); ++i){sum += gas[i] - cost[i];total += gas[i] - cost[i];if (sum < 0){index = i;sum = 0;}}return total < 0? -1 : index + 1;}};
【670. 最大交换】
给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
链接：https://leetcode.cn/problems/maximum-swap/description/
每一位数字应该不小于所有排它后面的数字，否则找最大的且排最后面的数字与之交换。
class Solution {public:int maximumSwap(int num) {string charArray = to_string(num);int n = charArray.size();int maxIdx = n - 1;int idx1 = -1, idx2 = -1;for (int i = n - 1; i >= 0; i--) {if (charArray[i] > charArray[maxIdx]) {maxIdx = i;} else if (charArray[i] < charArray[maxIdx]) {idx1 = i;idx2 = maxIdx;}}if (idx1 >= 0) {swap(charArray[idx1], charArray[idx2]);return stoi(charArray);} else {return num;}}};
【435. 无重叠区间】
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
链接：https://leetcode.cn/problems/non-overlapping-intervals/description/
本题的题意可以表达为，你今天有好几个活动，每个活动都可以用区间 [start,end] 表示开始和结束的时间，请问你今天最多能参加几个活动呢？那我们可能会自然的想到，优先选择参加那些结束时间早的，因为这样可以留下更多的时间参加其余的活动。如果有多个结束时间相同的，我们选择开始时间晚的，因为这样也有助于参加更多的活动。
bool cmp(vector<int> a, vector<int> b) {// return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]); 注意！与其他的区间问题不一样return a[1] < b[1] || (a[1] == b[1] && a[0] < b[0]);}class Solution {public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);vector<vector<int>> ans;for (auto& it: intervals) {if (!ans.empty() && ans.back()[1] > it[0]) {continue;} else {ans.push_back(it);}}return intervals.size() - ans.size();}};
关于互联网持续学习圈
