gas_station
1# @leet start 2class Solution: 3 def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int: 4 """ 5 This question asks if we can make a circuit around an array if 6 we're given an array of gas at a station and the cost to make it to the next 7 station. 8 9 To find out whether or not this is even feasible, the sum of the gas costs 10 must be greater than the sum of the costs. If this is not the case, a 11 complete circuit is not doable, and thus, we should return -1. 12 13 If there is more gas than is required to be spent, we can complete the circuit. 14 We then need to figure out the position to start. 15 To do this, we can start out at the first index, and check when we have 16 to spend more gas than we have available to us to make it to the next station. 17 If that's the case, we continue on. If our current gas ever dips below 0, 18 we know that we cannot make a circuit from the current index, so we 19 assume that we can start at the index one past where we are, since 20 that path could possibly be the starting index that solves the circuit. 21 """ 22 total_gain, curr_gain, answer = 0, 0, 0 23 24 for i, (gas_amount, gas_cost) in enumerate(zip(gas, cost)): 25 gain = gas_amount - gas_cost 26 total_gain += gain 27 curr_gain += gain 28 29 if curr_gain < 0: 30 curr_gain = 0 31 answer = i + 1 32 33 return answer if total_gain >= 0 else -1 34 35 36# @leet end 37 38 39def test(): 40 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int: 5 """ 6 This question asks if we can make a circuit around an array if 7 we're given an array of gas at a station and the cost to make it to the next 8 station. 9 10 To find out whether or not this is even feasible, the sum of the gas costs 11 must be greater than the sum of the costs. If this is not the case, a 12 complete circuit is not doable, and thus, we should return -1. 13 14 If there is more gas than is required to be spent, we can complete the circuit. 15 We then need to figure out the position to start. 16 To do this, we can start out at the first index, and check when we have 17 to spend more gas than we have available to us to make it to the next station. 18 If that's the case, we continue on. If our current gas ever dips below 0, 19 we know that we cannot make a circuit from the current index, so we 20 assume that we can start at the index one past where we are, since 21 that path could possibly be the starting index that solves the circuit. 22 """ 23 total_gain, curr_gain, answer = 0, 0, 0 24 25 for i, (gas_amount, gas_cost) in enumerate(zip(gas, cost)): 26 gain = gas_amount - gas_cost 27 total_gain += gain 28 curr_gain += gain 29 30 if curr_gain < 0: 31 curr_gain = 0 32 answer = i + 1 33 34 return answer if total_gain >= 0 else -1
def
canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
4 def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int: 5 """ 6 This question asks if we can make a circuit around an array if 7 we're given an array of gas at a station and the cost to make it to the next 8 station. 9 10 To find out whether or not this is even feasible, the sum of the gas costs 11 must be greater than the sum of the costs. If this is not the case, a 12 complete circuit is not doable, and thus, we should return -1. 13 14 If there is more gas than is required to be spent, we can complete the circuit. 15 We then need to figure out the position to start. 16 To do this, we can start out at the first index, and check when we have 17 to spend more gas than we have available to us to make it to the next station. 18 If that's the case, we continue on. If our current gas ever dips below 0, 19 we know that we cannot make a circuit from the current index, so we 20 assume that we can start at the index one past where we are, since 21 that path could possibly be the starting index that solves the circuit. 22 """ 23 total_gain, curr_gain, answer = 0, 0, 0 24 25 for i, (gas_amount, gas_cost) in enumerate(zip(gas, cost)): 26 gain = gas_amount - gas_cost 27 total_gain += gain 28 curr_gain += gain 29 30 if curr_gain < 0: 31 curr_gain = 0 32 answer = i + 1 33 34 return answer if total_gain >= 0 else -1
This question asks if we can make a circuit around an array if we're given an array of gas at a station and the cost to make it to the next station.
To find out whether or not this is even feasible, the sum of the gas costs must be greater than the sum of the costs. If this is not the case, a complete circuit is not doable, and thus, we should return -1.
If there is more gas than is required to be spent, we can complete the circuit. We then need to figure out the position to start. To do this, we can start out at the first index, and check when we have to spend more gas than we have available to us to make it to the next station. If that's the case, we continue on. If our current gas ever dips below 0, we know that we cannot make a circuit from the current index, so we assume that we can start at the index one past where we are, since that path could possibly be the starting index that solves the circuit.
def
test():