LeetCode-Hot100-图论

前言

题单LeetCode 热题 100的图论部分，给出解析。

200. Number of Islands

题目描述

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

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

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

解题方法

这个问题要求我们计算二维二进制网格中“岛屿”的数量。岛屿是由相连的陆地（'1'）组成的区域，并且被水（'0'）包围。相邻的陆地可以通过上下左右方向连接在一起。

解题思路：

遍历整个网格：
- 对于每一个格子，如果该格子是陆地（即'1'），那么我们就找到一个新的岛屿。
- 发现新岛屿后，使用深度优先搜索（DFS）或广度优先搜索（BFS）将该岛屿的所有相连的陆地格子都标记为已访问过（可以将其值改为'0'或其他值）。
DFS/BFS 的作用：
- 从某个陆地格子出发，通过递归（DFS）或队列（BFS）将与其相连的所有陆地格子都访问并标记，这样我们就可以确定该岛屿的边界。
- 这样做之后，所有与该岛屿相连的格子就不会再被误认为是新的岛屿。
时间复杂度：
- 每个格子最多只会被访问一次，所以时间复杂度为 $O(m×n)$，其中 $m$ 是网格的行数，$n$ 是网格的列数。

代码实现

DFS 实现：

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:  # 如果输入为空，直接返回 0
            return 0

        def dfs(i, j):
            # 如果索引越界或遇到水（'0'），则返回
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
                return
            # 将当前陆地（'1'）标记为已访问（改为 '0'，避免重复访问）
            grid[i][j] = '0'
            # 向上下左右四个方向继续深度优先搜索
            dfs(i + 1, j)  # 下
            dfs(i - 1, j)  # 上
            dfs(i, j + 1)  # 右
            dfs(i, j - 1)  # 左

        count = 0  # 记录岛屿数量的计数器
        # 遍历整个网格
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # 如果遇到陆地（'1'）
                if grid[i][j] == '1':
                    count += 1  # 岛屿数量加 1
                    dfs(i, j)   # 使用 DFS 搜索整座岛屿，将其所有陆地标记为水（'0'）

        return count  # 返回岛屿的数量

BFS 实现：

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0

        def bfs(i, j):
            queue = [(i, j)]
            # 将当前陆地标记为已访问（即变为 '0'）
            grid[i][j] = '0'
            # 方向数组，表示上下左右四个方向
            directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
            
            # 开始广度优先搜索
            while queue:
                x, y = queue.pop()
                # 遍历四个方向
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    # 检查是否越界以及是否为陆地
                    if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] == '1':
                        grid[nx][ny] = '0'  # 标记为已访问
                        queue.append((nx, ny))

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':  # 遇到陆地
                    count += 1  # 岛屿数量加 1
                    bfs(i, j)   # 广度优先搜索，标记相连的所有陆地为水

        return count

复杂度分析

时间复杂度：$O(m×n)$（$m$ 与 $n$ 为行数与列数）

空间复杂度：$O(m×n)$

994. Rotting Oranges

原题链接

题目描述

You are given an m x n grid where each cell can have one of three values:

0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example 1:

1 2	Input: grid = [[2,1,1],[1,1,0],[0,1,1]] Output: 4

Example 2:

1
2
3

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

1
2
3

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] is 0, 1, or 2.

解题方法

这道题的目标是模拟橙子腐烂的过程，腐烂的橙子会在每分钟四个方向（上下左右）传播给周围的新鲜橙子。如果最后所有的新鲜橙子都变成腐烂橙子，返回经过的最短分钟数；如果无法让所有新鲜橙子都腐烂，返回 -1。

这个问题可以使用广度优先搜索（BFS）来解决，把腐烂的橙子作为起始点，然后模拟它们向周围的四个方向传播，直到没有新鲜橙子为止。

解题思路：

初始化：
- 我们需要记录初始腐烂橙子的位置，作为BFS的起点。每次腐烂传播时，周围的相邻新鲜橙子会变成腐烂橙子。
- 如果最后还有新鲜橙子没腐烂，或者根本没有新鲜橙子，应该返回 -1。
BFS模拟：
- 遍历整个网格，找到所有腐烂橙子的位置，把它们放入队列中。每分钟，腐烂橙子会传播到其相邻的所有新鲜橙子。
- 用一个变量来记录经过的分钟数。
终止条件：
- 如果所有的腐烂橙子都传播完成，检查是否还有剩余的新鲜橙子。如果有，就返回 -1。
- 如果所有的新鲜橙子都腐烂了，返回经过的分钟数。

代码实现

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        
        # Initialize the queue and count of fresh oranges
        queue = deque()
        fresh_count = 0
        
        # Traverse the grid to find all initial rotten oranges and count fresh ones
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    queue.append((r, c))  # Add rotten orange to the queue
                elif grid[r][c] == 1:
                    fresh_count += 1  # Count fresh oranges
        
        # Directions for 4-directional movement (up, down, left, right)
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        # BFS to rot fresh oranges
        minutes = 0
        while queue and fresh_count > 0:
            # Process all rotten oranges in the current level (minute)
            for _ in range(len(queue)):
                r, c = queue.popleft()
                
                # Check all 4 adjacent directions
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        grid[nr][nc] = 2  # Make it rotten
                        fresh_count -= 1  # Decrease the fresh orange count
                        queue.append((nr, nc))  # Add new rotten orange to the queue
            
            minutes += 1  # Increment time after processing one level of BFS
        
        # If there are still fresh oranges left, it's impossible to rot them
        if fresh_count > 0:
            return -1
        
        return minutes

