Ich habe jeden Tag 20 LeetCode ausprobiert. Gültige Klammern (Python, Go)

Einführung

@Ishishow betreibt eine kostenlose englische Word-Site E-tan.

Ich möchte jeden Tag an Letcode arbeiten, um meine Fähigkeiten als Programmierer zu verbessern und meine eigene Art der Lösung zu finden.

Was ist Leetcode?

leetcode.com Dies ist die Praxis des Codierens von Interviews für Softwareentwickler. Insgesamt wurden mehr als 1.500 Codierungsfragen gestellt, und es scheint, dass in tatsächlichen Interviews häufig dieselben Fragen gestellt werden.

Einführung in Go Sprache + Algorithmus Ich werde es mit Golang und Python lösen, um mein Gehirn zu stärken. (Python ist schwach, aber erfahren)

6. Frage (Problem 20)

20. Valid Parentheses

--Probleminhalt (japanische Übersetzung)

Stellen Sie sich vor, eine Zeichenfolge s enthält nur Zeichen '(', ')', '{', '}', '[' und ']', Eingabe Stellen Sie fest, ob die Zeichenfolge gültig ist.

Die Eingabezeichenfolge ist in folgenden Fällen gültig:

1. Offene Klammern müssen mit demselben Klammertyp geschlossen werden.
2. Offene Klammern müssen in der richtigen Reihenfolge geschlossen werden.

Example 1:

  Input: s = "()"
  Output: true

Example 2:

  Input: s = "()[]{}"
  Output: true

Example 3:

  Input: s = "(]"
  Output: false

Example 4:

  Input: s = "([)]"
  Output: false

Example 5:

  Input: s = "{[]}"
  Output: true

Denkweise

1. Bereiten Sie ein Stack-Array und ein Wörterbuch (Map) vor.
2. Geben Sie das entsprechende Symbol in die Karte ein
3. Sehen Sie sich die Zeichenfolge zeichenweise an, fügen Sie sie dem Stapel hinzu, wenn sie mit einer Klammer beginnt. Wenn es sich um eine schließende Klammer handelt, nehmen Sie die neueste aus dem Stapel und prüfen Sie, ob sie übereinstimmt.

Erläuterung

1. Stapel definieren und diktieren (Karte).
2. dict = {"]":"[", "}":"{", ")":"("}
3. Sehen Sie sich die Zeichen einzeln mit der for-Anweisung an.

--Antwortcode

class Solution:
	def isValid(self, s):
		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 == []

If char in dict.values (): Gibt an, ob mit Klammern begonnen wird

Elif char in dict.keys (): Gibt an, ob es in Klammern endet

Holen Sie sich die neuesten Stack-Charaktere mit Pop

Zuweisen zum Stapeln mit Anhängen.

• Ich werde es auch in Go schreiben!

  func isValid(s string) bool {
  	stack := make([]rune, 0)
  	m := map[rune]rune{
  		')': '(',
  		']': '[',
  		'}': '{',
  	}
  	for _, c := range s {
  		switch c {
  		case '(', '{', '[':
  			stack = append(stack, c)
  		case ')', '}', ']':
  			if len(stack) == 0 || stack[len(stack)-1] != m[c] {
  				return false
  			}
  			stack = stack[:len(stack)-1]
  		}
  	}
  
  	return len(stack) == 0
  }

Dieser Code ist etwas knifflig, aber ich habe diesen Code erhalten, um die Zeichenfolgen zeichenweise in Go zu sehen.

Für _ liest c: = die Schleifenverarbeitung des Bereichs die Zeichenfolgen Zeichen für Zeichen. Zu diesem Zeitpunkt wird c zum Runentyp, sodass Karte und Stapel auch mit dem Runentyp definiert werden.

Da ich Golang schreibe, habe ich den Prozess mit der Switich-Anweisung geschrieben.

• Selbst Memo (Go)

Wenn Sie die Zeichenfolge Zeichen für Zeichen betrachten, Rune

An Slice anhängen (ok, da es keine feste Länge hat)