leetcode 134 加油站

前言

题目：134. 加油站

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

提交代码

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

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

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

每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。

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

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

#include 
#include 
#include 
#include 

using namespace std;

class Solution {
public:
    int canCompleteCircuit(vector& gas, vector& cost) {
        multimap gas_i; // <汽油量，下标>
        for(int i=0; i::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; isecond;
    }
};

int main(void){
    vector gas  = {2,0,1,2,3,4,0};
    vector cost = {0,1,0,0,0,0,11};
    Solution s;
    cout< 
方法三：贪心 
思路和代码实现，来自参考题解。 
class Solution {
public:
    int canCompleteCircuit(vector& gas, vector& 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]。很巧妙~
    }
};

leetcode 134 加油站

C/C++/C#相关栏目本月热门文章