Gültiges Sudoku (LeetCode 36): Python-Lösung, Box-Index und Randfälle

Valid Sudoku (LeetCode 36) gibt dir ein teilweise gefülltes 9×9-Brett und fragt, ob die gefüllten Zellen gegen eine Sudoku-Regel verstoßen. Du musst das Rätsel nicht lösen. Du prüfst nur, dass sich keine Ziffer in einer Zeile, einer Spalte oder einem 3×3-Block wiederholt. Ein Durchlauf mit drei Mengen bereits gesehener Ziffern erledigt das in O(81), also konstant.

Das Problem

Das Brett ist ein 9×9-Raster aus Zeichen, jedes eine Ziffer von 1 bis 9 oder . für leer. Gib true zurück, wenn die gefüllten Zellen diese Regeln einhalten:

• Jede Zeile hat keine wiederholte Ziffer.
• Jede Spalte hat keine wiederholte Ziffer.
• Jeder 3×3-Block hat keine wiederholte Ziffer.

Ein Brett kann gültig sein, auch wenn es keine Lösung hat. Nur die gefüllten Zellen werden geprüft.

Ansatz: drei Mengen pro Einheit

Führe eine Menge gesehener Ziffern für jede Zeile, jede Spalte und jeden Block. Prüfe für jede gefüllte Zelle die Ziffer in allen drei Mengen und füge sie hinzu, wenn sie neu ist.

Der einzige Teil, der Nachdenken erfordert, ist der Block-Index. Für eine Zelle in Zeile r und Spalte c ist die Blocknummer (r // 3) * 3 + c // 3. Sie zählt die Blöcke von links nach rechts, von oben nach unten, von 0 bis 8.

def is_valid_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == ".":
                continue
            b = (r // 3) * 3 + c // 3
            if ch in rows[r] or ch in cols[c] or ch in boxes[b]:
                return False
            rows[r].add(ch)
            cols[c].add(ch)
            boxes[b].add(ch)
    return True

Durchlauf

Angenommen, Zeile 0 hat eine 5 in Spalte 0 und eine weitere 5 in Spalte 4. Die erste 5 wird zu rows[0], cols[0] und boxes[0] hinzugefügt. Bei Spalte 4 ist die Prüfung ch in rows[0] wahr, also gibt die Funktion sofort false zurück. Gleiche Ziffern im selben Block oder in derselben Spalte werden auf dieselbe Weise von den anderen beiden Mengen erfasst.

Komplexität

Das Brett ist immer 9×9, also ist die Zeit konstant, 81 Zellbesuche. Wenn du auf ein n×n-Brett verallgemeinerst, sind es O(n zum Quadrat) Zeit und O(n zum Quadrat) Speicher. Nenne beides, da Interviewer oft fragen, wie es skaliert.

Varianten, die Interviewer fragen

Die Bitmasken-Version ersetzt jede Menge durch eine Ganzzahl. mask & (1 << d) prüft eine Ziffer und mask |= 1 << d zeichnet sie auf. Sie ist schneller, aber die Mengen-Version ist unter Zeitdruck leichter richtig hinzubekommen, also schreibe zuerst diese.

Häufige Fehler

• Zeilen und Spalten prüfen, aber die Blöcke vergessen.
• Eine falsche Block-Formel, wie r // 3 + c // 3, die verschiedenen Blöcken denselben Index gibt.
• . als Ziffer behandeln, sodass zwei leere Zellen als Wiederholung zählen.
• Versuchen, das Brett zu lösen, obwohl die Frage nur nach Gültigkeit fragt.

Randfälle zum Testen

Wie du es im Interview erklärst

1. Gib die Regeln wieder und sage, dass du nur validierst, nicht löst.
2. Nenne die drei Einheiten und sage, dass jede eine Gesehen-Menge braucht.
3. Gib die Block-Index-Formel an und erkläre sie mit einem Beispiel.
4. Schreibe den einzelnen Durchlauf und den vorzeitigen Return.
5. Nenne die Komplexität und biete die Bitmasken-Version an, wenn danach gefragt wird.

Ich habe den obigen Code gegen eine einfache Zeilen-, Spalten- und Block-Prüfung auf 20.000 zufälligen Brettern getestet, einige gültig und einige absichtlich fehlerhaft, bevor ich ihn veröffentlicht habe. Ein solcher schneller Zufallstest ist eine gute Angewohnheit beim Üben.

Verwandte Übung

Sieh dir unseren Big-O-Spickzettel für die Komplexitätsbegriffe an, die LeetCode Blind 75 Liste für das, was du als Nächstes üben solltest, und den Leitfaden zum Coding-Interview-Assistenten für das Üben.

Sprich deinen Ansatz laut durch, während du codest. Ein Transkript zeigt, ob du die entscheidende Beobachtung vor dem Schreiben genannt hast. Befolge die Regeln des Arbeitgebers zu KI-Tools in jeder Live-Prüfung.