Es scheint, dass Codierungstests in Ingenieurinterviews im Ausland durchgeführt werden, und in vielen Fällen besteht die Hauptsache darin, bestimmte Funktionen und Klassen entsprechend dem Thema zu implementieren.
Als Gegenmaßnahme scheint eine Website namens Let Code Maßnahmen zu ergreifen.
Eine Site, die algorithmische Leistung trainiert, die Codierungstests standhält, über die früh gesprochen wird.
Ich denke, es ist besser, die Algorithmuskraft eines Menschen zu haben, also werde ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.
Letztes Mal Leet Code Tag 19 ab Null "121. Beste Zeit zum Kaufen und Verkaufen von Aktien"
Grundsätzlich möchte ich die einfache Akzeptanz in absteigender Reihenfolge lösen.
Es dauerte 20 Mal, was für mich ungewöhnlich ist, der es satt hat. Überraschung.
Twitter Ich mache es.
Der Schwierigkeitsgrad ist Mittel. Eine der 100 beliebtesten Fragen.
Es war ein sehr interessantes Problem zu lösen, also versuchen Sie es bitte zu lösen.
Es werden zwei Listen angegeben: die Menge des mit Benzin betankten "Gases" und die "Kosten", die die Menge an Benzin angeben, die verbraucht wird, um zu diesem Punkt zu gelangen.
Zusätzlich erhielten Sie ein Auto mit einem Benzintank mit unendlicher Kapazität. Es kostet "cost [i]", von Station i zur nächsten Station zu wechseln (i + 1). Der Gastank ist zu Beginn leer, und wenn es sich um eine einwöchige Patrouille im Uhrzeigersinn handelt, wird der ** Startstationsindex ** zurückgegeben, andernfalls wird "-1" zurückgegeben.
Bitte beachten Sie die folgenden Punkte.
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.
Dies ist ein Beispiel für den Start ab Station 3. Die zu Beginn gehaltene Benzinmenge beträgt 3, da das "Gas" von Station 3 3 beträgt. In diesem Fall wird der Index "3" von Station 3 zurückgegeben, da dies auch dann möglich ist, wenn er die ganze Zeit von diesem Punkt zurückkehrt.
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.
Derzeit sind drei Variablen als variable Kandidaten erforderlich: "Tank", der die Benzinmenge verwaltet, "Start", der den Startpunkt angibt, wenn das Rennen beendet ist, und "cur", der die Benzinmenge angibt, die am aktuellen Standort gehalten wird. Der Grund, warum "Tank" und "Cur" getrennt werden, besteht darin, den Fall zu verwalten, in dem der Wert von "Cur" negativ wird. Das bedeutet, dass Sie das Rennen nicht beenden können, und was Sie in diesem Fall tun, ist ein wichtiger Teil der Lösung dieses Problems.
Außerdem habe ich wie folgt geschrieben.
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.
Es ist korrekt, indem Sie "cur" überprüfen, indem Sie beim Drehen mit "for" -Anweisung verwenden. Wenn es negativ ist, weisen Sie "cur" 0 zu und weisen Sie "start" "i + 1" zu. Die Startposition wird jetzt als Index zurückgegeben.
Ich dachte nach dem Bestehen, aber in diesem Satz ist der letzte Zweig etwas überflüssig. Wenn Sie wie Python schreiben
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
Ist
return -1 if tank < 0 else start
Ich habe versucht, es umzuschreiben, weil es gleich ist. Es ist ziemlich erfrischend. Wenn Sie es also schreiben können, ist es besser.
Wenn es eine andere gute Lösung gibt, werde ich sie hinzufügen.
Recommended Posts