gas station的解法，我觉得有不完备的可能－－－貌似又是完备的。# JobHunting - 待字闺中
j*d
1 楼
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int sum = 0;
int total = 0;
int j = -1;
for(int i = 0; i < gas.length ; ++i)
{
sum += gas[i]-cost[i];
total += gas[i]-cost[i];
if(sum < 0)
{
j=i; sum = 0;
}
}
if(total<0) return -1;
else return j+1;
}
}
OJ的确是accepted了。但是我觉得是test case不够多，没有测到我认为的case。
这个解法的问题在于，把那个圈当作了直线的100米跑道。第一个点，起点开始，算的
能否跑下来整圈。但是第一个点没跑下来之后，测的点，都只测了从 点 j ，跑到 gas
.length - 1的点的可能性。因为题目The solution is guaranteed to be unique，所
以能跑下来的点，自然在从j到gas.length - 1的点都可以跑下来。
但是，这个解法，就没有算能否从“终点”跑到 J －1的那个点。其实也不需要算，因
为答案唯一，能从 J到终点的点只有一个，那么算出来那个点，从终点到 j －1 自然
不用算了。
但是，如果答案不唯一，貌似需要把 index i， 取个模，把所有的能跑下来的点存下
来。因为唯一的条件不能用了，如果再用这个算法，就可能把所有能从j 跑到终点，但
是不能从终点跑回到 j － 1点的算进去？
写到这里，我发现，我错了。假设， J k两个点， K更接近终点，那么如果JK都能跑道
终点，那么J K段只会是积累gas，或者是0.那么如果终点能跑到 K － 1，也必然能跑
到 J －1.
废话帖子。
public int canCompleteCircuit(int[] gas, int[] cost) {
int sum = 0;
int total = 0;
int j = -1;
for(int i = 0; i < gas.length ; ++i)
{
sum += gas[i]-cost[i];
total += gas[i]-cost[i];
if(sum < 0)
{
j=i; sum = 0;
}
}
if(total<0) return -1;
else return j+1;
}
}
OJ的确是accepted了。但是我觉得是test case不够多，没有测到我认为的case。
这个解法的问题在于，把那个圈当作了直线的100米跑道。第一个点，起点开始，算的
能否跑下来整圈。但是第一个点没跑下来之后，测的点，都只测了从 点 j ，跑到 gas
.length - 1的点的可能性。因为题目The solution is guaranteed to be unique，所
以能跑下来的点，自然在从j到gas.length - 1的点都可以跑下来。
但是，这个解法，就没有算能否从“终点”跑到 J －1的那个点。其实也不需要算，因
为答案唯一，能从 J到终点的点只有一个，那么算出来那个点，从终点到 j －1 自然
不用算了。
但是，如果答案不唯一，貌似需要把 index i， 取个模，把所有的能跑下来的点存下
来。因为唯一的条件不能用了，如果再用这个算法，就可能把所有能从j 跑到终点，但
是不能从终点跑回到 j － 1点的算进去？
写到这里，我发现，我错了。假设， J k两个点， K更接近终点，那么如果JK都能跑道
终点，那么J K段只会是积累gas，或者是0.那么如果终点能跑到 K － 1，也必然能跑
到 J －1.
废话帖子。