Question:

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.

Note:
The solution is guaranteed to be unique.

 

这个问题看似简单实际上非常棘手,简单想一下BF遍历所有情况的方法很容易想到,但是这种O(N^2)的方法太慢并不能Accepted.



class Solution {
public:
        int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
            int sum = 0;
            for(int i = 0; i < gas.size(); ++i)
            {
                sum = 0;
                for(int j = i; j < gas.size(); ++j)
                {
                    sum += gas[j] - cost[j];
                    if(sum < 0) break;
                }
                if(sum < 0) continue;
                for(int j = 0; j < i; ++j)
                {
                    sum += gas[j] - cost[j];
                    if(sum < 0) break;
                }
                if(sum >= 0) return i;
            }
            return -1;
        }
};
*TLE 做法

进一步思考来说,由于此题解unique,其实有以下规律:

设diff[i] = cost[i] – gas[i], sum(i, j) = diff[i] + diff[i + 1] +…+ diff[j]

  1. 对于sum(0, n) = diff[0] + diff[1] +…+diff[n], 当且仅当sum >= 0时该题才有解
  2.  对于sum(i, j), 当sum(i, j) < 0时,起始出发点不在[i, j-1]中

对于第一个规律,起始从任何点出发如果能回到原点则最终所剩油量都是sum(0, n),所以如果sum(0, n) < 0则证明没有任何一点可以回到原点。

对于第二个规律,由于i无法到达j,所以i肯定不是起始点。假设k ( i < k < j )出发可返回k,由于从i出发可以到达k, 所以从i出发到达k时油量必然大于等于0,也就是说从0出发到达k永远更容易返回k。因为从k出发可返回k,因此从k出发必然能返回i,所以从i出发必然能返回i。此时解并不是unique,故与原条件矛盾。规律2成立。

有了此两个规律就很好写代码了,对于第i (0 <= i < n) 个点来说,找出向前最多能到的第j – 1 (j > i)个点,从第j个点开始再重复以上步骤直到找到能够返回的点。(循环加速法)



class Solution {
public:
        int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
                int sum = 0, ptr = 0;
                vector<int> diff;
                for(int i = 0; i < gas.size(); ++i)
                {
                        diff.push_back(gas[i] - cost[i]);
                        sum += diff[i];
                }
                if(sum < 0) return -1;
                sum = 0;

                while(ptr < diff.size())
                {
                        if(diff[ptr] < 0) { ++ptr; continue; }
                        sum = 0;
                        for(int j = ptr; j < diff.size(); ++j)
                        {
                                sum += diff[j];
                                if(sum < 0) { ptr = j; break; }
                        }
                        if(sum < 0) continue;
                        for(int j = 0; j < ptr; ++j)
                        {
                                sum += diff[j];
                                if(sum < 0) { ++ptr; break; }
                        }
                        if(sum >= 0) return ptr;
                }
                return -1;
        }
};

Leave a Reply

Your email address will not be published. Required fields are marked *