一些加油站構(gòu)成一個(gè)環(huán)路，給出每個(gè)加油站i可以加的油量gas[i],以及從idaoi+1需要的油量cost[i]，問(wèn)是否可以從某個(gè)加油站開(kāi)始順時(shí)針遍歷所有加油站
從第一個(gè)加油站開(kāi)始，假設(shè)從該站出發(fā)，然后依次遍歷，如果發(fā)現(xiàn)到達(dá)某個(gè)加油站時(shí)庫(kù)存油量加上該站加入的油量無(wú)法到達(dá)下一站，則重置，從下一站出發(fā)，在遍歷時(shí)累加所有站的gas[i]-cost[i]，如果總和小于0，則輸出-1
C++版
1 //134
2 //Runtime: 52 ms (Beats 100%)
3
4 class Solution {
5 public:
6 int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
7 int sum = 0, cnt = 0, st = 0;
8 for(int i = 0; i < gas.size(); ++i) {
9 sum += gas[i] - cost[i];
10 cnt += gas[i] - cost[i];
11 if(sum < 0) {
12 sum = 0;
13 st = (i + 1) % gas.size();
14 }
15 }
16 if(cnt < 0) return -1;
17 return st;
18 }
19 };
Python版
1 #134
2 #Runtime: 551 ms (Beats 85.35%)
3 #Memory: 20.2 MB (Beats 26.28%)
4
5 class Solution(object):
6 def canCompleteCircuit(self, gas, cost):
7 """
8 :type gas: List[int]
9 :type cost: List[int]
10 :rtype: int
11 """
12 cur_gas = 0
13 tol_gas = 0
14 ans = 0
15 for i in range(len(gas)):
16 tol_gas += gas[i] - cost[i]
17 cur_gas = cur_gas + gas[i] - cost[i]
18 if cur_gas < 0:
19 cur_gas = 0
20 ans = (i + 1) % len(gas)
21 if tol_gas < 0:
22 return -1
23 return ans