首页 > 代码库 > 134. Gas Station
134. Gas Station
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station‘s index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.
Brutal way O(n^2) ,计算每一个点，做一边sum gas and cost 会超时tle
public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int step = gas.length; int start = 0; for(int i = 0; i < step; i++){ int temp = start; int station = 0; int sumGas = 0; int sumCost = 0; while(sumCost <= sumGas && station < step){ sumGas += gas[start%step]; sumCost += cost[start%step]; start ++; station ++; } if(station >= step && sumGas >= sumCost) return temp; else if(station < step) start = temp + 1; } return -1; }}
最优解：
设一个total ＝ sum （gas[i] - cost[i]）
if(total < 0) return -1
if(total > 0) 一定存在一个解；
用sum ＝ gas[i] + cost[i]
if(sum < 0) i - > i+1 sum要重新算
if(sum > 0) sum 累加
public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int total = 0; int sum = 0; int start = 0; for(int i = 0; i < gas.length; i++){ total += gas[i] - cost[i]; } if(total < 0) return -1; for(int i = 0; i < gas.length; i++){ if(sum >= 0){ sum += gas[i] - cost[i]; } else{ sum = gas[i] - cost[i]; start = i; //记录新的起点 } } return start; }}
134. Gas Station
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。