Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
一些加油站构成一个环路,给出每个加油站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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理