Gas Station

Algorithm>LeetCode

LeetCode - 134.Gas Station

题目大意：

有n个加油站分布在 环形路线上。其中每个加油站的储油量为 gas[i]。 你有一辆巨大油箱(可以无限加油)的汽车,从 站点i到下一站i+1，油耗为 cost[i]。一开始的时候，汽车油箱是空的。

如果你能一次开完全程的话，请返回一个起始站点。否则返回-1表示无法完成。

  • 提示： 测试用例保证答案是唯一的。

  • 疑问：题目未明显指出 是顺时针开或逆时针开。但从测试数据理解 站点i 到 站点i+1，应该是顺时针开的。

解题思路：

首先可以明确的是，如果 总油耗sum{cost[0...n]} 大于 总储量sum{gas[0...n]}的话，是无法完成任务的。直接返回-1。

接着，思考一下当 总油耗 小等于 总储量时，是否必然存在可行解。

C(i) + C(i+1) + C(i+2) + C(i+3) … + C(i+n) = C

G(i) + G(i+1) + G(i+2) + G(i+3) … + G(i+n) = G

G >= C

如果 平均分布的话， 则 G(i)>=C(i) 。 必然是ok的。

考虑极限情况，C(i) 油耗巨大。贪心策略保证每站必停(油不加白不加)，我们从i站点逆时针选点。基于贪心考虑，逆时针选站点要保证对经过C(i)最大油耗是有利：每一次后退选点对总油耗是正向的。

枚举 (Time Limit Exceeded)

时间复杂度 大致为 O(n^2)。 测试用例数据极为暴力。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 int goRound(int starInx,int *gas,int gasSize,int *cost,int costSize){
    int nowGas = 0;
    int nowIdx = starInx;
    for(int i=0;i<gasSize;i++){
        nowGas += gas[nowIdx];
        if(nowGas < cost[nowIdx]) return -1;
        
        nowGas -= cost[nowIdx];
        nowIdx = (nowIdx+1)%gasSize;
    }
    
    return nowGas >= 0 ? starInx : -1;
}

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
    int ans = -1;
    int totalGas = 0, totalCosts = 0;

    for(int i=0;i<costSize;i++){
        totalCosts += cost[i];
    }
    
    for(int i=0;i<gasSize;i++){
        totalGas += gas[i];
    }
    
    if(totalGas < totalCosts) return ans;
    
    for(int i=0;i<gasSize;i++){
        if((ans = goRound(i,gas,gasSize,cost,costSize)) != -1){
            break;
        }
    }
    
    return ans;
}

贪心 (Accepted)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
    int totalGas = 0, totalCosts = 0;
    int maxCostIdx = -1, maxCost = -1;
    for(int i=0;i<costSize;i++){
        totalCosts += cost[i];
        if(cost[i] > maxCost){
            maxCostIdx = i;
            maxCost = cost[i];
        }
    }
    
    for(int i=0;i<gasSize;i++){
        totalGas += gas[i];
    }
    
    if(totalGas < totalCosts) return -1;
    
    int tmp = maxCostIdx;
    int tmpMaxgas = gas[tmp];
    int tmpMaxCost = cost[tmp];
    
    while (tmpMaxgas < tmpMaxCost || gas[tmp] >= cost[tmp]) { // 贪心策略
        tmp--;
        if(tmp == -1) tmp = gasSize - 1;
        if(tmp == maxCostIdx) break;
        
        
        tmpMaxgas += gas[tmp];
        tmpMaxCost += cost[tmp];
    }
    
    
    return (tmp+1)%gasSize;
}

Accepted