leetcode每日一题：134 加油站
leetcode每日一题：134 加油站
题目地址： https://leetcode-cn.com/problems/gas-station/
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
说明:
如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。
示例 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 可为起始索引。
示例 2:
输入:
gas = [2,3,4]
cost = [3,4,3]
输出: -1解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
思路：
把这个题理解成环形图就可以。
每个节点表示添加的油量，每条边表示消耗的油量。题目的意思就是问我们从哪个节点出发，还可以回到该节点。只能顺时针方向走。
每个节点表示添加的油量，每条边表示消耗的油量。题目的意思就是问我们从哪个节点出发，还可以回到该节点。只能顺时针方向走。
解法一：暴力解法
考虑暴力破解，一方面是验证下自己对题目的理解是否正确，另一方面后续的优化也可以从这里入手。
考虑从第 0 个点出发，能否回到第 0 个点。
考虑从第 1 个点出发，能否回到第 1 个点。
考虑从第 2 个点出发，能否回到第 2 个点。
... ...
考虑从第 n 个点出发，能否回到第 n 个点。
由于是个圆，得到下一个点的时候我们需要取余数。
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
n = len(gas) # 获得加油站的个数
for i in range(n): # 遍历从每个加油站试一下
j = i # 下一里程所处的index
remain_gas = gas[i] # 当前剩余的油
while(remain_gas-cost[j]) >= 0: # 当前油量-旅程需要花费的油量，如果>= 0表示能继续往下走
remain_gas = remain_gas - cost[j] + gas[(j + 1) %n]; # 减去花费的加上新的点的补给
j = (j + 1) % n # j 回到了 i
if j == i:
return i
return -1解法二 优化尝试
暴力破解慢的原因就是会进行很多重复的计算。比如下边的情况：
假设当前在考虑 i, 先初始化 j = i
* * * * * *
^
i
^
j
随后 j 会进行后移
* * * * * *
^ ^
i j
继续后移
* * * * * *
^ ^
i j
继续后移
* * * * * *
^ ^
j i
此时 j 又回到了第 0 个位置，我们在之前已经考虑过了这个位置。
如果之前考虑第 0 个位置的时候，最远到了第 2 个位置。
那么此时 j 就可以直接跳到第 2 个位置，同时加上当时的剩余汽油，继续考虑
* * * * * *
^ ^
j i
利用上边的思想我们可以进行一个优化，就是每考虑一个点，就将当前点能够到达的最远距离记录下来，同时到达最远距离时候的剩余汽油也要记下来。
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
n = len(gas)
# 记录能到的最远距离
farIndex = [-1] * n
# 记录到达最远距离时候剩余的汽油
farIndexRemain = [0] * n
for i in range(n):
j = i
remain_gas = gas[i]
while (remain_gas - cost[j] >= 0):
# 到达下个点后的剩余的油
remain_gas = remain_gas - cost[j];
j = (j + 1) % n
# 判断之前有没有考虑过这个点
if farIndex[j] != -1:
# 加上当时剩余的汽油
remain_gas = remain_gas + farIndexRemain[j]
# j 进行跳跃
j = farIndex[j]
else:
# 加上当前点的补给
remain_gas = remain_gas + gas[j]
if j == i:
return i
# 记录当前点最远到达哪里
farIndex[i] = j;
# 记录当前点的剩余
farIndexRemain[i] = remain_gas
return -1
解法三 优化尝试二
我们考虑一下下边的情况
* * * * * *
^ ^
i j
当考虑 i 能到达的最远的时候，假设是 j。
那么 i + 1 到 j 之间的节点是不是就都不可能绕一圈了？
假设 i + 1 的节点能绕一圈，那么就意味着从 i + 1 开始一定能到达 j + 1。
又因为从 i 能到达 i + 1，所以从 i 也能到达 j + 1。
但事实上，i 最远到达 j 。产生矛盾，所以 i + 1 的节点一定不能绕一圈。同理，其他的也是一样的证明。
所以下一次的 i 我们不需要从 i + 1 开始考虑，直接从 j + 1 开始考虑即可。
还有一种情况，就是因为到达末尾的时候，会回到 0。
如果对于下边的情况。
* * * * * *
^ ^
j i
如果 i 最远能够到达 j ，根据上边的结论 i + 1 到 j 之间的节点都不可能绕一圈了。想象成一个圆，所以 i 后边的节点就都不需要考虑了，直接返回 -1 即可。
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
n = len(gas)
for i in range(n):
j = i
remain_gas = gas[i]
while (remain_gas - cost[j]) >= 0:
# 减去花费的加上新的点的补给
remain_gas = remain_gas - cost[j] + gas[(j + 1) % n]
j = (j + 1) % n;
if j == i:
return i
# 最远距离绕到了之前，所以 i 后边的都不可能绕一圈了
if j < i:
return -1
# i 直接跳到 j，外层 for 循环执行 i++，相当于从 j + 1 开始考虑
i = j
return -1腾讯云开发者
