It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.
As a countermeasure, it seems that a site called Let Code will take measures.
A site that trains algorithmic power that can withstand coding tests that are often done in the home.
I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.
Leet Code Table of Contents Starting from Zero
Last time Leet Code Day 19 "121. Best Time to Buy and Sell Stock" starting from zero
Basically, I would like to solve the easy acceptance in descending order.
It lasted 20 times, which is unusual for me, who is tired of it. surprise.
Twitter I'm doing it.
The difficulty level is Medium. One of the Top 100 Liked Questions.
It was a very interesting problem to solve, so please try to solve it.
Two lists are given: the amount of gasoline refueled gas and the amount of gasoline consumed to move to that point cost.
In addition to them you were given a car with a petrol tank with infinite capacity.
It costs cost [i] to move from station i to the next station (i + 1). At the start, the petrol tank is empty, and if it patrolls clockwise for a week, it returns the ** start station index **, otherwise it returns -1.
Please note the following points.
--If a solution exists, it is unique. --Both input arrays are not empty and are the same length. --Each element of the input array is a non-negative integer.
Input: gas = [1,2,3,4,5] cost = [3,4,5,1,2]
Output: 3
Explanation: Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 4. Your tank = 4 - 1 + 5 = 8 Travel to station 0. Your tank = 8 - 2 + 1 = 7 Travel to station 1. Your tank = 7 - 3 + 2 = 6 Travel to station 2. Your tank = 6 - 4 + 3 = 5 Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3. Therefore, return 3 as the starting index.
This is an example when starting from station 3.
The amount of gasoline held at the start is 3 because the gas of station 3 is 3. In this case, the index 3 of station 3 is returned because it can be done even if it returns from that point all the time.
Example 2:
Input: gas = [2,3,4] cost = [3,4,3]
Output: -1
Explanation: You can't start at station 0 or 1, as there is not enough gas to travel to the next station. Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 0. Your tank = 4 - 3 + 2 = 3 Travel to station 1. Your tank = 3 - 3 + 3 = 3 You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3. Therefore, you can't travel around the circuit once no matter where you start.
For the time being, three variables are required as variable candidates: tank, which manages the amount of gasoline, start, which indicates the starting point if the vehicle can be completed, and cur, which indicates the amount of gasoline held at the current location.
The reason why tank and cur are separated is to manage the case where the value of cur becomes negative. That means that you can't finish the race, and what you do in that case will be an important part of solving this problem.
In addition, I wrote as follows.
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
tank,start,cur = 0,0,0
for i in range(len(gas)):
cur += (gas[i] - cost[i])
tank += (gas[i] - cost[i])
if cur < 0:
cur = 0
start = i + 1
if tank < 0:
return -1
else:
return start
# Runtime: 56 ms, faster than 53.48% of Python3 online submissions for Gas Station.
# Memory Usage: 14.6 MB, less than 6.25% of Python3 online submissions for Gas Station.
It is correct by checking cur by if while turning with a for statement, substituting 0 for cur if it is negative, and substituting ʻi + 1 for start`. The start position is now returned as an index.
I thought after passing, but in this sentence, the last branch is a little redundant. If you write like Python
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
tank,start,cur = 0,0,0
for i in range(len(gas)):
cur += (gas[i] - cost[i])
tank += (gas[i] - cost[i])
if cur < 0:
cur = 0
start = i + 1
return -1 if tank < 0 else start
# Runtime: 52 ms, faster than 76.94% of Python3 online submissions for Gas Station.
# Memory Usage: 14.9 MB, less than 6.25% of Python3 online submissions for Gas Station.
In python
if tank < 0:
return -1
else:
return start
Is
return -1 if tank < 0 else start
I tried to rewrite it because it is equal. It's pretty refreshing, so if you can write it, this is better.
If there is another good solution, I will add it.
Recommended Posts