0%

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

发表于 分类于 ， 评论次数:：
本文字数： 3.2k 阅读时长 ≈ 3 分钟

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;
    }
};