【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();
}
};