[Leetcode][python/Java]Gas Station/加油站

迷南。 2022-06-05 04:15 147阅读 0赞

## 题目大意 ##

Gas Station

## 解题思路 ##

贪心法。但其实需要证明，证明详见：

http://bookshadow.com/weblog/2015/08/06/leetcode-gas-station/

**看懂证明，才能看懂代码**

结论1：若从加油站A出发，恰好无法到达加油站C（只能到达C的前一站）。则A与C之间的任何一个加油站B均无法到达C。

反证法：

> 假设从加油站A出发恰好无法到达加油站C，但是A与C之间存在加油站B，从B出发可以到达C。  
> 而又因为从A出发可以到达B，所以A到B的油量收益（储油量 - 耗油量）为正值，进而可以到达C。  
> 推出矛盾，假设不成立。

换一种理解方式：

> 如果到中间的某个位置, 剩余的油量为负了, 那么说明之前累积剩下的油量不够从这一站到下一站了. 那么就从下一站从新开始计数. 为什么是下一站, 而不是之前的某站呢? 因为第一站剩余的油量肯定是大于等于0的, 然而到当前一站油量变负了, 说明从第一站之后开始的话到当前油量只会更少而不会增加. 也就是说从第一站之后, 当前站之前的某站出发到当前站剩余的油量是不可能大于0的. 所以只能从下一站重新出发开始计算从下一站开始剩余的油量, 并且把之前欠下的油量也累加起来, 看到最后剩余的油量是不是大于欠下的油量.

结论2：若储油量总和sum(gas) >= 耗油量总和sum(cost)，**则问题一定有解**。

## 代码 ##

### Python ###

class Solution:
        # @param {integer[]} gas
        # @param {integer[]} cost
        # @return {integer}
        def canCompleteCircuit(self, gas, cost):
            start = sums = 0
            for x in range(len(gas)):
                sums += gas[x] - cost[x]
                if sums < 0:
                    start, sums = x + 1, 0
            return start if sum(gas) >= sum(cost) else -1

class Solution(object):
        def canCompleteCircuit(self, gas, cost):
            """
            :type gas: List[int]
            :type cost: List[int]
            :rtype: int
            """
            if sum(gas) < sum(cost):
                return -1
            min_sum, min_index, total = 0, 0, 0
            
            for i in range(len(gas)):
                print '----'
                total += gas[i] - cost[i]
                if min_sum > total:
                    print 'gg'
                    min_sum = total
                    min_index = i + 1
                print i, 'total:', total, 'min_sum:', min_sum, 'min_index:', min_index
                    
            if total < 0:
                return -1 
            else:
                return min_index

### Java ###

class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int n = gas.length;
            int total_tank = 0;
            int curr_tank = 0;
            int starting_station = 0;
            
            for (int i = 0; i < n; ++i) {
              total_tank += gas[i] - cost[i];
              curr_tank += gas[i] - cost[i];
              // If one couldn't get here,
              if (curr_tank < 0) {
                // Pick up the next station as the starting one.
                starting_station = i + 1;
                // Start with an empty tank.
                curr_tank = 0;
              }
            }
            return total_tank >= 0 ? starting_station : -1;
        }
    }

## 总结 ##