leetcode 134 加油站

分手后的思念是犯贱 2022-08-28 09:47 175阅读 0赞

## 前言 ##

题目：[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]。很巧妙~
        }
    };

[134.]: https://leetcode-cn.com/problems/gas-station/
[-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.md