德国网站域名后缀,wordpress好的插件,网站建设综合实训报告,网站服务器题目描述
在一条环路上有 n 个加油站#xff0c;其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车#xff0c;从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发#xff0c;开始时油箱为空。
给定两个整数数组 gas…题目描述
在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。
给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回 -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 可为起始索引。
思路分析 首先我们要判断一个加油站是否能到下一个加油站需要看gas[j]cost[j]所以我们关注的点应该是gas[j]-cost[j]。所以我们先计算出经过每个站点油箱是增加油量还是减少油量。remainder[j]gas[j]-cost[j]。 然后我们判断什么时候汽车无法绕一圈呢也就是汽油不够呢。简单举几个例子就知道只有在remainder[j]的总和是负数的时候才会出现。比如说remianer[3,-1,0,-1,0]总和是1即使大部分是0或者是负数但还是能找到个起点然后绕一圈。 最后的重点就是找出这唯一的起点题目中说解唯一。
思路一联想 最大子数组和 一开始我想到了一个类似的题目最大子数组和可以用到贪心、前缀和或者动态规划三种思路解决。但是这个题目求的是最大子数组和但是本题求的是索引。改写起来的复杂度为O(2N)。
class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int:column len(gas)remainder [0] * columnfor i in range(column): #计算经过每个加油站油箱的增量remainder[i] gas[i] - cost[i]if sum(remainder) 0:return -1max_value 0result 0index 0max_index 0flag True#这里是2*column因为要考虑是环路也就是循环数组for i in range(2*column):if flag: #是否要记录当前起始下标index i%columnflag Falseresult remainder[i%column]if result 0: #从当前下标无法绕一圈result 0# 再次开始记录下标flag Trueif result max_value: #记录这个可能的索引max_value resultmax_index indexreturn max_index
思路二贪心算法 看到leetcode官方解只需遍历一遍即可找出起始下标。所以对上面的代码修改如果当前从第index个加油站出发到第right个加油站时油箱为负数时那么即使从index-right之间的任意加油站出发同样无法绕过第right个加油站。比如说你选了第x个加油站(indexxright)其实从index到x之间油箱剩余的油量肯定是大于等于0的不然不可能到达第x个加油站。所以从index都到不了right更别说中间的其他加油站出发了。 所以当遇到油量为负数时我们直接可以跳过起始和末尾这些加油站从right1的加油站开始重新遍历结算。
class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int:column len(gas)remainder [0] * columnfor i in range(column):remainder[i] gas[i] - cost[i]if sum(remainder) 0:return -1# 如果总和不为负数那么一定可以找到从一个点开始能遍历全部qianzhui 0index 0while index column:for j in range(index, column):qianzhui remainder[j]if qianzhui 0: # 汽油不够了qianzhui 0index j1breakelse:return index
