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 de mettre en œuvre des fonctions et des classes spécifiques en fonction du thème.
Apparemment, de nombreux ingénieurs prennent des mesures sur le site appelé LetCode.
C'est un site qui forme la puissance de l'algorithme qui peut résister au test de codage effectué au début, et c'est un chemin inévitable pour ceux qui veulent faire carrière dans une entreprise de technologie à l'étranger.
Je l'ai écrit en grand, mais je n'ai pas l'intention d'avoir une telle interview pour le moment.
Cependant, en tant qu'ingénieur informatique, il serait préférable d'avoir le même niveau de puissance d'algorithme qu'une personne, alors j'aimerais résoudre le problème de manière irrégulière et écrire la méthode que je pensais à l'époque sous forme de mémo.
Je le résolve avec Python3.
Table de codes Leet commençant à zéro
Dernière fois Leet Code Day 57 "35. Search Insert Position" à partir de zéro
À l'heure actuelle, je donne la priorité au moyen des 100 questions les plus appréciées. Easy a été résolu, donc si vous êtes intéressé, veuillez vous rendre à la table.
Twitter Je le fais.
20. Valid Parentheses Le niveau de difficulté est facile.
La question est, si on donne une chaîne s qui contient uniquement les lettres '(', ')', '{', '}', '[' et ']', la chaîne saisie est-elle valide? Juger.
La chaîne de caractères d'entrée est effective dans les cas suivants.
Les parenthèses ouvertes doivent être fermées avec le même type de parenthèses. Les parenthèses doivent être fermées dans le bon ordre. Notez que les chaînes vides sont également considérées comme valides.
Input: "()" Output: true
Input: "()[]{}" Output: true
Input: "(]" Output: false
Input: "([)]" Output: false
Input: "{[]}" Output: true
Comme vous pouvez le voir dans l'exemple, si la parenthèse est complétée séparément, elle peut être «True», sinon elle peut être «False», et ainsi de suite.
Je pense que c'est plus facile à gérer en utilisant une pile si vous pouvez vérifier exactement le début et la fin.
Par exemple, considérons le cas de ʻInput: "{[]}" `. Utilisez l'instruction for pour remplacer «s» par «char» et lisez de l'avant. Ensuite, l'ordre des caractères à lire est `` '{', '[', ']', '}' '.
Vous devez vérifier que l'instruction if ferme les parenthèses dans le bon ordre.
Par conséquent, vous devez préparer votre propre jeu de parenthèses pour vérifier.
Je pense qu'il est courant de le gérer avec une liste ou un dictionnaire ici.
Si les éléments de parenthèses sont gérés dans une liste
open_str = ["[","{","("] close_str = ["]","}",")"]
Ça ressemble à ça
Si vous gérez avec un dictionnaire
dict = {")":"(","]":"[","}":"{"}
Il ressemblera à ceci. Cette fois, j'ai utilisé le dictionnaire.
Maintenant, si vous arrivez à ce point, si l'élément char existe dans le dict lorsque vous le tournez avec l'instruction for, vous pouvez écrire le traitement quand il n'existe pas.
Et si l'élément était dans dict.values?
Dans ce cas, c'est une bonne idée de l'ajouter à la pile préparée.
Comme vous le savez tous, la nature de la pile est LIFO (dernier entré premier sorti), donc la pile à retirer de la fin est pratique dans le cas comme cette fois.
Alors, que devons-nous faire si char existe dans dict.keys, et enfin dans les autres cas?
Dans ce cas, j'ai écrit un nouveau processus comme suit.
if stack == [] or dict[char] != stack.pop():
return False
Dans de tels cas, si l'un de ces cas est vrai, "False" Retour. Inversement, si ce n'est pas le cas, le processus se poursuit.
Et s'il ne correspond à aucune des conditions que j'ai écrites jusqu'à présent, il renvoie False.
Les contenus écrits ensemble sont les suivants.
class Solution:
def isValid(self, s: str) -> bool:
stack = []
dict = {")":"(","]":"[","}":"{"}
for char in s:
if char in dict.values():
stack.append(char)
elif char in dict.keys():
if stack == [] or dict[char] != stack.pop():
return False
else:
return False
return stack == []
# Runtime: 36 ms, faster than 30.47% of Python3 online submissions for Valid Parentheses.
# Memory Usage: 13.8 MB, less than 77.84% of Python3 online submissions for Valid Parentheses.
La partie solution est plus longue que ce à quoi je m'attendais ... Il peut être plus facile pour le lecteur d'écrire plus rapidement. Je voudrais écrire en réfléchissant à diverses choses de la part du lecteur.
Pour changer l'histoire, j'ai récemment découvert CS, pas seulement les algorithmes et les structures de données, mais c'est amusant d'étudier les genres qui m'intéressent!
Alors c'est tout pour cette fois. Je vous remercie pour votre travail acharné.
Recommended Posts