Condivisione della tecnologia

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Descrizione della domanda

题目🔗

Risposta iniziale

Le idee sono tutte nei commenti, non ce n'è abbastanza per superare il limite di tempo.

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        /* 首先出发站startIndex获得的汽油要大于前往下一站要消耗的汽油
        *  也就是：gas[startIndex] >= cost[startIndex]
        *  将计算公式写出来就是：例如从startIndex = 3出发
        *  ((((0 + gas[3] - cost[3]) + gas[4] - cost[4]) + gas[0] - cost[0]) + gas[1] - cost [1]) + gas[2] - cost[2] = 0可以返回
        *  但是还有条件：每一次括号中的计算结果也要大于0
        */ 
        vector<int> v1(gas.size(), 0);
        for(int i = 0; i < gas.size(); i++){
            v1[i] = gas[i] - cost[i];
        }
        /* 上面的计算公式就变成了((((0 + v1[3]) + v1[4]) + v1[0]) + v1[1]) + v1[2] = 0
        *  那么下面我们根据条件“每一次括号中的计算结果也要大于0”来进行判断
        */
        
        // 首先判断整体和如果小于0，那么肯定不能环绕一圈
        if(accumulate(v1.begin(), v1.end(), 0) < 0) return -1;
        int result = -1;
        for(int i = 0; i < gas.size(); i++){
            // 找到第一个汽油大于0的加油站
            if(v1[i] < 0) continue;
            int num = gas.size();
            int k = i;
            int sum = v1[k];
            while(num--){
                if(k == gas.size() - 1){
                    sum += v1[0];
                    k = 0;
                }
                else sum += v1[++k];
                if(sum < 0) break;
            }
            if(sum >= 0) result = i;
        }
        return result;
    }
};
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
37
38
39

Analisi della versione golosa

Non risolvo un problema di algoritmo goloso da molto tempo e non ricordo nemmeno come fare orz...

Innanzitutto, la limitazione di questa domanda è: il volume netto di olio residuo di ciascuna stazione deve essere maggiore o uguale a 0, cioèrest[i] = gas[i] - cost[i] >= 0。

Quindi inizio ad accumulare dall'indice 0rest[i], la cui somma è registrata comecurSum,una voltacurSumè inferiore a 0, significa che da 0 aiAll'interno di questo intervallo, qualunque sia il sito scelto come sito di partenza, quello di destinazioneifiniranno tutti il ​​carburante, allora potremo sceglierei+1Ricalcolare come punto di partenza.

Per riassumere l’analisi di cui sopra:
Ottimo locale:curSumUna volta inferiore a 0, la posizione iniziale deve essere almeno i+1 per soddisfare la condizione.
Ottimale globale: puoi trovare una posizione di partenza che può funzionare per un giro.

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        for(int i = 0; i < gas.size(); i++){
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if(curSum < 0){
                start = i + 1;
                curSum = 0;
            }
        }
        if(totalSum < 0) return -1;
        return start;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18