[PYTHON] Leet Code "200. Anzahl der Inseln" Kommentar

Überblick

Es scheint, dass es viele ausländische Unternehmen gibt, die Codierungstests in Interviews mit Ingenieuren durchführen. Der Ort der letzten Frage des Codierungstests ist Let Code Ich habe nicht vor, es anzunehmen, aber ich löse jeden Tag eine Frage zum Lernen

Problem

200. Number of Islands Die Schwierigkeit ist mittel

Sie erhalten folgende Eingabe In einem kartenähnlichen Bild steht 1 für Land und 0 für Meer. Eine Insel entsteht auf angrenzendem Land Die erforderliche Ausgabe ist die Anzahl der Inseln Im folgenden Beispiel befinden sich oben links, in der Mitte und unten rechts 3 Inseln, sodass 3 die Ausgabe ist

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Lösung

Schauen Sie von der Kante und wiederholen Sie das Folgende

1. Wenn Sie eine Insel finden, markieren Sie das gesamte Land auf dieser Insel als besucht
2. 1 Inselzähler hinzufügen

python

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        
        #Machen Sie das ganze Land der Insel besucht
        def check(i,j):            
            if grid[i][j]=="1":        
                #Machen Sie es besucht
                grid[i][j]="2"                
                #Besuchen Sie rekursiv benachbarte Gebiete nach oben, unten, links und rechts
                if i-1>=0:
                    check(i-1,j)
                if j-1>=0:
                    check(i,j-1)
                if i+1<=len(grid)-1:
                    check(i+1,j)
                if j+1<=len(grid[0])-1:
                    check(i,j+1)                                            
        
        #Inselzähler
        count=0
            
        #grid[0][0]Ich werde es mir in der Reihenfolge von ansehen
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                #Wenn es Land wäre
                if grid[i][j]=="1":
                    #Machen Sie das ganze Land der Insel besucht
                    check(i,j)
                    #1 Inselzähler hinzufügen
                    count+=1                
        return count