Laissez Code Day20 partir de zéro "134. Station-service"

Aperçu

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.

Leetcode

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.

problème

134. Gas Station

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.

Solution

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

Laissez Code Day20 partir de zéro "134. Station-service"
Soit Code Day75 à partir de zéro "15.3 Sum"
Let Code Day 29 "46. Permutations" à partir de zéro
Let Code Day 27 "101. Symmetric Tree" à partir de zéro
Let Code Day 41 "394. Decode String" à partir de zéro
Let Code Day 25 "70. Grimper les escaliers" à partir de zéro
Laissez Code Day69 à partir de zéro "279. Perfect Squares"
Laissez Code Day85 à partir de zéro "6. Conversion en zigzag"
Let Code Day 88 "139. Word Break" à partir de zéro
Let Code Day 28 "198. House Robber" à partir de zéro
Let Code Day 39 "494. Target Sum" à partir de zéro
Let Code Day 36 "155. Min Stack" à partir de zéro
Let Code Day 17 "169. Majority Element" à partir de zéro
Let Code Day 33 "1. Two Sum" à partir de zéro
Let Code Day 23 "226. Invert Binary Tree" en partant de zéro
Let Code Day8 À partir de zéro "1302. Somme des feuilles les plus profondes"
Soit Code Jour 22 à partir de zéro "141. Cycle de liste liée"
Let Code Day 30 à partir de zéro "234. Palindrome Linked List"
Let Code Day 32 "437. Path Sum III" à partir de zéro
Soit Code Day68 à partir de zéro "709. To Lower Case"
Let Code Day 26 à partir de zéro "94. Traversée en ordre de l'arbre binaire"
Soit Code Day 46 à partir de zéro "406. Reconstruction de file d'attente par hauteur"
Let Code Day 31 "581. Le sous-tableau continu non trié le plus court" à partir de zéro
Let Code Day 38 à partir de zéro "208. Implémenter Trie (Prefix Tree)"
Soit Code Day3 à partir de zéro "1313. Decompress Run-Length Encoded List"
Soit Code Day 65 "560. Subarray Sum Equals K" à partir de zéro
Soit Code Day4 à partir de zéro "938. Range Sum of BST"
Let Code Day 77 "1502. Peut faire une progression arithmétique à partir de la séquence" à partir de zéro
Soit Code Jour 76 à partir de zéro "3. Sous-chaîne la plus longue sans caractères répétitifs"
Soit Code Day58 à partir de zéro "20. Parenthèses valides"
Soit Code Day16 à partir de zéro "344. Reverse String"
Soit Code Day49 à partir de zéro "1323. Maximum 69 Number"
Let Code Day89 "62. Chemins uniques" à partir de zéro
Let Code Day 55 "22. Générer des parenthèses" à partir de zéro
Soit Code Day18 à partir de zéro "53. Maximum Subarray"
Let Code Day 13 "338. Comptage des bits" à partir de zéro
Let Code Day71 À partir de zéro "1496. Traversée de chemin"
Let Code Day 61 "7. Integer Integer" à partir de zéro
Let Code Day 82 "392. Is Subsequence" Partant de zéro
Let Code Day51 "647. Sous-chaînes palindromiques" à partir de zéro
Let Code Day 50 "739. Températures quotidiennes" à partir de zéro
Let Code Day 15 "283. Move Zeroes" à partir de zéro
Soit Code Day14 à partir de zéro "136. Numéro unique"
Let Code Day 9 "701. Insérer dans un arbre de recherche binaire" à partir de zéro
Let Code Day 80 "703. Kth plus grand élément d'un flux" à partir de zéro
Let Code Day 66 "438. Find All Anagrams in a String" en partant de zéro
Let Code Day 43 à partir de zéro "5. Le plus long substrat palindromique"
Soit Code Day74 à partir de zéro "12. Integer to Roman"
Let Code Day 42 "2. Add Two Numbers" en partant de zéro
Let Code Day57 À partir de zéro "35. Rechercher Insérer la position"
Soit Code Day47 à partir de zéro "14. Préfixe commun le plus long"
Soit Code Day78 à partir de zéro "206. Liste liée inversée"
Let Code Day 90 à partir de zéro "101 1. Capacité à expédier les colis dans les D jours"
Soit Code Day 44 "543. Diamètre de l'arbre binaire" à partir de zéro
Soit Code Jour 64 à partir de zéro "287. Trouver le numéro en double"
Laissez Code Day12 partir de zéro "617. Fusionner deux arbres binaires"
Soit Code Day2 à partir de zéro "1108. Defanging an IP Address"
Let Code Day70 À partir de zéro "295. Trouver la médiane à partir du flux de données"
Let Code Day81 "347. Top K éléments fréquents" à partir de zéro
Let Code Day48 Starting from Zero "26. Supprimer les doublons du tableau trié"
Soit Code Day87 à partir de zéro "1512. Nombre de bonnes paires"