算法设计与分析-Week7

发表于 | 更新于

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 in the clockwise direction, otherwise return -1.

Note:

  • If there exists a solution, it is guaranteed to be unique.
  • Both input arrays are non-empty and have the same length.
  • Each element in the input arrays is a non-negative integer.

Example 1:

Input:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input:
gas = [2,3,4]
cost = [3,4,3]
Output: -1
Explanation:
You can’t start at station 0 or 1, as there is not enough gas to travel to the next station.
Let’s start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can’t travel around the circuit once no matter where you start.

解题思路

本题要找到一个加油站的下标，使得从这个加油站出发，走一圈可以回到这个加油站。

  • 算法一：遍历所有加油站，从某个加油站开始，向前遍历一圈加油站，若能回到原点，则返回该加油站的下标；否则以下一个加油站为起点，继续向前遍历一圈加油站，直到找到能够返回原点的加油站或者遍历完所有加油站。时间复杂度为\(O(n^2)\)。
  • 算法二：对以上算法进行改进，没有必要遍历所有的加油站。例如从某一个加油站i出发，到达加油站j之前停了下来，那么加油站i与j之间的所有加油站都无法到达j，那么这之间的加油站就不需要遍历了，下个起点可以选择加油站j+1，整个算法只需要遍历一遍加油站，时间复杂度为\(O(n)\)。

源代码

  • 算法一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    class Solution {
    public:
        int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
            int index = 0;
            int n = gas.size();
            vector<int> remain;
            int sum = 0;
            for(int i = 0; i < n; i++) {
                remain.push_back(gas[i] - cost[i]);
                sum += gas[i] - cost[i];
            }
            if(sum < 0) return -1;
            while(index < n) {
                if(remain[index] < 0) {
                    index++;
                    continue;
                }
                sum = remain[index];
                int cur = index + 1;
                while((cur %= n) != index) {
                    sum += remain[cur];
                    if(sum < 0) break;
                    cur++;
                }
                if(cur == index) return index;
                index++;
            }
            return -1;
        }
    };

  • 算法二

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution {
    public:
        int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
            int i, j, n = gas.size();

            /*
             * If start from i, stop before station x -> no station k from i + 1 to x - 1 can reach x.
             * Bcoz if so, i can reach k and k can reach x, then i reaches x. Contradiction.
             * Thus i can jump directly to x instead of i + 1, bringing complexity from O(n^2) to O(n).
             */
            // start from station i
            for (i = 0; i < n; i += j) {
                int gas_left = 0;
                // forward j stations
                for (j = 1; j <= n; j++) {
                    int k = (i + j - 1) % n;
                    gas_left += gas[k] - cost[k];
                    if (gas_left < 0)
                        break;
                }
                if (j > n)
                    return i;
            }

            return -1;
        }
    };
0%