[数据结构与算法]leetcode 134 加油站

前言

题目：134. 加油站

参考题解：加油站-代码随想录

提交代码

方法一：暴力法。均从0位置开始进行累计比较。比较简单，代码略。

方法二：从汽油量最大的点，进行累计比较。最大点失败，则从次大点开始。依次类推，直到确定当前条件无法绕圈。

方法三：这个方法不错，但不容易想到。

• 每个加油站的剩余量rest[i]为gas[i] - cost[i]。

• i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。

我推荐方法一，虽然它是暴力法，但它足够简单，在数据量较少时，完全可以承受。

方法二：从油量较大的站点出发

#include <vector>
#include <algorithm>
#include <map>
#include <iostream>

using namespace std;

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        multimap<int,int> gas_i; // <汽油量，下标>
        for(int i=0; i<gas.size(); i++){
            gas_i.insert(make_pair(gas[i],i));
        }

        multimap<int,int>::iterator it;
        for(it=gas_i.begin(); it!=gas_i.end(); it++){ // 从大于始发站需要汽油量，从大到小选择
            int gas_count = 0;
            int cost_count = 0;
            int loc = it->second;
            int i;
            for(i=0; i<gas.size(); i++){
                gas_count += gas[loc];
                cost_count += cost[loc];
                if(gas_count < cost_count)
                    break;
                loc = (loc+1)%gas.size();
            }
            if(i==gas.size()) break;
        }

        return it==gas_i.end() ? -1 : it->second;
    }
};

int main(void){
    vector<int> gas  = {2,0,1,2,3,4,0};
    vector<int> cost = {0,1,0,0,0,0,11};
    Solution s;
    cout<<s.canCompleteCircuit(gas,cost);
}

方法三：贪心

思路和代码实现，来自参考题解。

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) {   // 当前累加rest[i]和 curSum一旦小于0
                start = i + 1;  // 起始位置更新为i+1
                curSum = 0;     // curSum从0开始
            }
        }
        if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
        return start; // 当可以走一圈时候，起点必然是圈中某一点。从[start,end]多出来的油量，可以填补[0.start-1]。很巧妙~
    }
};