기술나눔

한어Русский язык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。

그런 다음 인덱스 0부터 누적되기 시작합니다.rest[i], 그 합계는 다음과 같이 기록됩니다.curSum,한 번curSum0보다 작다는 것은 0부터i이 간격 내에서 어느 사이트를 출발지로 선택하든 목적지는i연료가 모두 떨어지면 우리가 선택할 수 있어요i+1시작점으로 다시 계산하세요.

위의 분석을 요약하면 다음과 같습니다.
국소 최적:curSum0보다 작으면 조건을 충족하려면 시작 위치가 최소한 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