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.
solution:
如果从i出发可以环绕一圈的话,则对于路径上任何一点j,到达j时tank均大于等于零。从index=0为start开始寻找起点,需满足tank += gas[0]-cost[0]>0,如果到达i时,tank += gas[i]-cost[i]<0,则说明从0到i均不能作为起点(i点中gas[i]-cost[i]<0,显然不能做起点),而从0到i-1中,以0为起点时到达i后tank最大,此时仍不满足tank += gas[i]-cost[i]>=0,因此0到i-1均不能作为起点,从i+1开始继续搜索起点。
class Solution { public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { int prev = 0,start = 0,tank = 0; for(int i=0;i<gas.size();i++) { tank += gas[i] - cost[i]; if(tank<0) { prev += tank; start = i+1; tank = 0; } } if(prev+tank<0) return -1; return start; } };
相关推荐
gas ...gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归 valid-palindrome 模拟 pascals-triangle 模拟 pasca
gas station leetcode LeetCode- 坚持每天刷一道算法题,冲鸭!!! day1 验证回文字符串 day2 亲密字符串 柠檬水找零 day3 反转字符串中的单词 day4 三数之和 day5 数组中的第k个最大元素 day6 环形链表II day7 无...
gas station leetcode Leetcode solutions written in Javascript 分类标准 重点:必须掌握的题型。通常都有着代表一类题型的解法,或者可以举一反三。 提高:难度相对高的题,或者思路巧妙的题,提升自我的目的可以...
leetcode 加油站 实施:蛮力 O(N ^ 2) class Solution { public int canCompleteCircuit ( int [] gas , int [] cost ) { for ( int i = 0 ; i < gas . length; i ++ ) { int current_stop = i; int count = 0 ; ...
gas station leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9...
这道题,题目名字就叫gas-station(网址的最后一部分),于是此题目的代码也在gas-station.c文件中。 当一道题通过测试且性能达到预期时,将在git中commit,注释为“测试通过,性能达标”。若commit的注释为其它内容...
Leetcode\gas station(134)。 swift Leetcode\group anagrams(49).swift Leetcode\group 给定他们所属的组大小的人(1282).swift Leetcode\数组中的第k 个最大元素(215).swift Leetcode\最长递增子序列(300).swift ...
134_Gas_Station 118_Pascal's_Triangle_I 119_Pascal's_Triangle_II 169_Majority_Element 229_Majority_Element_II 274_H_索引 275_H_Index_II 217_Contain_Duplicate 55_Jump_Game 45_Jump_Game_II 121_Best_Time...
leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...
gas station leetcode 什么是LeetCode? 官网(中文): 官网(英文): LeetCode是一个在线算法编程网站,上面主要收集了各大IT公司的笔试面试题,对于找工作是一个不可多得的好帮手。 (Notes: Last updated table:...
gas station leetcode LeetCode算法高频题目汇总 序号 题目 1 2 3 4 5 7 8 9 11 12 13 14 15 16 17 19 20 21 22 23 24 25 26 27 28 31 32 33 34 35 38 39 40 41 42 43 45 46 47 48 49 50 53 54 55 56 59 62 64 67 69...
gas station leetcode leetcode # Title README Java Python 0002 0003 0005 0010 0011 0015 0019 0022 0023 0046 0050 0054 0064 0070 0079 0079 0084 0098 0102 0103 0104 README 0110 0110 0124 0125 0134 0142 ...
gas station leetcode Rust Leetcode 练习使用Rust语言刷或者算法题目, 一些不支持Rust判题的会使用Python进行解决,并对解题思路进行简单分析,分类,及总结. Environment rustc 1.44.0 cargo 1.44.0 How to test ...
gas station leetcode algorithm 记录一下学习算法的一些代码。 冗余连接 II 全排列 II 左叶子之和 子集 把二叉搜索树转换为累加树 监控二叉树 合并二叉树 二叉搜索树中的众数 从中序与后序遍历序列构造二叉树 路径...
gas station leetcode 记录leetCode的解题思路 Arrays 发现力不从心的地方很多,我可能有很多的功课需要补足,所以这个专题暂时停止更新 更新剑指offer的解题 备注 1. 部分完工:可以实现,但算法待改进 2. 未完工:...
gas station leetcode Data_Structure 该文记录笔者刷的pat和leetcode的题解。 Pat甲级题解: 模拟: 链表: 树: 图: LeetCode题解:
gas station leetcode LeetCodeCPP 题目来自于牛客网在线编程模块leetcode经典编程题, 激励自己进行算法练习。 148道LeetCode数据结构算法经典在线编程题C++、Java实现 、C++版本:
gas station leetcode 记录leetCode的解题思路 ##Arrays ####发现力不从心的地方很多,我可能有很多的功课需要补足,所以这个专题暂时停止更新