leetcode134.加油站 贪心法求解 （c++版本）

题目描述

题目比较长，明确以下这点就可以

• gas数组是当前下标i加油站所能加的油
• cost数组是从当前下标i加油站到下一加油站所消耗的油
• 那么gas [i]与cost [i] 的大小就决定了车辆能否从当前加油站出发到达下一加油站

上面三点非常重要是能正确做出题目的必须要求
其实用贪心法也是比较简单的，我们的正常思路其实就是贪心法
不断比较gas与cost数组的同一下标的数值，找到可以作为起始点的元素，然后进行计算是否可以达到。
这里面有个小小的数学逻辑：

• 加的油减去花费的就是剩余的，那么剩余的总和必须为正才可以
• 即时在前面为负后面的也会将其补上，因此总体为正

代码实现

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int totalsum = 0;
        int cursum = 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)
            {	// 不可以作为起始点，将下一点作为起始点
                cursum = 0;
                start = i + 1;
            }
        }
        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
19
20
21
22
23