leetcode134gas-station 2020-11-1

leetcode134. 加油站

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

思路：
汽车在当前站获取gas[i]汽油，并需要消耗cost[i]汽油到达下一站，必须保证到达下一站时存油非负。因此，可将gas[i]与cost[i]做差得到一个数组delta，例子中对应的delta为[-2,-2,-2,3,3]。因为初始汽油量为0，那么问题转化为，我们需要在delta中找到一个起点，保证从起点出发的任一路段和非负

解法1：
暴力模拟
对delta的每个位置，模拟走完一个环路。对于每一个起点，如果过程中出现负数和的情况，则从该起点出发不可环行一圈

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        l = len(gas)
        delta = [gas[i]-cost[i] for i in range(l)]

        for i in range(l):
            # i位置为环路起点
            temp_delta = delta[i:] + delta[:i]
            total = 0
            # 检查temp_delta每一段的和是否为负
            for j in range(l):
                total += temp_delta[j]
                if total < 0:
                    break
            else:
                return i
        return -1

解法2：
在暴力模拟的基础上优化
暴力模拟需要check delta每一个位置为起点的情况，实际上不需要。假设站点0到站点k一路都正常，但到达不了站点k+1，这时如果我们再尝试区间[1, k]的站点为起点就多余了——从0开始都到不了k+1，从中间任意的站点 i 更加到不了k+1，因为少了 0-i 路段的汽油存储
因此，站点s为起点，如果发现站点k无法到达，起点应该重新定为k+1，而不是s+1，因为从[s, k]中的任一站点出发都无法到达k
对于delta而言，当序列和开始为负时，从下一位置重新计算序列和

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # 汽车行驶若干站点后gas < 0，则从下一站点重新出发
        l = len(gas)
        delta = [gas[i] - cost[i] for i in range(l)]
        i = 0
        while i < l:
            cur_gas = 0
            for j in range(l):
                cur_gas += delta[(i+j) % l]
                # 汽车行驶若干站点后gas < 0，则从下一站点重新出发
                if cur_gas < 0:
                    i = i + j + 1
                    break
            else:
                return i
        return -1

解法3：
if sum(gas) >= sum(cost)，那么必然可以从某一站出发完成环行
互为充要：sum(gas) >= sum(cost) <=> 可以从某一站出发完成环行

下面证明 sum(gas) >= sum(cost) => 可以从某一站出发完成环行

反证法：
假设 sum(gas) >= sum(cost) ，则从任意一站出发都不能完成环行；
这里我们假定站点0不可达站点k，那么0-k这一段内有sum(sub_gas) < sum(sub_cost)，且这一段内的任意一点都不可作为起点，新的尝试起点为站点k+1，而站点k+1又不可达站点kk，那么k+1-kk这一段又有sum(sub_gas) < sum(sub_cost)，且段内的任意一点都不可作为起点——于是，每一段都有sum(sub_gas) < sum(sub_cost)，加起来就得到sum(gas) < sum(cost) ，与sum(gas) >= sum(cost) 矛盾
因此，sum(gas) >= sum(cost) => 可以从某一站出发完成环行
可参考https://leetcode-cn.com/problems/gas-station/solution/shou-hua-tu-jie-liang-ge-guan-jian-jie-lun-de-jian/

也可以正向理解，如果sum(gas) >= sum(cost) ，那么我总可以贪心地找到一个起点，从那里开始疯狂存油，从而保证后面的消耗

即 sum(delta) >= 0 => 可以从某一站出发完成环行，这样问题就简单很多了

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        l = len(gas)
        delta = [gas[i]-cost[i] for i in range(l)]
        
        # 计算sum(delta)
        total = 0
        # 计算当前油量
        cur = 0
        start_index = 0
        for i in range(l):
            cur += delta[i]
            total += delta[i]
            if cur < 0:
                cur = 0
                # 更新起点
                start_index = i + 1
        if total >= 0:
            return start_index
        return -1