1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「LeetCode每日一题」—— 200. 岛屿数量

200. 岛屿数量

链接:https://leetcode-cn.com/problems/number-of-islands/
难度:中等

思路

这题比较简单,思路就是DFS。

我们需要找到所有的连着的"1",然后答案自增1,后面继续寻找没有被访问过了"1",我们可以把访问过了的"1"变成"0",因为我们对"0"的区域没有做任何操作。

代码见解决方案

方案代码

解决方案:

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid: return 0
        
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1
                    
        return count
    
    def dfs(self, grid, i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
            return 
        grid[i][j] = '0'
        self.dfs(grid, i + 1, j)
        self.dfs(grid, i - 1, j)
        self.dfs(grid, i, j + 1)
        self.dfs(grid, i, j - 1)

原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/340.html