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.
[分析] 这道题目暴力法是容易的,但是O(n)的解法都不是那么容易理解的,下面是转载
https://leetcodenotes.wordpress.com/2013/11/21/leetcode-gas-station-%E8%BD%AC%E5%9C%88%E7%9A%84%E5%8A%A0%E6%B2%B9%E7%AB%99%E7%9C%8B%E8%83%BD%E4%B8%8D%E8%83%BD%E8%B5%B0%E4%B8%80%E5%9C%88/的思路:
用反证法来理解。算法:
从i开始,j是当前station的指针,sum += gas[j] – cost[j] (从j站加了油,再算上从i开始走到j剩的油,走到j+1站还能剩下多少油)
如果sum < 0,说明从i开始是不行的。那能不能从i..j中间的某个位置开始呢?假设能从k (i <=k<=j)走,那么i..j < 0,若k..j >=0,说明i..k – 1更是<0,那从k处就早该断开了,根本轮不到j。所以一旦sum<0,i就赋成j + 1,sum归零。最后total 表示能不能走一圈。
看完这个思路后我还有一点疑惑是貌似sum仅计算了[i..N -1]这段能否走下来,为啥total非负就能确定从i 开始可以走完一圈? 对于这个疑惑同样可以用反证法证明(怀疑别人结论时就尝试举反例试试~):
[p, q]表示汽车从p 站出发到达q + 1站时的剩油量。记A=[i, N-1], B=[i, k-1], C=[i, i-1],D=[0, k - 1], E=[k, i - 1], 假设A >= 0 && total >= 0时,B < 0。 因为total == A + D + E, 而(B == A + D)< 0, 则E > 0。 A >= 0, 那么E + A >0,因此按算法找到的start 就不会是 i 而是 k。
[ref]
http://blog.csdn.net/linhuanmars/article/details/22706553
http://blog.csdn.net/kenden23/article/details/14106137
public class Solution {
// Method 2: O(n)
public int canCompleteCircuit(int[] gas, int[] cost) {
if (gas == null || cost == null || gas.length != cost.length)
return -1;
int N = gas.length;
int start = 0;
int sum = 0, total = 0;
for (int i = 0; i < N; i++) {
total += gas[i] - cost[i];
sum += gas[i] - cost[i];
if (sum < 0) {
start = i + 1;
sum = 0;
}
}
return total >= 0 ? start : -1;
}
// Method 1: O(n^2), time out
public int canCompleteCircuit1(int[] gas, int[] cost) {
if (gas == null || cost == null || gas.length != cost.length)
return -1;
int N = gas.length;
for (int i = 0; i < N; i++) {
int volume = 0, j = 0;
for (; j < N; j++) {
int curr = (i + j) % N;
volume += gas[curr];
volume -= cost[curr];
if (volume < 0)
break;
}
if (j == N)
return i;
}
return -1;
}
}
分享到:
相关推荐
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 ####发现力不从心的地方很多,我可能有很多的功课需要补足,所以这个专题暂时停止更新