leetcode加油站问题_高一物理必修一典型例题及答案

leetcode加油站问题_高一物理必修一典型例题及答案问题描述:在一条环形路上有N个加油站,其中第i个加油站有汽油gas[i]升

问题描述:

在一条环形路上有N个加油站,其中第i个加油站有汽油gas[i]升。你有一辆汽油容量无限的汽车,从第i个加油站开往第i+1个加油站需要耗费油量gas[i]升。假设开始时油箱为空,如果你可以围绕环行路形式一周,则返回出发时加油站的编号,否则返回-1。

leetcode加油站问题_高一物理必修一典型例题及答案

问题分析:

本题是一个典型的求子和最大问题。我们需要对整个序列进行遍历。首先设置一个标志位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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注