LeetCode: Gas Station

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.

这道题主要是数字分析,找规律。

首先,可以用gas[i]-cost[i]求得left[i]. 如何将所有的left[i]求和total<0,那么一定是不能循环一圈的。

如何total>0,那么一定是可以循环一圈的。就是要求这个起始点。

还有一点是,如果从i到j的和是负的,那么从i,j中间任意一个节点出发都是失败的。因为i到k是正的,i到j是负的,那么k到j一定是负的。

根据这个条件就可以得到一个O(n)的算法。

从i=0循环,如果求和为0,那么从i的下一个节点重新开始循环,直到index与i重合。

关键的一点是,i和index在最开始的时候会重合一次,最后还会重合一次。所以要用一个flag来标记是第几次重合。

LeetCode: Gas Station
 1 public int canCompleteCircuit(int[] gas, int[] cost) {
 2         int total = 0;
 3         int[] left = new int[gas.length];
 4         for (int i=0; i<gas.length; i++) {
 5             left[i] = gas[i] - cost[i];
 6             total += left[i];
 7         }
 8         if (total < 0) return -1;
 9         int s = 0;
10         int index = 0;
11         boolean flag = false;
12         for (int i=0; ; i = (i+1)%left.length) {
13             s += left[i];
14             if (s < 0) {
15                 s = 0;
16                 index = (i+1)%left.length;
17             }
18             if (index == i) {
19                 if (flag == false)
20                     flag = true;
21                 else 
22                     return index;
23             }
24         }
25     }
LeetCode: Gas Station

看到别人的方法,在我的基础上有一个新的观察,就是i只要循环到数组结尾就行。因为如果index到数组结尾是正的,那么它一定能循环回index。

反证法:假设从index到一个i<index的位置的和为负。因为index到结尾为正,那么从0到i一定是负的。同时从i到index一定是负的,否则不能以index起始。

所以三段加起来一定是负的。与total>0矛盾。

LeetCode: Gas Station
 1 int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
 2   int sum = 0;
 3   int total = 0;
 4   int j = -1;
 5   for(int i = 0; i < gas.size() ; ++i){
 6     sum += gas[i]-cost[i];
 7     total += gas[i]-cost[i];
 8     if(sum < 0){
 9       j=i; sum = 0; 
10     }
11   }
12   return total>=0? j+1 : -1;
13 }
LeetCode: Gas Station

LeetCode: Gas Station

上一篇:Triangle


下一篇:谁干的mysql无密码登录?