Number of Islands

Q: Wie lautet die Zeitkomplexität von Number of Islands?

O(rows × cols). Der Scan betrachtet jedes Feld einmal, und jedes Landfeld gelangt einmal auf den Stack oder in die Queue und prüft vier Nachbarn. Die Markierungen für bereits besuchte Felder und der Stack oder die Queue benötigen O(rows × cols) Speicherplatz auf einer Karte, die vollständig aus Land besteht.

Q: Solltest du für „Number of Islands“ BFS oder DFS verwenden?

Beide sind in Bezug auf Zeit und Speicherplatz korrekt, da beim Zählen lediglich jedes Feld einer Insel markiert werden muss. BFS mit einer Warteschlange verwendet keine Rekursion; DFS ist ebenso sicher, wenn ein expliziter Stapel verwendet wird.

Q: Kannst du Number of Islands mit Union-Find lösen?

Ja. Lege jedes Landfeld in eine eigene Menge und beginne die Zählung mit der Anzahl der Landfelder. Verbinde jedes Paar benachbarter Landfelder und verringere die Zählung jeweils um eins, wenn durch eine Verbindung zwei verschiedene Mengen zusammengeführt werden. Mit Pfadkompression liegt die Laufzeit nahe bei O(Zeilen × Spalten).

Q: Kannst du Inseln ohne ein separates Array für besuchte Inseln zählen?

Ja, wenn du die Karte ändern darfst: Wandle jedes Landfeld in Wasser um, sobald du es erreichst. Viele Sprachen können Zeichenfolgen nicht direkt ändern, daher kopierst du zuerst die Zeilen in ein Zeichengitter. Das benötigt genauso viel Speicherplatz wie die Markierungen für bereits besuchte Felder.

MittelGraphen

+10

Du erhältst eine Karte als Liste gleich langer Zeichenfolgen, wobei '1' ein Landquadrat und '0' ein Wasserquadrat ist. Zwei Landquadrate gehören zur selben Insel, wenn sie eine Seite gemeinsam haben: oben, unten, links oder rechts. Quadrate, die sich nur an einer Ecke berühren, sind nicht verbunden. Gib die Anzahl der Inseln zurück.

Funktion

numIslands(grid: string-array) → integer

gridstring-array: die Karte, eine Zeichenfolge pro Zeile
Gibt zurückinteger: die Anzahl der Inseln

Einschränkungen

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Jede Zeile hat dieselbe Länge.
Jedes Zeichen ist '0' oder '1'.

Beispiele

Eingabe: grid = ["11000", "11000", "00100", "00011"]
Ausgabe: 3
Erklärung: Die vier Quadrate oben links bilden eine Insel. Das mittlere Quadrat in der dritten Zeile berührt sie nur an einer Ecke, daher ist es eine zweite Insel. Das Paar unten rechts ist die dritte.

Weiterführende Frage

LAND erscheint nun ein Feld nach dem anderen auf einer Wasserkarte. Kannst du nach jedem neuen Feld die Anzahl der Inseln angeben, ohne die ganze Karte erneut zu durchsuchen?

Lösung

Betrachte jedes Landfeld als einen Knoten, der mit den angrenzenden Landfeldern verbunden ist: Eine Insel ist ein zusammenhängendes Gebiet. Durchsuche die Karte, und jedes Mal, wenn du Land erreichst, das du noch nicht gesehen hast, zähle eine neue Insel und fülle sie per Flood Fill, indem du jedes ihrer Felder markierst, damit sie beim Durchsuchen nicht noch einmal gezählt wird.

Flächenfüllung mit einem expliziten Stack (DFS)

Idee

Ein nicht markiertes Landfeld kann nicht zu einer Insel gehören, die du bereits gezählt hast, denn beim Zählen wird die gesamte Insel markiert. Es beginnt also eine neue Insel. Ein Stack, den du selbst verwaltest, markiert den Rest: Jedes Feld, das du vom Stack nimmst, legt seine nicht markierten Landnachbarn auf den Stack, und wenn der Stack leer ist, ist die gesamte Insel markiert.

Dein eigener Stack ist wichtig, weil eine rekursive Flutung auf einer Karte mit durchgehendem Land von 150 × 150 Feldern 22,500 Aufrufe tief gehen kann. Jedes Feld wird höchstens einmal auf den Stack gelegt und prüft vier Nachbarn, daher beträgt die Laufzeit O(rows × cols). Die Markierungen und der Stack benötigen O(rows × cols) Speicherplatz, wenn die Karte vollständig aus Land besteht.

Algorithmus

