Graph

[Notes] Graph

Posted by 西维蜀黍的OJ Blog on 2023-09-10, Last Modified on 2025-04-16

解析

130. Surrounded Regions

ref

133. Clone Graph

  • 用 DFS 不断地递归创建未创建过的节点
    • 如果已经创建过了，直接从 oldToNew 里返回新节点
  • DFS/BFS 的区别是先创建最 deepth 的节点还是先创建最 close 的节点
    # DFS
    #  - time: O(nodes + edges)
    #  - space: O(nodes), oldToNew 用了 O(nodes)，calling stack for recursion 用了 O(nodes)
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        oldToNew = {}

        def dfs(oldNode):
            if oldNode in oldToNew:
                return oldToNew[oldNode]

            newNode = Node(oldNode.val)
            oldToNew[oldNode] = newNode
            for neighbor in oldNode.neighbors:
                newNode.neighbors.append(dfs(neighbor))
            return newNode

        if not node:
            return None
        return dfs(node)
      
    # BFS
    #  - time: O(nodes + edges)
    #  - space: O(nodes)
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        if not node:
            return None

        oldToNew = {node: Node(node.val)}
        queue = [node]
        while queue:
            oldNode = queue.pop(0)
            for nei in oldNode.neighbors:
                if nei not in oldToNew:
                    newNei = Node(nei.val)
                    oldToNew[nei] = newNei
                    queue.append(nei)
                oldToNew[oldNode].neighbors.append(oldToNew[nei])
        return oldToNew[node]

ref

200. Number of Islands

  • 用一个 set 记录已经访问过的节点，然后用 DFS/BFS 不断去寻找 island，直到所有节点都被访问了
  • 可以优化成 访问过的"1"节点置为 “0”，从而不需要 visit
# BFS
    #  - time: O(m*n)
    #  - space: O(m*n)
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if len(grid) == 0:
            return 0

        visit = set()
        islands = 0
        ROW, COL = len(grid), len(grid[0])

        def bfs(r, c):
            queue = [(r, c)]
            visit.add((r, c))
            while queue:
                r, c = queue.pop(0)
                directions = [[0, -1], [0, 1], [1, 0], [-1, 0]]
                # BFS 去访问上下左右的元素
                for direction in directions:
                    newR, newC = r + direction[0], c + direction[1]
                    if (0 <= newR < ROW and
                            0 <= newC < COL and
                            (newR, newC) not in visit and
                            grid[newR][newC] == "1"):
                        queue.append((newR, newC))
                        visit.add((newR, newC))

        for row in range(ROW):
            for col in range(COL):
                if grid[row][col] == "1" and (row, col) not in visit:
                    bfs(row, col)
                    islands += 1

        return islands
      
# DFS - 使用 visit
    #  - time: O(m*n)
    #  - space: O(m*n), visit 使用了 O(m*n)
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if len(grid) == 0:
            return 0

        visit = set()
        islands = 0
        ROW, COL = len(grid), len(grid[0])

        def dfs(r, c):
            if r < 0 or r == ROW or c < 0 or c == COL or grid[r][c] == "0" or (r, c) in visit:
                return

            visit.add((r, c))
            directions = [[0, -1], [0, 1], [-1, 0], [1, 0]]
            for direction in directions:
                newRow, newCol = r + direction[0], c + direction[1]
                dfs(newRow, newCol)

        for row in range(ROW):
            for col in range(COL):
                if grid[row][col] == "1" and (row, col) not in visit:
                    dfs(row, col)
                    islands += 1

        return islands  

# DFS - 不使用 visit
#  - time: O(m*n)
#  - space: O(m*n), recursion stack uses o(m*n)
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        islands = 0
        ROW = len(grid)
        COL = len(grid[0])
        directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]

        def dfs(row, col):
            if row < 0 or row >= ROW or col < 0 or col >= COL or grid[row][col] == "0":
                return

            grid[row][col] = "0"  # 把已经访问过island的土地置为"0"，已标识该土地已经被访问过了
            for direction in directions:
                newRow = direction[0] + row
                newCol = direction[1] + col
                dfs(newRow, newCol)

        for r in range(ROW):
            for c in range(COL):
                if grid[r][c] == "1":  # 只有发现 island 时，才 dfs
                    # dfs 把该岛屿的所有土地都置为 "0"，然后更新 islands
                    dfs(r, c)
                    islands += 1

        return islands

ref

695. Max Area of Island

  • 用一个 set 记录已经访问过的节点，然后用 DFS/BFS 不断去寻找 island 并计算每个已访问 island 的大小，直到所有节点都被访问了
  • 可以优化成 访问过的"1"节点置为 “0”，从而不需要 visit
    # BFS
    #  - time: O(m*n)
    #  - space: O(m*n)
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        visit = set()
        res = 0
        ROW, COL = len(grid), len(grid[0])

        def bfs(row, col):
            maxArea = 1
            queue = [(row, col)]
            visit.add((row, col))
            directions = [[0, -1], [0, 1], [-1, 0], [1, 0]]
            while queue:
                r, c = queue.pop(0)
                for direction in directions:
                    newRow, newCol = r + direction[0], c + direction[1]
                    if 0 <= newRow < ROW and 0 <= newCol < COL and grid[newRow][newCol] == 1 and (
                            newRow, newCol) not in visit:
                        maxArea += 1
                        visit.add((newRow, newCol))
                        queue.append((newRow, newCol))
            return maxArea

        for row in range(ROW):
            for col in range(COL):
                if grid[row][col] == 1 and (row, col) not in visit:
                    res = max(res, bfs(row, col))
        return res
      
# DFS
    #  - time: O(m*n)
    #  - space: O(m*n)
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        visit = set()
        res = 0
        ROW, COL = len(grid), len(grid[0])

        def dfs(row, col):
            if row < 0 or row == ROW or col < 0 or col == COL or (row, col) in visit or grid[row][col] == 0:
                return 0

            visit.add((row, col))
            return (1
                    + dfs(row + 1, col)
                    + dfs(row - 1, col)
                    + dfs(row, col + 1)
                    + dfs(row, col - 1)
                    )

        for row in range(ROW):
            for col in range(COL):
                if grid[row][col] == 1 and (row, col) not in visit:
                    res = max(res, dfs(row, col))
        return res

ref

286 · Walls and Gates

ref

417. Pacific Atlantic Water Flow

ref

684. Redundant Connection

ref

994. Rotting Oranges

ref

FEATURED TAGS
hashmap leetcode lintcode matrix sortarray topic tree 剑指刷题

TOC