[PYTHON] Lassen Sie Code Day58 ab Null "20. Gültige Klammern"

Überblick

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.

Leetcode

Ich löse es mit Python3.

Leet Code-Tabelle ab Null

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.

Problem

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

Lösung

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

Lassen Sie Code Day58 ab Null "20. Gültige Klammern"
Lassen Sie Code Tag 55 "22. Klammern erzeugen" ab Null
Lassen Sie Code Day16 von vorne beginnen "344. Reverse String"
Lassen Sie Code Day49 ab Null "1323. Maximum 69 Number".
Lassen Sie Code Day89 "62. Unique Paths" ab Null
Lassen Sie Code Day18 ab Null "53. Maximum Subarray"
Lassen Sie Code Tag 13 "338. Bits zählen" ab Null
Lassen Sie Code Day71 ab Null "1496. Pfadkreuzung"
Lassen Sie Code Tag 61 "7. Reverse Integer" ab Null
Lassen Sie Code Tag 82 "392. Ist Folge" ab Null
Lassen Sie Code Day51 "647. Palindromic Substrings" ab Null
Lassen Sie Code Tag 50 "739. Tägliche Temperaturen" ab Null
Lassen Sie Code Day15 ab Null "283. Nullen verschieben"
Lassen Sie Code Day14 ab Null "136. Single Number"
Lassen Sie Code Day 43 von vorne beginnen "5. Längster palindromischer Teilstring"
Lassen Sie Code Day74 ab Null "12. Integer to Roman"
Lassen Sie Code Day 42 "2. Add Two Numbers" von vorne beginnen
Lassen Sie Code Day57 ab Null "35. Search Insert Position"
Lassen Sie Code Day47 von vorne beginnen "14. Längstes gemeinsames Präfix"
Lassen Sie Code Day78 von vorne beginnen "206. Reverse Linked List"
Lassen Sie Code Day75 von vorne beginnen "15.3 Sum"
Lassen Sie Code Day 44 "543. Durchmesser des Binärbaums" von vorne beginnen
Lassen Sie Code Tag 64 ab Null "287. Finden Sie die doppelte Nummer"
Lassen Sie Code Day 84 ab Null "142. Linked List Cycle II"
Lassen Sie Code Day 29 "46. Permutationen" von vorne beginnen
Lassen Sie Code Day24 ab Null "21. Zwei sortierte Listen zusammenführen"
Lassen Sie Code Day12 von vorne beginnen "617. Zwei binäre Bäume zusammenführen"
Lassen Sie Code Day2 von vorne beginnen "1108. IP-Adresse löschen"
Lassen Sie Code Day70 ab Null "295. Median aus Datenstrom suchen"
Lassen Sie Code Day81 "347. Top K Frequent Elements" ab Null
Lassen Sie Code Day48 ab Null "26. Duplikate aus sortiertem Array entfernen"
Lassen Sie Code Day87 ab Null "1512. Anzahl der guten Paare"
Lassen Sie Code Day67 von vorne beginnen "1486. XOR-Operation in einem Array"
Lassen Sie Code Day56 ab Null "5453. Laufende Summe von 1d Array"
Lassen Sie Code Day7 ab Null "104. Maximale Tiefe des Binärbaums"
Lassen Sie Code Day86 ab Null "33. Suche in gedrehtem sortiertem Array"
Lassen Sie Code Day92 ab Null "4. Median von zwei sortierten Arrays"
Lassen Sie Code Day5 ab Null "1266. Mindestzeit für den Besuch aller Punkte"
Lassen Sie Code Tag 35 "160. Schnittpunkt zweier verknüpfter Listen" von vorne beginnen
Lassen Sie Code Day83 ab Null "102. Order Traversal auf Binäre Baumebene"
Lassen Sie Code Day 27 "101. Symmetric Tree" von vorne beginnen
Lassen Sie Code Day 41 "394. Decode String" ab Null
Lassen Sie Code Day 25 "70. Climbing Stairs" von vorne beginnen
Lassen Sie die Codetabelle von Null beginnen
Lassen Sie Code Day69 von vorne beginnen "279. Perfect Squares"
Lassen Sie Code Day 34 von vorne beginnen "118. Pascals Dreieck"
Lassen Sie Code Day85 von vorne beginnen "6. Zick-Zack-Konvertierung"
Lassen Sie Code Day20 von vorne beginnen "134. Tankstelle"
Lassen Sie Code Day 88 "139. Word Break" von vorne beginnen
Lassen Sie Code Day 28 "198. House Robber" von vorne beginnen
Lassen Sie Code Day 39 "494. Target Sum" von vorne beginnen
Lassen Sie Code Day 36 "155. Min Stack" von vorne beginnen
Lassen Sie Code Tag 17 "169. Mehrheitselement" von vorne beginnen
Lassen Sie Code Tag 33 "1. Zwei Summe" ab Null
Lassen Sie Code Tag 40 ab Null "114. Binärbaum auf verknüpfte Liste reduzieren"
Lassen Sie Code Tag 91 "153. Minimum in gedrehtem sortiertem Array finden" ab Null
Lassen Sie Code Day59 ab Null "1221. Teilen Sie einen String in ausgeglichene Strings"
Lassen Sie Code Tag 11 ab Null "1315. Summe der Knoten mit gleichwertigen Großeltern"
Lassen Sie Code Day6 ab Null beginnen "1342. Anzahl der Schritte, um eine Zahl auf Null zu reduzieren"
Lassen Sie Code Tag 23 "226. Binären Baum umkehren" von vorne beginnen
Lassen Sie Code Day8 ab Null "1302. Deepest Leaves Sum"