复杂度分析

时间复杂度：$O(m×n)$，其中 $m$ 是行数，$n$ 是列数。我们最多遍历网格每个格子一次。

空间复杂度：$O(m×n)$，用于存储队列中腐烂橙子的数量，最多可能存储整个网格。

207. Course Schedule

原题链接

题目描述

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
All the pairs prerequisites[i] are unique .

解题方法

题目大意为：课程表上有一些课，有着修学分的先后顺序，必须在上完某些课的情况下才能上下一门，分析是否有方案修完所有的课程。

即题目需要判断这些课程是否能够构成有向无环图（DAG）

DFS

题目需要判断这些课程是否能够构成有向无环图（DAG），判断 DAG 使用拓扑排序。

采用 DFS 解答，思路如下：

解决思路：

图的表示：将课程和它们的依赖关系表示为一个邻接表。每个课程是一个节点，先修课程是有向边。
状态表示：
- **未访问 (0)**：课程尚未被访问。
- **访问中 (-1)**：课程正在当前的DFS路径中被访问（检测是否存在环的标志）。
- **已访问 (1)**：课程已经被访问，并且从该课程开始没有发现环。
环的检测：
- 使用DFS遍历每个课程。如果在DFS过程中遇到一个正在访问中的课程（状态为-1），则说明存在环，返回false。
- 如果DFS成功完成没有发现环，则返回true。

拓扑排序

同样的，可以使用拓扑排序来解决判断有向无环图的问题。

解决思路：

图的表示：同样使用邻接表表示课程和它们的依赖关系。
入度表示：每个课程的入度表示需要先修的课程数量。
拓扑排序：
- 初始化一个队列，将所有入度为0的课程加入队列。
- 从队列中依次取出课程，并减少相应依赖它的课程的入度。如果某个课程的入度减少为0，则将其加入队列。
- 如果最终处理的课程数量等于numCourses，则可以完成所有课程，否则说明存在环，无法完成所有课程。

代码实现

DFS

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 1. 初始化图和状态数组
        graph = [[] for _ in range(numCourses)]
        visited = [0] * numCourses
        
        # 2. 构建图：邻接表表示
        for course, prereq in prerequisites:
            graph[prereq].append(course)
        
        # 3. 定义DFS函数
        def dfs(course):
            # 如果该节点正在访问，说明找到了环
            if visited[course] == 1:
                return False
            # 如果该节点已经访问过，说明没有环
            if visited[course] == 2:
                return True
            
            # 标记该节点为正在访问
            visited[course] = 1
            
            # 递归访问该课程的后续课程
            for next_course in graph[course]:
                if not dfs(next_course):
                    return False
            
            # 递归结束后，标记该节点为已访问
            visited[course] = 2
            return True
        
        # 4. 遍历每个课程，进行DFS检测是否有环
        for i in range(numCourses):
            if not dfs(i):
                return False
        
        # 5. 如果所有课程都没有形成环，返回True
        return True

拓扑排序

from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 1. 初始化入度数组和邻接表
        indegree = [0] * numCourses
        adj_list = [[] for _ in range(numCourses)]
        
        # 2. 构建图：统计每门课的入度，建立邻接表
        for course, prereq in prerequisites:
            indegree[course] += 1
            adj_list[prereq].append(course)
        
        # 3. 将所有入度为0的课程加入队列
        queue = deque([i for i in range(numCourses) if indegree[i] == 0])
        
        # 4. 拓扑排序：依次处理队列中的课程
        processed_courses = 0
        while queue:
            course = queue.popleft()
            processed_courses += 1
            
            # 遍历该课程的后继课程，将其入度减1
            for next_course in adj_list[course]:
                indegree[next_course] -= 1
                # 如果入度变为0，则加入队列
                if indegree[next_course] == 0:
                    queue.append(next_course)
        
        # 5. 如果处理的课程数等于总课程数，说明可以完成所有课程
        return processed_courses == numCourses

复杂度分析

两个方法的复杂度是一样的。

时间复杂度：$O(V+E)$

空间复杂度：$O(V+E)$

208. Implement Trie (Prefix Tree)

原题链接

题目描述

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints:

1 <= word.length, prefix.length <= 2000
word and prefix consist only of lowercase English letters.
At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.

解题方法

要实现 Trie 类，可以使用一种常见的方法——使用字典来模拟树的节点，每个节点存储字母以及一个标志，表示是否为某个单词的结尾。

代码实现

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        node = self._search(word)
        return node is not None and node.is_end_of_word

    def startsWith(self, prefix: str) -> bool:
        return self._search(prefix) is not None

    def _search(self, prefix: str) -> TrieNode:
        # 辅助方法，用于查找给定前缀的最后一个节点
        node = self.root  # 从根节点开始
        for char in prefix:
            # 如果当前字符不在子节点中，返回None
            if char not in node.children:
                return None
            # 移动到下一个节点
            node = node.children[char]
        # 返回前缀的最后一个节点
        return node

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

复杂度分析

无