网站建设 壹起航,广告传媒网站模板,长春做网站企业,网站欢迎页代码加油站 文章目录 加油站1 题目描述2 思路3 解题方法 1 题目描述
https://leetcode.cn/problems/gas-station/
在一条环路上有 n 个加油站#xff0c;其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车#xff0c;从第 i 个加油站开往第 i1 个加油站需要消…加油站 文章目录 加油站1 题目描述2 思路3 解题方法 1 题目描述
https://leetcode.cn/problems/gas-station/
在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。
给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回 -1 。如果存在解则 保证 它是 唯一 的。
2 思路 正如大部分大佬所言需要找到最小值所在的点。但是他们的代码写得有些含糊我希望可以使用一种更加符合直觉的方式。 我们假设从i号加油站出发然后用一张折线图表示到达每个加油站最终返回i时的剩余油量。x轴为加油站号y轴为剩余油量。一开始的时候剩余油量为0。首先来看一种可能的情况
gas [4, 3, 1, 2, 7, 4]
cost [1, 2, 7, 3, 2, 5]这里我们提供代码来表示从不同的站点出发到达不同站点时候的剩余油量
gas [4,3,1,2,7,4]
cost [1,2,7,3,2,5]
# 绘制
fig, axs plt.subplots(1, 6, figsize(20, 3))
for s in range(len(gas)):left_gas [0 for _ in range(len(gas))]for i in range(len(gas)):left_gas[i] (left_gas[i-1] if i 0 else 0) gas[(s i) % len(gas)] - cost[(s i) % len(gas)]left_gas.insert(0, 0)x [(s i) % len(gas) for i in range(len(gas))]x.append(s)axs[s].plot(range(len(gas) 1), left_gas)axs[s].scatter(range(len(gas) 1), left_gas)# 设置 x 轴刻度及标签axs[s].set_xticks(np.arange(len(gas) 1))axs[s].set_xticklabels(x)# 绘制0刻度线axs[s].axhline(y0, colorr, linestyle-)# 将最低点标记出来最低点的索引为left_gas.index(min(left_gas))axs[s].scatter(left_gas.index(min(left_gas)), min(left_gas), colorr)
plt.show()你可以明显地看到从哪里出发可以安全地开一圈了。红线为0刻度线红色点为最小点
那么我们再举一个不可能开一圈的例子
gas [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # 0~9号加油站的油量
cost [10, 9, 8, 7, 6, 5, 4, 3, 2, 11] # 0~9号加油站到下一站的消耗其对应图像为 我这里也提供对应的绘图代码
import matplotlib.pyplot as plt
import numpy as npgas [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # 0~9号加油站的油量
cost [10, 9, 8, 7, 6, 5, 4, 3, 2, 11] # 0~9号加油站到下一站的消耗# 绘制
# fig, axs plt.subplots(1, 10, figsize(20, 3))
# 上下两行每行5个子图
fig, axs plt.subplots(2, 5, figsize(20, 6))
for s in range(len(gas)):left_gas [0 for _ in range(len(gas))]for i in range(len(gas)):left_gas[i] (left_gas[i - 1] if i 0 else 0) gas[(s i) % len(gas)] - cost[(s i) % len(gas)]left_gas.insert(0, 0)x [(s i) % len(gas) for i in range(len(gas))]x.append(s)# 设置 x 轴刻度及标签axs[int(s / 5)][s % 5].set_xticks(np.arange(len(gas) 1))axs[int(s / 5)][s % 5].set_xticklabels(x)axs[int(s / 5)][s % 5].plot(range(len(gas) 1), left_gas)axs[int(s / 5)][s % 5].scatter(range(len(gas) 1), left_gas)# 绘制0刻度线axs[int(s / 5)][s % 5].axhline(y0, colorr, linestyle-)# 将最低点标记出来最低点的索引为left_gas.index(min(left_gas))axs[int(s / 5)][s % 5].scatter(left_gas.index(min(left_gas)), min(left_gas), colorr)# 最低点设置垂直虚线只往下画axs[int(s / 5)][s % 5].axvline(xleft_gas.index(min(left_gas)), colorr, linestyle--)
plt.show()什么情况下能转完一圈 即总油量大于等于总耗油量。
3 解题方法
其实就是根据直觉创建一个长度为gas.length 1参考上面的图走一圈回来相当于一共gas.length1个站点的数组left_gas剩余油量i位置初始为0表示为在站点i出发时剩余油量或者说初始油量为0。
每两个站点之间的增加或者减少量是一定的即任何两点之间连线的斜率是不变的gas[i] - cost[i]只要我们让最低值大于等于0就可以保证走一圈。怎么让最低值大于等于0只要我们让最低值为出发点不就能保证其为0了也就是能够保证最低点大于等于0。
所以我们只需要找到最低点即可。
我们设置小车从0号站点出发然后我们计算每个站点的剩余油量
class Solution(object):def canCompleteCircuit(self, gas, cost):res [0 for _ in range(len(gas) 1)] # 剩余油量为什么是len(gas) 1参考图中的x轴min_index 0 # 初始站点min_left 0 # 初始油量for i in range(len(gas)):res[i 1] res[i] gas[i] - cost[i] # 例如站点1的时候剩余油量res[0] gas[0] - cost[0]if res[i 1] min_left: # 记录最低点的值和索引min_left res[i 1]min_index i 1return -1 if res[-1] 0 else min_index # 到达最最终点的时候相当于所有的gas相加然后减去所有的cost# 如果返回开头的时候剩余油量小于0则返回-1相比之下leetcode很多大佬的代码让我有点迷茫没有说大佬写得不好只是我有点难理解
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int sum 0 ;int min_num Integer.MAX_VALUE;int min_index 0;for ( int i 0 ; i gas.length ; i ){sum gas[i] - cost[i];if(summin_num gas[(i1)%gas.length] 0){min_index i;min_num sum;}}return sum 0 ? -1 : (min_index 1 ) % gas.length;}
}
