力扣热题 100：图论专题经典题解析

在力扣（LeetCode）平台上，图论相关的题目是算法面试和练习中的重要部门。本日，我们就来具体解析图论专题中的几道经典题目，帮助各人更好地明白解题思路和技巧。
一、岛屿数目（题目 200）

1. 题目描述

给定一个由 ‘0’（水）和 ‘1’（陆地）组成的二维网格，计算此中岛屿的数目。岛屿被水包围，且由相邻的陆地相连（程度或垂直）。
2. 示例

示例 1：
输入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
输出：1
示例 2：
输入：grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
输出：3
3. 解题思路

这道题重要考察深度优先搜索（DFS）或广度优先搜索（BFS）的应用。我们可以遍历网格中的每个元素，当遇到陆地时，将其标记为已访问，并递归或迭代地访问其相邻的陆地，直到所有相连的陆地都被访问过。
4. 代码实现（Java）

1. public class Solution {
2.     public int numIslands(char[][] grid) {
3.         if (grid == null || grid.length == 0) {
4.             return 0;
5.         }
6.         int rows = grid.length;
7.         int cols = grid[0].length;
8.         int count = 0;
9.         for (int i = 0; i < rows; i++) {
10.             for (int j = 0; j < cols; j++) {
11.                 if (grid[i][j] == '1') {
12.                     count++;
13.                     dfs(grid, i, j);
14.                 }
15.             }
16.         }
17.         return count;
18.     }
20.     private void dfs(char[][] grid, int i, int j) {
21.         if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {
22.             return;
23.         }
24.         grid[i][j] = '0';
25.         dfs(grid, i + 1, j);
26.         dfs(grid, i - 1, j);
27.         dfs(grid, i, j + 1);
28.         dfs(grid, i, j - 1);
29.     }
30. }

复制代码

5. 复杂度分析

• 时间复杂度 ：O(m * n)，此中 m 和 n 分别是网格的行数和列数。我们必要遍历每个元素一次。
  
• 空间复杂度 ：O(m * n)，在最坏情况下，递归调用栈的深度可能达到 m * n。
  

二、腐烂的橘子（题目 994）

1. 题目描述

给定一个二维网格，此中 ‘0’ 体现空单位格，‘1’ 体现奇怪橘子，‘2’ 体现腐烂橘子。每分钟，腐烂的橘子会使其上下左右的奇怪橘子腐烂。返回所有奇怪橘子腐烂的最小分钟数。假如不可能，返回 -1。
2. 示例

示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2：
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
3. 解题思路

这道题重要考察广度优先搜索（BFS）的应用。我们可以将所有腐烂的橘子作为初始节点，同时进行 BFS，逐层腐烂相邻的奇怪橘子。在 BFS 过程中记录时间，并在末了查抄是否还有奇怪橘子未腐烂。
4. 代码实现（Java）

1. import java.util.LinkedList;
2. import java.util.Queue;
4. public class Solution {
5.     public int orangesRotting(int[][] grid) {
6.         int rows = grid.length;
7.         int cols = grid[0].length;
8.         Queue<int[]> queue = new LinkedList<>();
9.         int fresh = 0;
10.         for (int i = 0; i < rows; i++) {
11.             for (int j = 0; j < cols; j++) {
12.                 if (grid[i][j] == 2) {
13.                     queue.offer(new int[]{i, j});
14.                 } else if (grid[i][j] == 1) {
15.                     fresh++;
16.                 }
17.             }
18.         }
19.         if (fresh == 0) {
20.             return 0;
21.         }
22.         int minutes = 0;
23.         int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
24.         while (!queue.isEmpty()) {
25.             int size = queue.size();
26.             for (int i = 0; i < size; i++) {
27.                 int[] cell = queue.poll();
28.                 for (int[] dir : directions) {
29.                     int r = cell[0] + dir[0];
30.                     int c = cell[1] + dir[1];
31.                     if (r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] == 1) {
32.                         grid[r][c] = 2;
33.                         fresh--;
34.                         queue.offer(new int[]{r, c});
35.                     }
36.                 }
37.             }
38.             minutes++;
39.         }
40.         return fresh == 0 ? minutes - 1 : -1;
41.     }
42. }

复制代码

5. 复杂度分析

• 时间复杂度 ：O(m * n)，此中 m 和 n 分别是网格的行数和列数。我们必要遍历每个元素一次。
  
• 空间复杂度 ：O(m * n)，在最坏情况下，队列中可能存储所有腐烂的橘子。
  

三、课程表（题目 207）

1. 题目描述

给定一个整数 numCourses 体现课程数目，以及一个列表 prerequisites，此中 prerequisites = [ai, bi] 体现想要学习课程 ai 必须先学习课程 bi。判断是否可以完成所有课程。
2. 示例

示例 1：
输入：numCourses = 2, prerequisites = [[1, 0]]
输出：true
解释：可以先修课程 0，再修课程 1。
示例 2：
输入：numCourses = 2, prerequisites = [[1, 0], [0, 1]]
输出：false
解释：存在环，无法完成所有课程。
3. 解题思路

这道题重要考察拓扑排序的应用。我们可以使用广度优先搜索（BFS）来检测图中是否存在环。具体步调如下：

• 构建图的邻接表体现，并计算每个节点的入度。
  
