Board相关题

原创

王脸小

修改于 2020-07-28 17:59:27

7300

修改于 2020-07-28 17:59:27

文章被收录于专栏：王漂亮王漂亮

200. 岛屿数量

Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

Solution-DFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        row = len(grid)
        col = len(grid[0]) if row else 0
    
        if not row or not col: return 0
        res = 0
        
        def dfs(i,j):
            grid[i][j] = 0
            for x,y in [(0,1),(0,-1),(1,0),(-1,0)]:
                if 0<=i+x<row and 0<=j+y<col and grid[i+x][j+y]=="1":
                    dfs(i+x,j+y)
                    
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
                    dfs(i,j)
                    res += 1

        return res

Solution-BFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        row = len(grid)
        col = len(grid[0]) if row else 0
    
        if not row or not col: return 0
        res = 0
        
        def bfs(i,j):
            grid[i][j] == "0"
            q = [(i,j)]
            
            while q:
                i,j = q.pop()
                for x,y in [(0,1),(0,-1),(1,0),(-1,0)]:
                    if 0<=i+x<row and 0<=j+y<col and grid[i+x][j+y]=="1":
                        q.append((i+x,j+y))
                        grid[i+x][j+y] = "0"
                        
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
                    bfs(i,j)
                    res += 1
                    
        return res

Solution-UF

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        row = len(grid)
        col = len(grid[0]) if row else 0
    
        if not row or not col: return 0
        
        dummy_node = row*col
        uf = UnionFind(dummy_node+1)
        
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "0":
                    uf.Union(dummy_node, i*col+j)
                if grid[i][j] == "1":
                    for x,y in [(0,1), (1,0)]:
                        if i+x<row and j+y<col and grid[i+x][j+y] == '1':
                            uf.Union((i+x)*col+(j+y), (i*col)+j)
                            
        return uf.Count()-1

UnionFind Class

并查集(Union-Find)算法介绍 link

并查集（参考leetcode323题）link

class UnionFind:
    def __init__(self, n):
        self.count = n
        self.parent = [i for i in range(n)]

    def Find(self, p):
        while p != self.parent[p]:
            self.parent[p] = self.parent[self.parent[p]]
            p = self.parent[p]
        return self.parent[p]

    def Union(self, p, q):
        p_root = self.Find(p)
        q_root = self.Find(q)
        self.parent[p_root] = q_root
        
        self.count -= 1

    def Count(self):
        return self.count

    def is_connected(self, p, q):
        return self.Find(p) == self.Find(q)

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

count