Lexi's Leetcode solutions

[leetcode] Gas Station | 转圈的加油站看能不能走一圈

Posted on: November 21, 2013

这个题要用反证法来理解。算法:

  1. 从i开始,j是当前station的指针,sum += gas[j] – cost[j] (从j站加了油,再算上从i开始走到j剩的油,走到j+1站还能剩下多少油)
  2. 如果sum < 0,说明从i开始是不行的。那能不能从i..j中间的某个位置开始呢?假设能从k (i <=k<=j)走,那么i..j < 0,若k..j >=0,说明i..k – 1更是<0,那从k处就早该断开了,根本轮不到j。
  3. 所以一旦sum<0,i就赋成j + 1,sum归零。
  4. 最后total表示能不能走一圈。
  5. 这个题算法简单,写起来真是够呛。对数组一快一慢双指针的理解还是不行。注意千万不能出现while (i < 0) { i++, A[i]}这种先++然后取值的情况,必须越界。
public int canCompleteCircuit(int[] gas, int[] cost) {
    int i = 0, j = 0;
    int sum = 0;
    int total = 0;
    while (j < gas.length) {
        int diff = gas[j] - cost[j];
        if (sum + diff < 0) {
            i = j + 1;
            sum = 0;
        } else {
            sum += diff;
        }
        j++;
        total += diff;
    }
    return total >= 0 ? i : -1;
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: