प्रौद्योगिकी साझेदारी

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

प्रश्नवर्णनम्

题目🔗

प्रारम्भिक उत्तरम्

विचाराः सर्वे टिप्पण्यां सन्ति, समयसीमाम् अतिक्रमितुं पर्याप्तं नास्ति।

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

लोभी संस्करण विश्लेषण

मया चिरकालात् लोभी एल्गोरिदम् समस्या न कृता, orz...

सर्वप्रथमम् अस्य प्रश्नस्य सीमा अस्ति यत् प्रत्येकस्य स्टेशनस्य शुद्धशेषतैलस्य आयतनं 0 इत्यस्मात् अधिकं वा समं वा भवितुमर्हति अर्थात्rest[i] = gas[i] - cost[i] >= 0。

ततः i अनुक्रमणिका 0 तः सञ्चयं आरभतेrest[i], यस्य योगः इति अभिलेखितःcurSum,एकदाcurSum० तः न्यूनं भवति, ० तः पर्यन्तम् इत्यर्थःiअस्मिन् अन्तरालस्य अन्तः कोऽपि स्थलः आरम्भस्थलरूपेण, गन्तव्यस्थानरूपेण चयनितः न भवतुiसर्वेषां इन्धनं समाप्तं भविष्यति, तदा वयं चयनं कर्तुं शक्नुमःi+1प्रारम्भबिन्दुरूपेण पुनः गणनां कुर्वन्तु।

उपर्युक्तविश्लेषणस्य सारांशं वक्तुं : १.
स्थानीय इष्टतमः : १.curSumएकदा 0 तः न्यूनं जातं चेत्, शर्तं पूरयितुं आरम्भस्थानं न्यूनातिन्यूनं i+1 भवितुमर्हति ।
वैश्विकं इष्टतमम् : भवन्तः एकं प्रारम्भस्थानं ज्ञातुं शक्नुवन्ति यत् एकं परिक्रमणं यावत् धावितुं शक्नोति।

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