Gas Station [leetcode] 的两种解法

由于gas总量大于cost总量时,一定可以绕所有城市一圈。

第一种解法:

假设一开始有足够的油,从位置i出发,到位置k时剩余的油量为L(i,k)。

对任意的k,L(i,k)根据i的不同,只相差常数。

我们只需要找到最小的L(0, k)对应的k,k+1为所求。

代码如下:

int canCompleteCircuit(vector &gas, vector &cost) { int start = 0; int curGas = 0, minGas = 0, totalGas = 0; for (int i = 0; i curGas) { start = i + 1; minGas = curGas; } } if (totalGas >= 0) return start % gas.size(); else return -1; }

第二种解法:

如果L(i,k)

所以从k+1的位置从0开始找

int canCompleteCircuit(vector &gas, vector &cost) { int start = 0; int curGas = 0, totalGas = 0; for (int i = 0; i = 0) return start % gas.size(); else return -1; }

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:Effective C++ 29-33
下一篇:Effective C++ 34
相关文章

筛素数解法

用log(N)的解法实现数值的整数次方

两种解法-树形dp+二分+单调队列(或RM

UVa 10905 Children's Game 解法

C++中的单例模式 ,类只构造5次的解法

04-07递归解法问题

HDU 1754 树状数组 解法

hdu1394 树状数组 解法

Poj 2299 Ultra-QuickSort 树状数组

POJ 2828 Buy Tickets 线段树解法

图文推荐

Gas Station [leetcode] 的两种解法
ZOJ 3640 Help Me
Gas Station [leetcode] 的两种解法
CF 518C(Anya and
Gas Station [leetcode] 的两种解法
hdu 1016 Prime R
UVA - 11987 - A
分类:默认分类 时间:2015-03-11 人气:11
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.027 (s). 10 q(s)