问题描述:
在一条环形路上有N个加油站,其中第i个加油站有汽油gas[i]升。你有一辆汽油容量无限的汽车,从第i个加油站开往第i+1个加油站需要耗费油量gas[i]升。假设开始时油箱为空,如果你可以围绕环行路形式一周,则返回出发时加油站的编号,否则返回-1。
问题分析:
本题是一个典型的求子和最大问题。我们需要对整个序列进行遍历。首先设置一个标志位hasRes,然后再计算启动位置:如果sum>0,则启动位置不发生改变,否则,res = i , 并且sum重新计算。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int res = 0;
int sum = 0;
int hasRes = 0; //用于判断是否有跑完全程所需要的油
for(int i=0;i<gas.size();i++)
{
hasRes +=gas[i]-cost[i];
if(sum>0) sum+=gas[i]-cost[i];
else {
sum = gas[i]-cost[i];
res = i;
}
}
return hasRes >=0?res:-1;
}
};
今天的文章leetcode加油站问题_高一物理必修一典型例题及答案分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/64733.html