Il semble que des tests de codage soient menés à l'étranger lors d'entretiens d'ingénieurs, et dans de nombreux cas, l'essentiel est d'implémenter des fonctions et des classes spécifiques en fonction du thème.
En guise de contre-mesure, il semble qu'un site appelé Let Code prendra des mesures.
Un site qui forme une puissance algorithmique capable de résister aux tests de codage dont on parle très tôt.
Je pense qu'il vaut mieux avoir la puissance de l'algorithme d'un être humain, donc je vais résoudre le problème de manière irrégulière et écrire la méthode que j'ai pensé à ce moment-là sous forme de mémo.
Table de codes Leet commençant à zéro
Dernière fois Leet Code Day 19 à partir de zéro "121. Meilleur moment pour acheter et vendre des actions"
En gros, je voudrais résoudre l'acceptation facile par ordre décroissant.
Cela a duré 20 fois, ce qui est inhabituel pour moi qui en ai marre. surprise.
Twitter Je le fais.
Le niveau de difficulté est moyen. L'une des 100 questions les plus appréciées.
C'était un problème très intéressant à résoudre, alors essayez de le résoudre.
Deux listes sont données: la quantité d'essence "essence" et le "coût" indiquant la quantité d'essence consommée pour se déplacer vers ce point.
En plus d'eux, vous avez reçu une voiture avec un réservoir d'essence d'une capacité infinie. Il en coûte «cost [i]» pour passer de la station i à la station suivante (i + 1). Le réservoir d'essence est vide au début, et s'il s'agit d'une patrouille dans le sens des aiguilles d'une montre pendant une semaine, il renverra le ** index de la station de départ **, sinon il renverra «-1».
Veuillez noter les points suivants.
--Si une solution existe, elle est unique.
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.
Ceci est un exemple en partant de la station 3. La quantité d'essence retenue au départ est de 3 car le «gaz» de la station 3 est de 3. Dans ce cas, l'index «3» de la station 3 est renvoyé car il est possible de revenir de ce point à tout moment.
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.
Pour le moment, trois variables sont requises comme variables candidates: «tank», qui gère la quantité d'essence, «start», qui indique le point de départ si la course est terminée, et «cur», qui indique la quantité d'essence retenue à l'emplacement actuel. La raison pour laquelle «tank» et «cur» sont séparés est de gérer le cas où la valeur de «cur» devient négative. Cela signifie que vous ne pouvez pas terminer la course, et ce que vous faites dans ce cas sera une partie importante de la résolution de ce problème.
De plus, j'ai écrit comme suit.
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.
C'est correct en vérifiant cur par if en tournant avec l'instruction for, et si elle est négative, attribuez 0 à cur et affectez ʻi + 1 à start`. La position de départ est maintenant renvoyée sous forme d'index.
J'ai pensé après avoir passé, mais dans cette phrase, la dernière branche est un peu redondante. Si vous écrivez comme 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.
En Python
if tank < 0:
return -1
else:
return start
Est
return -1 if tank < 0 else start
J'ai essayé de le réécrire parce qu'il est égal. C'est assez rafraîchissant, donc si vous pouvez l'écrire, c'est mieux.
S'il y a une autre bonne solution, je l'ajouterai.
Recommended Posts