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.
Anscheinend ergreifen viele Ingenieure Maßnahmen auf der Website namens LetCode.
Es ist eine Site, die die Algorithmusleistung trainiert, die dem Codierungstest standhält, der in der frühen Geschichte durchgeführt wird, und es ist ein unvermeidlicher Weg für diejenigen, die eine Karriere bei einem ausländischen Technologieunternehmen aufbauen möchten.
Ich habe es groß geschrieben, aber ich habe im Moment keine Pläne für ein solches Interview.
Als IT-Ingenieur wäre es jedoch besser, die gleiche Algorithmusleistung wie eine Person zu haben. Daher möchte ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.
Ich löse es mit Python3.
Letztes Mal Leet Code Day 57 "35. Search Insert Position" ab Null
Im Moment priorisiere ich das Medium der 100 beliebtesten Fragen. Easy wurde gelöst. Wenn Sie interessiert sind, gehen Sie bitte zum Tisch.
Twitter Ich mache es.
20. Valid Parentheses Der Schwierigkeitsgrad ist einfach.
Die Frage ist, ob die eingegebene Zeichenfolge gültig ist, wenn eine Zeichenfolge "s" angegeben wird, die nur die Buchstaben "(", ")", "{", "}", "[" und "]" enthält. Urteilen.
Die Eingabezeichenfolge ist in den folgenden Fällen wirksam.
Offene Klammern müssen mit demselben Klammertyp geschlossen werden. Die Klammern müssen in der richtigen Reihenfolge geschlossen werden. Beachten Sie, dass leere Zeichenfolgen ebenfalls als gültig angesehen werden.
Input: "()" Output: true
Input: "()[]{}" Output: true
Input: "(]" Output: false
Input: "([)]" Output: false
Input: "{[]}" Output: true
Wie Sie dem Beispiel entnehmen können, kann die Klammer, wenn sie separat ausgefüllt wird, "Wahr" sein, andernfalls "Falsch" usw.
Ich denke, es ist einfacher, mit einem Stapel zu arbeiten, wenn Sie den Anfang und das Ende genau überprüfen können.
Betrachten Sie beispielsweise den Fall von Input:" {[]} ".
Verwenden Sie die for-Anweisung, um "char" durch "s" zu ersetzen, und lesen Sie von vorne.
Dann ist die Reihenfolge der zu lesenden Zeichen "{", "[", "]", "}".
Sie müssen überprüfen, ob die if-Anweisung die Klammern in der richtigen Reihenfolge schließt.
Daher müssen Sie Ihre eigenen Klammern vorbereiten, um dies zu überprüfen.
Ich denke, dass es üblich ist, es hier mit einer Liste oder einem Wörterbuch zu verwalten.
Wenn die Elemente in Klammern in einer Liste verwaltet werden
open_str = ["[","{","("] close_str = ["]","}",")"]
Es sieht aus wie das
Wenn Sie mit einem Wörterbuch auskommen
dict = {")":"(","]":"[","}":"{"}
Es wird so aussehen. Diesmal habe ich das Wörterbuch benutzt.
Übrigens, wenn das "char" -Element im "dict" vorhanden ist, wenn es von der for-Anweisung gedreht wird, reicht es aus, die Verarbeitung zu schreiben, wenn es nicht vorhanden ist. Was ist, wenn sich das Element in "dict.values" befindet? In diesem Fall ist es eine gute Idee, es dem vorbereiteten "Stapel" hinzuzufügen.
Wie Sie alle wissen, ist die Art des Stapels LIFO (Last in first out), daher ist der Stapel, der am Ende herausgenommen werden soll, in diesem Fall praktisch.
Was sollen wir dann tun, wenn "char" in "dict.keys" existiert und schließlich in anderen Fällen?
In diesem Fall habe ich einen neuen Prozess wie folgt geschrieben.
if stack == [] or dict[char] != stack.pop():
return False
In solchen Fällen, wenn einer dieser Punkte wahr ist, "Falsch" Kehrt zurück. Ist dies nicht der Fall, wird der Vorgang fortgesetzt.
Und es gibt "False" zurück, wenn es keiner der Bedingungen entspricht, die ich bisher geschrieben habe.
Die zusammen geschriebenen Inhalte sind wie folgt.
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.
Der Lösungsteil ist länger als ich erwartet hatte ... Es kann für den Leser einfacher sein, schneller zu schreiben. Ich möchte schreiben, während ich über verschiedene Dinge des Lesers nachdenke.
Um die Geschichte zu ändern, habe ich kürzlich etwas über CS gelernt, nicht nur über Algorithmen und Datenstrukturen, sondern es macht auch Spaß, die Genres zu studieren, an denen ich interessiert bin!
Das war's für diese Zeit. Danke für deine harte Arbeit.
Recommended Posts