题目
题目地址：LeetCode 86:Partition List
思路
这道题打上的是贪心的tag，那么我们可以这么想：首先如果要走完整个环，那么gas总和肯定要大过cost的总和。因此我们声明一个totalSum来记录每对gas和cost的差的总和。然后我们假设开始的起点res = 0，并从这里出发。接着我们声明一个curSum记录当前路径上每对gas和cost的差。如果遍历到某个点时curSum < 0，说明该路径（从起点到当前点）上任何一点都不能作为起点走完整个环，此时令curSum重置为0，res为下一个点i+1。
代码
C++版本：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int res = 0;
int curSum = 0;
int totalSum = 0;
for(int i = 0;i < gas.size();i++){
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if(curSum < 0){
res = i + 1;
curSum = 0;
}
}
return totalSum >= 0 ? res : -1;
}
};
Python版本：
class Solution(object):
def canCompleteCircuit(self, gas, cost):
"""
:type gas: List[int]
:type cost: List[int]
:rtype: int
"""
res = 0
curSum = 0
totalSum = 0
for i in range(0,len(gas)) :
curSum += gas[i] - cost[i]
totalSum += gas[i] - cost[i]
if curSum < 0 :
res = i + 1
curSum = 0
if totalSum < 0 :
return -1
else :
return res
