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.

Notice

The solution is guaranteed to be unique.

Example

Given 4 gas stations with gas[i]=[1,1,3,1], and the cost[i]=[2,2,1,1]. The starting gas station's index is 2.

题目链接

1. Naive Solution:

   • 枚举起点，判断是否可行
   • 时间复杂度： O(n^2)

2. Golden Solution:

   • 我们可以观察到，假设 i 到 j 是不可行的，而 i 到 j之前都是可行的，那么说明i+1到j也是不可行的，同理任何从k到j都是不可行的(i < k <= j), 所以一旦发现不可行，i 就变为 j + 1。
   • 时间复杂度： O(n)

参考代码：

Naive Solution:

class Solution {
public:
   /**
     * @param gas: a vector of integers
     * @param cost: a vector of integers
     * @return: an integer 
     */
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        // write your code her
        int n = gas.size();
        for (int i = 0; i < n; ++ i) {
            int val = 0;
            for (int j = 0; j < n; ++ j) {
                val += gas[(i + j) % n];
                val -= cost[(i + j) % n];
                if (val < 0) break;
            }
            if (val >= 0) return i;
        }
        return -1;
    }
}

Golden Solution:

class Solution {
public:
   /**
     * @param gas: a vector of integers
     * @param cost: a vector of integers
     * @return: an integer 
     */
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        // write your code her
        int n = gas.size();
        int i = 0;
        while (i < n) {
            int sum = 0;
            for (int j = 0; j < n; ++ j) {
                sum += gas[(i + j) % n];
                sum -= cost[(i + j) % n];
                if (sum < 0) {
                    i = i + j + 1;
                    break;
                }
            }
            if (sum >= 0) return i;
        } 
        return -1;
    }
};