c********p
发帖数: 1969 | 1 看到的最简洁的代码，大概是这个：
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
int sum = 0, total = 0, len = gas.length, index = -1;
for(int i=0; i
sum += gas[i]-cost[i];
total += gas[i]-cost[i];
if(sum < 0){
index = i;
sum = 0;
}
}
return total>=0 ? index+1 : -1;
}
}
但是不太理解。从最后那个index开始的，到结尾，total是大于0, 可是这个路线是环
形的，怎么能保证，到数组尾时候total大于0, 从数组头开始，能保证到这个index的
时候依然大于0么？
虽然这段代码非常简洁，，偶没看懂。。。请达人指教 |
t**********r
发帖数: 2153 | |
t**********r
发帖数: 2153 | 3 sum 用来找起始位置。total算总的油量和油耗。好象应该index+1% length
reused
【在 c********p 的大作中提到】
: 看到的最简洁的代码，大概是这个：
: public class Solution {
: public int canCompleteCircuit(int[] gas, int[] cost) {
: // Note: The Solution object is instantiated only once and is reused
: by each test case.
: int sum = 0, total = 0, len = gas.length, index = -1;
: for(int i=0; i: sum += gas[i]-cost[i];
: total += gas[i]-cost[i];
: if(sum < 0){
|
c********p
发帖数: 1969 | 4 别这么说。。。
不是我写的代码。。。
你让写代码的人看到多不好啊。。。
【在 t**********r 的大作中提到】
: 变量名起的太差了。
|
c********p
发帖数: 1969 | 5 可是怎么能确定，找到的起点位置，能保证从A[0]开始也能total大于0？
【在 t**********r 的大作中提到】
: sum 用来找起始位置。total算总的油量和油耗。好象应该index+1% length
:
: reused
|
T******e
发帖数: 157 | 6 只要total大于等于0，就说明走一个环路是可行的，假设total等于0时你能完成从i出
发走到起点但不能完成环路，就会有：
g[i] + g[i+1] + ... + g[n-1] >= A[i]+A[i+1]+...+A[n-1]
g[i]+...+g[n-1]+g[0] < A[i]+...+A[n-1]+A[0] //到达起点后无法前往下一站
但你的total大于等于0，这就会有：
g[1] + g[2] + g[i-1] > A[1] + ... + A[i-1]
如此你可以看到在1到i-1中会有那么个地点使得你能够完成环路
【在 c********p 的大作中提到】
: 可是怎么能确定，找到的起点位置，能保证从A[0]开始也能total大于0？
|
x****8
发帖数: 127 | 7 假设有一个array: gain[x] = gas[x] - cost[x]
1 如果gain的所有elements加起来大于等于0 那肯定有解；反之肯定无解
2 其次，从任何一个非负gain的x开始loop，如果到x2的时候cumulative sum小于零了
，肯定x不是
起点，而且x之后到这个x2之间的点也都不可能是起点（因为他们肯定也< 0)
所以走一遍 最后如果条件1满足 那时候的x就是起始点
【在 c********p 的大作中提到】
: 可是怎么能确定，找到的起点位置，能保证从A[0]开始也能total大于0？
|
c********p
发帖数: 1969 | 8 前边可能不止一段是小于0之后重新开始的。。。
【在 T******e 的大作中提到】
: 只要total大于等于0，就说明走一个环路是可行的，假设total等于0时你能完成从i出
: 发走到起点但不能完成环路，就会有：
: g[i] + g[i+1] + ... + g[n-1] >= A[i]+A[i+1]+...+A[n-1]
: g[i]+...+g[n-1]+g[0] < A[i]+...+A[n-1]+A[0] //到达起点后无法前往下一站
: 但你的total大于等于0，这就会有：
: g[1] + g[2] + g[i-1] > A[1] + ... + A[i-1]
: 如此你可以看到在1到i-1中会有那么个地点使得你能够完成环路
|
g***j
发帖数: 1275 | 9 这个题目我也有同样的疑问，但是题目似乎说，只有一个解，是不是这就是关键？
【在 c********p 的大作中提到】
: 前边可能不止一段是小于0之后重新开始的。。。
|
s*****n
发帖数: 169 | |
|
|
b******7
发帖数: 92 | 11 这题把gas[i] - cost[i]之后就变成找环形数组的最大子数组和问题。找出最大子数组
和的起始位置idx，若该问题有解，则idx一定是一个解 |
S******6
发帖数: 55 | 12 觉得做得挺巧妙
如果能跑完整个环，要保证所有Sigma(gas［i］－cost[i]),也就是这里的total >=0,
index是用来记录从哪里可以跑完，显然sum<0之前的位置都不可以 |
s*****n
发帖数: 994 | 13 class Solution {
public:
int canCompleteCircuit(vector &gas, vector &cost) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
int n = gas.size();
if (n == 0) return -1;
int worst = 0;
int worst_index = 0;
int sum = 0;
for (int i=0; i
int new_worst = worst+sum+gas[i]-cost[i];
if (new_worst < worst){
worst = new_worst;
worst_index = i;
sum = 0;
}else{
sum += gas[i]-cost[i];
}
}
if (sum + worst >= 0) return (worst_index+1)%n;
return -1;
}
};
reused
【在 c********p 的大作中提到】
: 看到的最简洁的代码，大概是这个：
: public class Solution {
: public int canCompleteCircuit(int[] gas, int[] cost) {
: // Note: The Solution object is instantiated only once and is reused
: by each test case.
: int sum = 0, total = 0, len = gas.length, index = -1;
: for(int i=0; i: sum += gas[i]-cost[i];
: total += gas[i]-cost[i];
: if(sum < 0){
|
c********p
发帖数: 1969 | 14 which is wrong
【在 s*****n 的大作中提到】
: wrong solution.
|
z*********8
发帖数: 2070 | 15 swanson (swanson) is wrong :)
【在 c********p 的大作中提到】
: which is wrong
|
c********p
发帖数: 1969 | 16 .......
【在 z*********8 的大作中提到】
: swanson (swanson) is wrong :)
|
a********9
发帖数: 129 | 17 还是不太明白，为什么总共所有的total>0，就能保证一定能有解。。求大神解释。。 |
w********s
发帖数: 214 | 18 这个的确描述起来有点tricky
其实整个过程就是寻找最低点的过程。
我们假设k[i]=g[i]-a[i];//g[i]是油量，a[i]是耗油量
如果 i 是最低点，那么如果total>0，那么我们可以推算出以下几个条件成立：
k[i]<0;
A=k[i+1]+...+k[N-1]>0；
B=k[0]+...+k[i-1]>0;
C=B+k[i]<0;
Sum=A+C>0;
A可以compensate C让其大于零，C是处于最低点i的储油值，
所以A可以保证所有点的储油值大于零，如果有唯一解的话，那么i+1必然就是出发点。
因为i+1到最后一个点是积累A的过程。 |
