Posted on 2023-01-07 18:01
Uriel 阅读(48)
评论(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