Technologieaustausch

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

Beschreibung der Frage

题目🔗

Erste Antwort

Die Ideen sind alle in den Kommentaren, es gibt nicht genug, um das Zeitlimit zu überschreiten.

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

Gierige Versionsanalyse

Ich habe schon lange kein Greedy-Algorithmus-Problem mehr gelöst und kann mich nicht einmal daran erinnern, wie man Orz macht ...

Die Einschränkung dieser Frage besteht zunächst darin, dass das verbleibende Nettoölvolumen jeder Station größer oder gleich 0 sein muss, d.rest[i] = gas[i] - cost[i] >= 0。

Dann beginne ich mit der Akkumulation ab Index 0rest[i], deren Summe als aufgezeichnet wirdcurSum,einmalcurSumkleiner als 0 ist, bedeutet dies, dass von 0 bisiInnerhalb dieses Intervalls ist es egal, welcher Standort als Start- und Zielort gewählt wirdiWird allen der Treibstoff ausgehen, dann können wir wähleni+1Beginnen Sie als Ausgangspunkt mit der Neuberechnung.

Um die obige Analyse zusammenzufassen:
Lokales Optimum:curSumSobald er kleiner als 0 ist, muss die Startposition mindestens i+1 sein, um die Bedingung zu erfüllen.
Global optimal: Man findet eine Startposition, die man eine Runde lang laufen kann.

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