Erstelle für jedes Feld eine Markierung für „gesehen“ und setze den Zähler auf 0.
Durchlaufe jedes Feld und überspringe Wasser sowie bereits markierte Felder.
Erhöhe bei unmarkiertem Land den Zähler um 1, markiere das Feld und lege es auf einen Stapel.
Solange der Stapel nicht leer ist, nimm ein Feld vom Stapel und lege jeden Nachbarn innerhalb der Karte auf den Stapel, der unmarkiertes Land ist. Markiere ihn, bevor du ihn auf den Stapel legst.
Gib den Zähler zurück, wenn der Durchlauf beendet ist.

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1' or seen[r][c]:
                continue
            # Land that no island has claimed yet: a new island.
            count += 1
            seen[r][c] = True
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
                        # Mark on push, so no square enters the stack twice.
                        seen[ni][nj] = True
                        stack.append((ni, nj))
    return count

Flood Fill mit einer Warteschlange (BFS)

Idee

Das Zählen funktioniert genauso; nur die Reihenfolge der Besuche ändert sich. Eine Warteschlange nimmt Felder vom Anfang und fügt unmarkierte Landnachbarn am Ende hinzu, sodass sie die Insel in Ringen durchläuft: zuerst das erste Feld, dann jedes Feld in einem Schritt Entfernung, dann die Felder in zwei Schritten Entfernung. Jedes Feld wird weiterhin genau einmal besucht, in O(rows × cols) Zeit und Speicherplatz.

Die Reihenfolge der Ringe gibt die Entfernung jedes Feldes vom Start an, sodass dieselbe Schleife Fragen nach dem kürzesten Pfad auf einem Raster mit einer zusätzlichen Zahl pro Feld beantwortet.

Algorithmus

Erstelle für jedes Feld eine Markierung für „gesehen“ und setze den Zähler auf 0.
Durchlaufe jedes Feld und überspringe Wasser sowie bereits gesehene Felder.
Erhöhe bei ungesehenem Land den Zähler um 1, markiere das Feld und füge es einer leeren Warteschlange hinzu.
Solange die Warteschlange Felder enthält, nimm eines vom Anfang und füge jeden Nachbarn innerhalb der Karte, der ungesehenes Land ist, hinten hinzu und markiere ihn dabei.
Gib den Zähler zurück, wenn der Durchlauf endet.

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1' or seen[r][c]:
                continue
            count += 1
            seen[r][c] = True
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
                        seen[ni][nj] = True
                        stack.append((ni, nj))
    return count

Stolperfallen und Grenzfälle

Ein Quadrat zu markieren, wenn du es aus dem Stapel oder der Warteschlange nimmst, statt wenn du es hinzufügst. Dasselbe Quadrat kommt dann mehrmals hinein.
Ein Quadrat mit der Zahl 1 statt mit dem Zeichen '1' zu vergleichen. Jede Zeile ist eine Zeichenkette, also ist jedes Quadrat ein Zeichen.
Einen Nachbarn zu lesen, bevor du 0 ≤ row < rows und 0 ≤ col < cols überprüfst. Ein Landquadrat am Rand liest dann über die Karte hinaus.
Die Flutung rekursiv zu schreiben. Python hält standardmäßig nach 1.000 Aufrufen an, und andere Sprachen können bei einer einzigen großen Insel einen Stapelüberlauf verursachen.
Das erste Element einer Python-Liste mit pop(0) zu entnehmen, was Zeit proportional zur Listenlänge kostet. Verwende collections.deque und popleft().

Häufige Fragen4

Wie lautet die Zeitkomplexität von Number of Islands?

O(rows × cols). Der Scan betrachtet jedes Feld einmal, und jedes Landfeld gelangt einmal auf den Stack oder in die Queue und prüft vier Nachbarn. Die Markierungen für bereits besuchte Felder und der Stack oder die Queue benötigen O(rows × cols) Speicherplatz auf einer Karte, die vollständig aus Land besteht.

Solltest du für „Number of Islands“ BFS oder DFS verwenden?

Beide sind in Bezug auf Zeit und Speicherplatz korrekt, da beim Zählen lediglich jedes Feld einer Insel markiert werden muss. BFS mit einer Warteschlange verwendet keine Rekursion; DFS ist ebenso sicher, wenn ein expliziter Stapel verwendet wird.

Kannst du Number of Islands mit Union-Find lösen?

Ja. Lege jedes Landfeld in eine eigene Menge und beginne die Zählung mit der Anzahl der Landfelder. Verbinde jedes Paar benachbarter Landfelder und verringere die Zählung jeweils um eins, wenn durch eine Verbindung zwei verschiedene Mengen zusammengeführt werden. Mit Pfadkompression liegt die Laufzeit nahe bei O(Zeilen × Spalten).

Kannst du Inseln ohne ein separates Array für besuchte Inseln zählen?

Ja, wenn du die Karte ändern darfst: Wandle jedes Landfeld in Wasser um, sobald du es erreichst. Viele Sprachen können Zeichenfolgen nicht direkt ändern, daher kopierst du zuerst die Zeilen in ein Zeichengitter. Das benötigt genauso viel Speicherplatz wie die Markierungen für bereits besuchte Felder.

def numIslands(grid):
    # Schreibe hier den Code

Test #1

Test #2

Argument

grid = ["11000", "11000", "00100", "00011"]

Erwartete Ausgabe