Posted on 2023-01-07 18:01
Uriel 閱讀(75)
評論(0) 編輯 收藏 引用 所屬分類:
貪心 、
閑來無事重切Leet Code
一些加油站構成一個環路，給出每個加油站i可以加的油量gas[i],以及從idaoi+1需要的油量cost[i]，問是否可以從某個加油站開始順時針遍歷所有加油站
從第一個加油站開始，假設從該站出發，然后依次遍歷，如果發現到達某個加油站時庫存油量加上該站加入的油量無法到達下一站，則重置，從下一站出發，在遍歷時累加所有站的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