• 将入度为 0 的节点加入队列。
  
• 遍历队列中的节点，淘汰其邻人节点的入度，假如邻人节点的入度变为 0，则加入队列。
  
• 末了查抄是否所有节点都被访问过，假如是，则可以完成所有课程；否则，存在环，无法完成。
  

4. 代码实现（Java）

1. import java.util.ArrayList;
2. import java.util.LinkedList;
3. import java.util.List;
4. import java.util.Queue;
6. public class Solution {
7.     public boolean canFinish(int numCourses, int[][] prerequisites) {
8.         List<List<Integer>> adj = new ArrayList<>();
9.         for (int i = 0; i < numCourses; i++) {
10.             adj.add(new ArrayList<>());
11.         }
12.         int[] inDegree = new int[numCourses];
13.         for (int[] pre : prerequisites) {
14.             adj.get(pre[1]).add(pre[0]);
15.             inDegree[pre[0]]++;
16.         }
17.         Queue<Integer> queue = new LinkedList<>();
18.         for (int i = 0; i < numCourses; i++) {
19.             if (inDegree[i] == 0) {
20.                 queue.offer(i);
21.             }
22.         }
23.         int count = 0;
24.         while (!queue.isEmpty()) {
25.             int node = queue.poll();
26.             count++;
27.             for (int neighbor : adj.get(node)) {
28.                 inDegree[neighbor]--;
29.                 if (inDegree[neighbor] == 0) {
30.                     queue.offer(neighbor);
31.                 }
32.             }
33.         }
34.         return count == numCourses;
35.     }
36. }

复制代码

5. 复杂度分析

• 时间复杂度 ：O(V + E)，此中 V 是课程数目，E 是先修关系数目。我们必要遍历所有节点和边。
  
• 空间复杂度 ：O(V + E)，必要存储图的邻接表和入度数组。
  

四、实现 Trie（前缀树）（题目 208）

1. 题目描述

实现一个 Trie（前缀树），包罗以下方法：

• Trie() ：初始化前缀树。
  
• insert(String word) ：将字符串 word 插入前缀树。
  
• search(String word) ：假如字符串 word 存在于前缀树中，则返回 true，否则返回 false。
  
• startsWith(String prefix) ：假如存在以 prefix 为前缀的字符串，则返回 true，否则返回 false。
  

2. 示例

示例 1：
输入：

1. ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
2. [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

复制代码

输出：

1. [null, null, true, false, true, null, true]

复制代码

3. 解题思路

这道题重要考察前缀树的实现。前缀树是一种树形数据布局，用于高效地存储和检索字符串聚集。每个节点体现一个字符，并包罗指向子节点的链接。具体步调如下：

• 创建一个 TrieNode 类，包罗一个字符数组（或哈希表）来存储子节点，以及一个标志位体现是否是单词的结尾。
  
• 在 Trie 类中，维护一个根节点，初始化时创建。
  
• 插入操作：从根节点开始，逐字符遍历字符串，假如当前字符不存在于当前节点的子节点中，则创建新节点。遍历竣事后，将末了一个节点的标志位置为 true。
  
• 搜索操作：从根节点开始，逐字符遍历字符串，假如当前字符不存在于当前节点的子节点中，则返回 false。遍历竣事后，查抄末了一个节点的标志位是否为 true。
  
• 前缀匹配操作：与搜索操作雷同，但不必要查抄标志位，只必要遍历完整个前缀即可。
  

4. 代码实现（Java）

1. class TrieNode {
2.     TrieNode[] children;
3.     boolean isEnd;
5.     public TrieNode() {
6.         children = new TrieNode[26];
7.         isEnd = false;
8.     }
9. }
11. public class Trie {
12.     private TrieNode root;
14.     public Trie() {
15.         root = new TrieNode();
16.     }
18.     public void insert(String word) {
19.         TrieNode node = root;
20.         for (char c : word.toCharArray()) {
21.             int index = c - 'a';
22.             if (node.children[index] == null) {
23.                 node.children[index] = new TrieNode();
24.             }
25.             node = node.children[index];
26.         }
27.         node.isEnd = true;
28.     }
30.     public boolean search(String word) {
31.         TrieNode node = root;
32.         for (char c : word.toCharArray()) {
33.             int index = c - 'a';
34.             if (node.children[index] == null) {
35.                 return false;
36.             }
37.             node = node.children[index];
38.         }
39.         return node.isEnd;
40.     }
42.     public boolean startsWith(String prefix) {
43.         TrieNode node = root;
44.         for (char c : prefix.toCharArray()) {
45.             int index = c - 'a';
46.             if (node.children[index] == null) {
47.                 return false;
48.             }
49.             node = node.children[index];
50.         }
51.         return true;
52.     }
53. }

复制代码

5. 复杂度分析

• 时间复杂度 ：对于插入、搜索和前缀匹配操作，时间复杂度均为 O(L)，此中 L 是字符串的长度。我们必要遍历每个字符一次。
  
• 空间复杂度 ：O(1)，每个节点的子节点数目固定为 26（假设只包罗小写字母）。
  

以上就是力扣热题 100 中与图论相关的经典题目的具体解析，希望对各人有所帮助。在实际刷题过程中，建议各人多动手实践，明白解题思路的本质，这样才气更好地应对各种算法题目。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。