LeetCode——gas station

发布时间:2017-7-1 11:24:12编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"LeetCode——gas station ",主要涉及到LeetCode——gas station 方面的内容,对于LeetCode——gas station 感兴趣的同学可以参考一下。

Question

There are N gas stations along a circular route, where the amount of gas at station i isgas[i].
You have a car with an unlimited gas tank and it costscost[i]of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.

Solution

这道题采用贪心的思想,如果这站到下一站不能满足要求的话,就从下一站开始,然后记录已经走过的地方所缺的油量的数目。

Code

class Solution {public:    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {        int tankCount = 0;        int need = 0;        int start = 0;        for (int i = 0; i < gas.size(); i++) {            tankCount += gas[i];            if (tankCount >= cost[i]) {                tankCount -= cost[i];                need -= (gas[i] - cost[i]);            } else {                need += (cost[i] - gas[i]);                tankCount = 0;                start = i + 1;            }        }        if (tankCount >= need)            return start;        else


上一篇:HttpClient连接池抛出大量ConnectionPoolTimeoutException: Timeout waiting for connection异常排查
下一篇:[Python爬虫] 之二十一:Selenium +phantomjs 利用 pyquery抓取36氪网站数据

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。