Leetcode134-加油站

$\textrm{Problem Description : }$$\href{https://leetcode-cn.com/problems/gas-station/}{\textrm{LeetCode134—Gas Station}}$

$\textrm{Language: C++,Python3}$

$\textrm{Label: Greedy,Brain Teaser}$

$\textrm{Solution:}$

显然模拟一个起点是否能够达到终点需要$O(n)$的时间复杂度，那么枚举每个点的起点就需要$O(n^2)$的复杂度，题目中虽然没有说明$n$的规模，但我们肯定希望用更优的解法。考虑这样一个情况，假设有加油站$X_0$，我们从$X_0$开始枚举，遇到$X_N$时汽油不够，此时停止循环，得到了$X_0$，$X_1$，$X_2$，……，$X_N$的队列，那么我们可以保证$X_0$开始抵达任意一个$X_i (i < N)$ 均有$ExtraGas >= 0$，然后考虑起始点为$X_i$时到$X_N$的路径，此时$ExtraGas = 0$，那么相比于$X_0$到$X_N$，失去了额外油量的加持，也一定无法抵达。即若$ExtraGas + gas[i] < cost$，那么$gas[i] < cost$必定成立。

这就意味着对于$X_i (0 <= i <= N)$均无法完成一周的旅程，我们的下一次枚举点之间变更为$X_{N+1}$，基于这样的思想，实际上只要遍历一遍数组，时间复杂度为$O(n)$

时间复杂度: $O(n)$

空间复杂度: $O(1)$

$\textrm{C++ Source Code}$

class Solution 
{
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) 
    {
        int n = gas.size();         
        int index = 0; //起点下标
        while(index < n)
        {
            int ExtraGas = 0,i;
            for(i = 0;i < n;i++) //枚举n个点
            {
                int j = (i+index)%n; //类似循环队列
                ExtraGas += gas[j]-cost[j];
                if(ExtraGas < 0) break;
            }
            if(i == n) return index;
            else index += i+1; //getNext
        }
        return -1; //没有符合要求的点
    }
};

$\textrm{Python Source Code}$

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas) 
        index = 0
        while index < n:
            ExtraGas = i = 0
            while i < n:
                j = (i+index)%n
                ExtraGas += gas[j]-cost[j]
                if ExtraGas < 0:
                    break
                i += 1

            if i == n:
                return index 
            index += i+1

        return -1

$\textrm{Author}$@$\href{http://kuroko.info}{\textrm{Kuroko}}$

$\textrm{GitHub}$@$\href{https://github.com/SuperKuroko}{\textrm{SuperKuroko}}$

$\textrm{LeetCode}$@$\href{https://leetcode-cn.com/u/kuroko177/}{\textrm{kuroko177}}$

$\textrm{Last Modified: 2020-11-18 12:55}$