跳转至

2022/01/20 - 134. Gas Station

134. Gas Station - Medium

Description

134. Gas Station

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

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.

其实就是一道找规律的数组题，首先能想出来的办法就是暴力遍历，将每一个位置都当成是第一个station，看是否可以转一圈回到这个地方。但是算法的时间复杂度是O(n)，所以TLE了。那么考虑一下这种方法有没有优化的余地呢？ 因为这个暴力穷举的过程中，变化的量只有起点和当前油箱的油量。这两种状态的组合一定有不下n^2种，所以没有任何优化空间。

Solution

图像

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        // 利用一个sum变量，记录在每个点时的总油量
        // 用一个minSum记录路途中sum的最小值
        int sum = 0, minSum = 0;
        int start = 0;
        for (int i = 0; i < n; i++) {
            sum += gas[i] - cost[i];
            if (sum < minSum) {
                start = i + 1;
                minSum = sum;
            }
        }
        if (sum < 0) return -1;
        return start == n ? 0 : start;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
object Solution {
    def canCompleteCircuit(gas: Array[Int], cost: Array[Int]): Int = {
        val n = gas.length
        var sum: Int = 0
        var minSum: Int = 0
        var start: Int = 0
        for (i <- (0 until n)) {
            sum = sum + gas(i) - cost(i)
            if (sum < minSum) {
                start = i + 1
                minSum = sum
            }
        }
        if (sum < 0) return -1
        if (start == n) 0 else start
    }
}

贪心算法

其实是和图像解法差不多的，就是思路不太一样。

假设从i开始为起点，到j时，总油量小于0了，说明i无法到j，这也侧面说明了i和j之间的点都无法走到j，例如k为i和j之间的点，i到k的时候总油量一定是大于等于0的，如果从k点开始，起始油量一定是0，那么想一下，从i到k的时候油量大于零都无法到达j，那么k开始油量为0，就更不可能到达j了。

所以当遍历到一个点时，当前的邮箱总量小于0，那就就让起始点start为i+1，然后tank（总油量）重新设置为0。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += gas[i] - cost[i];
        }
        // 总油量小于0，说明无解
        if (sum < 0) return -1;
        int tank = 0, start = 0;
        for (int i = 0; i < n; i++) {
            tank += gas[i] - cost[i];
            if (tank < 0) {
                tank = 0;
                start = i + 1;
            }
        }
        return start == n ? 0 : start;
    }
}

评论

回到页面顶部