0%

每日三题 leetcode137 加油站 leetcode 739 每日温度 leetcode 1029 两地调度

leetcode 134 加油站

在一条环路上有 $N$ 个加油站,其中第$i$个加油站有汽油 $gas[i]$ 升。你有一辆油箱容量无限的的汽车,从第 $i$ 个加油站开往第 $i+1$ 个加油站需要消耗汽油 $cost[i]$ 升。你从其中的一个加油站出发,开始时油箱为空。如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 $-1$。

  • 说明: 如果题目有解,该答案即为唯一答案。输入数组均为非空数组,且长度相同。输入数组中的元素均为非负数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例 1:

输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

输出: 3

解释:
3 号加油站(索引为 3 处)出发,可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站,此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站,此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站,此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站,此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站,你需要消耗 5 升汽油,正好足够你返回到 3 号加油站。
因此,3 可为起始索引。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 2:
输入:
gas = [2,3,4]
cost = [3,4,3]

输出: -1

解释:
你不能从 0 号或 1 号加油站出发,因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发,可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站,此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站,此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站,因为返程需要消耗 4 升汽油,但是你的油箱只有 3 升汽油。
因此,无论怎样,你都不可能绕环路行驶一周。

思路:每个站的实际消耗为$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
    20
    class 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
2
例如,给定一个列表temperatures = [73, 74, 75, 71, 69, 72, 76, 73],
你的输出应该是[1, 1, 4, 2, 1, 1, 0, 0]。

思路:单调栈模板水题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
int n = T.size();
stack<int> s;
vector<int> right(n);
for(int i=n-1;i>=0;i--){
while(!s.empty() && T[s.top()] <= T[i]) s.pop();
if(s.empty()) right[i] = n;
else right[i] = s.top();
s.push(i);
}
for(int i=0;i<n;i++) {
if(right[i] == n) right[i] = 0;
else right[i] -= i;
}
return right;
}
};

leetcode 1029 两地调度

计划面试 $2N$ 人。第 $i$ 人飞往 A 市的费用为 $costs[i][0]$飞往 B 市的费用为 $costs[i][1]$将每个人都飞到某座城市的最低费用,要求每个城市都有 $N$ 人抵达。

1
2
3
4
5
6
7
8
9
10
11
示例:

输入:[[10,20],[30,200],[400,50],[30,20]]
输出:110
解释:
第一个人去 A 市,费用为 10
第二个人去 A 市,费用为 30
第三个人去 B 市,费用为 50
第四个人去 B 市,费用为 20

最低总费用为 10 + 30 + 50 + 20 = 110,每个城市都有一半的人在面试。

思路:贪心,按照每个人去两个城市的花费的差的绝对值从大到小排序,差越大说明如果这个人没去花费小的那个城市的话代价更大,因此按照代价选城市,例如[10,20][30,200]这两个,代价差从小到大排好序之后是170,10,如果第二个人去B那他比去A要多花170的花费。A记录去A市的人数,B记录去B市的人数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
int n = costs.size(), A = 0, B = 0, res = 0;
vector<vector<int>> dis(n);
for(int i=0;i<n;++i) dis[i] = {abs(costs[i][1] - costs[i][0]),i};
sort(dis.rbegin(),dis.rend());
for(vector<int> &c:dis) {
if(costs[c[1]][0] < costs[c[1]][1]){
if(A < n>>1){
++A;
res+=costs[c[1]][0];
}else res+=costs[c[1]][1];
} else {
if(B < n>>1){
++B;
res+=costs[c[1]][1];
}
else res+=costs[c[1]][0];
}
}
return res;
}
};