Commentaire du Leet Code "200. Nombre d'îles"

Aperçu

Il semble que de nombreuses sociétés étrangères affiliées effectuent des tests de codage lors d'entretiens avec des ingénieurs. Le site de la question précédente du test de codage est Let Code Je n'ai pas l'intention de le prendre, mais je résous une question chaque jour pour étudier

problème

200. Number of Islands La difficulté est moyenne

Vous recevrez l'entrée suivante Dans une image de type carte, 1 représente la terre et 0 représente la mer. Une île est créée sur un terrain adjacent La sortie requise est le nombre d'îles Dans l'exemple ci-dessous, il y a 3 îles en haut à gauche, au milieu et en bas à droite, donc 3 est la sortie

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

Solution

Regardez du bord et répétez ce qui suit

1. Si vous trouvez une île, marquez toutes les terres de cette île comme visitées
2. Ajoutez 1 compteur d'îles

python

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        
        #Faites visiter toute la terre de l'île
        def check(i,j):            
            if grid[i][j]=="1":        
                #Faites-le visiter
                grid[i][j]="2"                
                #Visitez récursivement les terres adjacentes en haut, en bas, à gauche et à droite
                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)                                            
        
        #Compteur d'îles
        count=0
            
        #grid[0][0]Je vais le regarder dans l'ordre de
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                #Si c'était la terre
                if grid[i][j]=="1":
                    #Faites visiter toute la terre de l'île
                    check(i,j)
                    #Ajouter 1 compteur d'îles
                    count+=1                
        return count