力扣热题-100图论专题经典题解析
力扣热题 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）
public class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
int count = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {
return;
}
grid[i][j] = '0';
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
}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）
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public int orangesRotting(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int fresh = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 2) {
queue.offer(new int[]{i, j});
} else if (grid[i][j] == 1) {
fresh++;
}
}
}
if (fresh == 0) {
return 0;
}
int minutes = 0;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cell = queue.poll();
for (int[] dir : directions) {
int r = cell[0] + dir[0];
int c = cell[1] + dir[1];
if (r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] == 1) {
grid[r][c] = 2;
fresh--;
queue.offer(new int[]{r, c});
}
}
}
minutes++;
}
return fresh == 0 ? minutes - 1 : -1;
}
}5. 复杂度分析
- 时间复杂度 ：O(m * n)，其中 m 和 n 分别是网格的行数和列数。我们需要遍历每个元素一次。
- 空间复杂度 ：O(m * n)，在最坏情况下，队列中可能存储所有腐烂的橘子。
三、课程表（题目 207）
1. 题目描述
给定一个整数
numCourses
表示课程数目，以及一个列表
prerequisites
，其中
prerequisites[i] = [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）
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
adj.add(new ArrayList<>());
}
int[] inDegree = new int[numCourses];
for (int[] pre : prerequisites) {
adj.get(pre[1]).add(pre[0]);
inDegree[pre[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int count = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
count++;
for (int neighbor : adj.get(node)) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
queue.offer(neighbor);
}
}
}
return count == numCourses;
}
}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：
输入：
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]输出：
[null, null, true, false, true, null, true]3. 解题思路
这道题主要考察前缀树的实现。前缀树是一种树形数据结构，用于高效地存储和检索字符串集合。每个节点表示一个字符，并包含指向子节点的链接。具体步骤如下：
- 创建一个 TrieNode 类，包含一个字符数组（或哈希表）来存储子节点，以及一个标志位表示是否是单词的结尾。
- 在 Trie 类中，维护一个根节点，初始化时创建。
- 插入操作：从根节点开始，逐字符遍历字符串，如果当前字符不存在于当前节点的子节点中，则创建新节点。遍历结束后，将最后一个节点的标志位置为
true。 - 搜索操作：从根节点开始，逐字符遍历字符串，如果当前字符不存在于当前节点的子节点中，则返回
false。遍历结束后，检查最后一个节点的标志位是否为true。 - 前缀匹配操作：与搜索操作类似，但不需要检查标志位，只需要遍历完整个前缀即可。
4. 代码实现（Java）
class TrieNode {
TrieNode[] children;
boolean isEnd;
public TrieNode() {
children = new TrieNode[26];
isEnd = false;
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEnd = true;
}
public boolean search(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
return node.isEnd;
}
public boolean startsWith(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
}
return true;
}
}5. 复杂度分析
- 时间复杂度 ：对于插入、搜索和前缀匹配操作，时间复杂度均为 O(L)，其中 L 是字符串的长度。我们需要遍历每个字符一次。
- 空间复杂度 ：O(1)，每个节点的子节点数目固定为 26（假设只包含小写字母）。
以上就是力扣热题 100 中与图论相关的经典题目的详细解析，希望对大家有所帮助。在实际刷题过程中，建议大家多动手实践，理解解题思路的本质，这样才能更好地应对各种算法问题。
