leetcode 134 加油站
在一条环路上有 $N$ 个加油站,其中第$i$个加油站有汽油 $gas[i]$ 升。你有一辆油箱容量无限的的汽车,从第 $i$ 个加油站开往第 $i+1$ 个加油站需要消耗汽油 $cost[i]$ 升。你从其中的一个加油站出发,开始时油箱为空。如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 $-1$。
- 说明: 如果题目有解,该答案即为唯一答案。输入数组均为非空数组,且长度相同。输入数组中的元素均为非负数。
1 | 示例 1: |
1 | 示例 2: |
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/gas-station
思路:每个站的实际消耗为$gas[i]-cost[i]$,要回到出发地,所以可以将数组扩大一倍,指针start指向起点,end指向终点,cur记录当前油箱有多少油,当$cur<0$说明到不了end这个站,移动start指针直到$cur>=0$。如果$end-start+1==n$说明可以从start出发并且回到start。
- 时间复杂度:$O(2*n)$
- 空间复杂度:$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n=gas.size(),start=0,end=0,cur=0;
int sum[n];
for(int i=0;i<n;i++) sum[i] = gas[i] - cost[i];
while(start<n && end<2*n){
cur+=sum[end%n];
if(cur<0){
while(start<n && cur<0){
cur-=sum[start];
start++;
}
}
if(end - start + 1 == n) return start;
end++;
}
return -1;
}
};
leetcode 739 每日温度
请根据每日 气温 列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。
1 | 例如,给定一个列表temperatures = [73, 74, 75, 71, 69, 72, 76, 73], |
提示:气温列表长度的范围是[1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。
来源:力扣(LeetCode)
思路:单调栈模板水题。
1 | class Solution { |
leetcode 1029 两地调度
计划面试 $2N$ 人。第 $i$ 人飞往 A 市的费用为 $costs[i][0]$飞往 B 市的费用为 $costs[i][1]$将每个人都飞到某座城市的最低费用,要求每个城市都有 $N$ 人抵达。
1 | 示例: |
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/two-city-scheduling
思路:贪心,按照每个人去两个城市的花费的差的绝对值从大到小排序,差越大说明如果这个人没去花费小的那个城市的话代价更大,因此按照代价选城市,例如[10,20][30,200]这两个,代价差从小到大排好序之后是170,10,如果第二个人去B那他比去A要多花170的花费。A记录去A市的人数,B记录去B市的人数。
1 | class Solution { |