LeetCode(134) Gas Station
2024-10-21 13:01:32
题目
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[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.
分析
题目描述:有N个加油站点构成一个环状,每个站点i加油量为gas[i],从站点i到站点i+1需要耗费有两为cost[i],现要求从哪个站点出发可以成功转一圈回到初始站点,返回该站点,若没有则返回-1;
详细思路分析参考:算法分析网址
AC代码
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
if (gas.size() == 0 || cost.size() == 0 || gas.size() != cost.size()) return -1;
int total = 0, sum = 0, start = 0;
for (int i = 0; i < gas.size(); ++i){
total += (gas[i] - cost[i]);
if (sum < 0){ //发现油箱空了,从下一个站点尝试
sum = (gas[i] - cost[i]);
start = i;
}
else
sum += (gas[i] - cost[i]);
}
return total < 0 ? -1 : start; //用total判断start 是否是满足要求的解
}
};
最新文章
- js模版引擎handlebars.js实用教程——如何引入Handlebars.js
- 浅析 Cordova for iOS
- HQ-SSAO (High-Quality SSAO)
- NodeJS路径的小问题
- 7.15 css与js 选择奇偶子元素的区别
- java类的初始化
- 03-JavaScript之数据类型
- ☆ [POJ2559] Largest Rectangle in a Histogram 「单调栈」
- C#异常--System.IO.FileLoadException:“混合模式程序集是针对“v2.0.50727”版的运行时生成的错误
- Ubuntu中让归档管理器支持rar和7z格式
- ASP.NET Core Razor Pages
- Juniper基础配置
- [小A与最大子段和][斜率优化dp+二分]
- HDU 3221 矩阵快速幂+欧拉函数+降幂公式降幂
- poj 2396 Budget
- Bugku Crack it
- 【转】CentOS: 开放80、22、3306端口操作
- Python爬虫之百度API调用
- Zabbix——异常问题处理
- 笔记-python-module导入技巧