【LeetCode】加油站
2024-08-25 06:15:32
【问题】在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。
如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1。
说明:
如果题目有解,该答案即为唯一答案。
输入数组均为非空数组,且长度相同。
输入数组中的元素均为非负数。
输入:
gas = [,,,,]
cost = [,,,,]
输出:
解释:
从 号加油站(索引为 处)出发,可获得 升汽油。此时油箱有 = + = 升汽油
开往 号加油站,此时油箱有 - + = 升汽油
开往 号加油站,此时油箱有 - + = 升汽油
开往 号加油站,此时油箱有 - + = 升汽油
开往 号加油站,此时油箱有 - + = 升汽油
开往 号加油站,你需要消耗 升汽油,正好足够你返回到 号加油站。
因此, 可为起始索引。
【思路】首先我们要分析这个起点会不会存在?这个其实很简单,如果将所有的gas总油量 >= 车子的cost总耗油量,从而车子可以走一周的。
我们分析一下,假设起始点为x, 如果总的gas-总的cost大于零时,则我们将当前路径从其实路径x一分为二,左侧的部分剩余油量必定 <= 0,而右侧的部分剩余油量必定 >= 0. 这样才可以使得车子可以完成一周的路程!
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int total = , cur = , start = ;
for(int i = ; i < gas.size(); i++){
total += (gas[i] - cost[i]);
cur += (gas[i] - cost[i]);
if(cur < ){
start = i + ;
cur = ;
}
}
return (total >= ) ? start : -;
}
};
最新文章
- 马化腾称春节前推出微信小程序
- matlab clear
- tomcat安装服务和内存参数设置
- 【转】Gvim开发环境配置笔记--Windows篇
- 【hello,world 也打脸】记storm-starter在某知名IDE下的悲催调试经历
- oracle序列为什么不是从1开始
- select2去除搜索框
- aspnetpager的2种分页方法
- jquery(1.3.2)<;--json-->;spring(3.0)
- UIMenuController/UIPasteboard(1) 制作一个可以粘贴复制的Label
- 子元素div高度不确定时父div高度如何自适应
- 【1】Laravel5.1 安装
- 浙江大学PAT上机题解析之3-04. 一元多项式的乘法与加法运算
- svn搭建
- Kali命令集
- Selenium里可以自行封装与get_attribute对应的set_attribute方法
- Python转页爬取某铝业网站上的数据
- 【oracle入门】数据模型
- OpenMPI源码剖析:网络通信原理(一)
- Python 函数式编程和OOP编程 0001测试
热门文章
- 定时任务--mysql数据库备份
- lnmp1.5安装fileinfo扩展
- win10的guard占内存过高
- input、raw_input区别,运算符,运算优先级,多变赋值方式
- Spark教程——(8)本地执行spark-sql程序
- sparkRDD:第4节 RDD的依赖关系;第5节 RDD的缓存机制;第6节 DAG的生成
- 帆软FineReport报表由于使用HTML显示后无法控制行高
- Atcoder Grand Contest 037C(贪心,优先队列,思维)
- in comment after two dashes (--) next character must be >; not - (position: START_TAG seen ...
- JSTL中获取URL参数