一、岛屿数量
中等
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 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提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]的值为'0'或'1'
1.1 dfs
上上下下左右左右BABA
遇到海水则直接返回，因为我们只关心陆地
遇到新的陆地，递归该格子的上下左右，为避免重复计数，直接把该片陆地变为海洋即可
class Solution {
/**
* 200. 岛屿数量（dfs）
*
* @param grid 岛屿分布数组
* @return 岛屿个数
*/
public int numIslands(char[][] grid) {
int r = grid.length;
int c = grid[0].length;
int ans = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
// 如果是陆地，说明是一个新的岛
if (grid[i][j] == '1') ans++;
dfs(grid, i, j);
}
}
return ans;
}
public void dfs(char[][] grid, int r, int c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return;
if (grid[r][c] == '0') return; // 如果是水，不考虑直接返回
grid[r][c] = '0'; // 每访问一片新的岛屿，直接递归上下左右把其变成海
dfs(grid, r + 1, c);
dfs(grid, r - 1, c);
dfs(grid, r, c + 1);
dfs(grid, r, c - 1);
}
}执行用时4ms，击败37.50%，复杂度O(M * N)
消耗内存51.72MB，击败5.18%，复杂度O(M * N)
二、腐烂的橘子
中等
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值
0代表空单元格； - 值
1代表新鲜橘子； - 值
2代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4示例 2：
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。示例 3：
输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j]仅为0、1或2
2.1 bfs
bfs：最短路径问题、传播问题
dfs：所有可能路径问题（回溯）、连通问题、拓扑排序（课程安排、任务调度依赖）
最短腐烂时间，每一分钟腐烂四个方向，即每分钟上下左右可以走一步，系最短路径问题，应用bfs
先统计新鲜橘子数量、找到所有初始的腐烂源，把腐烂源放入队列
每开始新的一轮腐烂，先获取当前队列长度作为循环终点，防止同一轮腐烂俩波橘子
class Solution {
/**
* 994. 腐烂的橘子（bfs）
*
* @param grid 橘子分布矩阵
* @return 腐烂总时长
*/
public int orangesRotting(int[][] grid) {
int r = grid.length;
int c = grid[0].length;
// 腐烂橘子的位置
Queue<int[]> queue = new LinkedList<>();
int fresh = 0; // 新鲜橘子的数量
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (grid[i][j] == 1) {
fresh++;
} else if (grid[i][j] == 2) {
queue.add(new int[]{i, j});
}
}
}
int ans = 0;
while (fresh > 0 && !queue.isEmpty()) {
ans++;
int size = queue.size();
for (int i = 0; i < size; i++) {
// 弹出腐烂橘子的坐标
int[] orange = queue.poll();
int row = orange[0];
int col = orange[1];
// 感染上方橘子
if (row - 1 >= 0 && grid[row - 1][col] == 1) {
grid[row - 1][col] = 2;
fresh--;
queue.add(new int[]{row - 1, col});
}
// 下
if (row + 1 < r && grid[row + 1][col] == 1) {
grid[row + 1][col] = 2;
fresh--;
queue.add(new int[]{row + 1, col});
}
// 左
if (col - 1 >= 0 && grid[row][col - 1] == 1) {
grid[row][col - 1] = 2;
fresh--;
queue.add(new int[]{row, col - 1});
}
// 右
if (col + 1 < c && grid[row][col + 1] == 1) {
grid[row][col + 1] = 2;
fresh--;
queue.add(new int[]{row, col + 1});
}
}
}
return fresh > 0 ? -1 : ans;
}
}三、课程表
中等
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。提示：
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesprerequisites[i]中的所有课程对 互不相同
3.1 三色dfs
注意到所有课程无法修完，说明存在左脚踩右脚的情况——所有参数组成了几个环
依题意，[后修课（终点）， 先修课（起点）]
下边介绍俩个东西：
List<Integer>[] adj = new ArrayList[numCourses];
adj 是 “adjacency list”（邻接表）的缩写，存储的是从课程 i 出发可以到达的所有课程
三色标记法是一种在图遍历（特别是DFS）中用来检测环和进行拓扑排序的标记方法。它将图中的节点分为三种状态：
- 白色（White） - 0：节点尚未访问
- 灰色（Gray） - 1：节点正在访问中（在当前DFS递归栈中）
- 黑色（Black） - 2：节点已访问完成（不在当前递归栈中）
如果DFS过程中遇到灰色节点，说明存在回边（back edge）, 即有环
class Solution {
/**
* 207. 课程表（dfs）
*
* @param numCourses 需要修的课程总数
* @param prerequisites 课程学习顺序
* @return 能否修完
*/
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 将题目所给二维数组转换为邻接表
List<Integer>[] adj = new ArrayList[numCourses];
for (int i = 0; i < numCourses; i++) adj[i] = new ArrayList<>();
for (int[] p : prerequisites) {
int late = p[0], pre = p[1];
adj[pre].add(late); // 有向边 pre -> late
}
// 颜色标记数组，用于DFS中检测环
// 0: 白色 - 未访问（unvisited）
// 1: 灰色 - 访问中（visiting，在当前DFS递归栈中）
// 2: 黑色 - 已访问完成（visited，不在当前递归栈中）
int[] color = new int[numCourses]; // 0 unvisited, 1 visiting, 2 visited
// 遍历所有课程（图的所有顶点）
for (int i = 0; i < numCourses; i++) {
// 只从未访问的节点开始DFS
if (color[i] == 0) {
// 如果发现环，则无法完成所有课程
if (dfs(i, adj, color)) {
return false;
}
}
}
return true;
}
private boolean dfs(int u, List<Integer>[] adj, int[] color) {
// 标识当前节点正在递归访问中
color[u] = 1;
// 遍历邻接表
for (int v : adj[u]) {
if (color[v] == 0) {
if (dfs(v, adj, color)) return true;
} else if (color[v] == 1) {
// 找到回边，存在有向环
return true;
}
}
// 标识当前节点已递归访问完
color[u] = 2;
return false;
}
}四、实现 Trie (前缀树)
中等
Trie↗（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
示例：
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True提示：
1 <= word.length, prefix.length <= 2000word和prefix仅由小写英文字母组成insert、search和startsWith调用次数 总计 不超过3 * 10^4次
4.1 暴力穷举
创建俩个HashSet<String>，一个prefix用来存储每个插入字符串的所有前缀，一个origin用来存储每个插入的字符串
由于只需要前缀，所以遍历整个插入的字符串word，截取前i个字符存入prefix即可
class Trie {
private Set<String> prefix;
private Set<String> origin;
/**
* 208. 实现 Trie (暴力穷举）
*/
public Trie() {
this.prefix = new HashSet<>();
this.origin = new HashSet<>();
}
public void insert(String word) {
for (int i = 1; i <= word.length(); i++) {
this.prefix.add(word.substring(0, i));
}
this.origin.add(word);
}
public boolean search(String word) {
return this.origin.contains(word);
}
public boolean startsWith(String prefix) {
return this.prefix.contains(prefix);
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/执行用时149ms，击败5.07%
消耗内存59.61MB，击败53.93%
4.2 二十六叉树
由于题目限定小写字母，我们可以只定义一个长度为26的数组，比如存入apple
对于a，在'a' - 'a' = 0的数组下标处新建一个长度为26的数组，表示a ?
对于p，在'p' - 'a' = 16的数组下标处新建一个长度为26的数组，表示ap ?
- 再存入
p，即app? - …完整存入了
apple，标识为end
此时再插入一个api
对于a，下标为0处已经存在，直接进入，即a?
对于p，下标为16处已经存在，直接进入，即ap?
由上可知，只需要按顺序从浅到深遍历Tire[]，一旦发现null，就说明这个前缀不存在
class Trie {
private Trie[] dictionary;
private boolean isEnd;
/**
* 208. 实现 Trie (字典树）
*/
public Trie() {
this.dictionary = new Trie[26];
this.isEnd = false;
}
public void insert(String word) {
Trie cur = this;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (cur.dictionary[index] == null) cur.dictionary[index] = new Trie();
cur = cur.dictionary[index];
}
cur.isEnd = true;
}
public boolean search(String word) {
Trie cur = this;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (cur.dictionary[index] == null) return false;
cur = cur.dictionary[index];
}
return cur.isEnd;
}
public boolean startsWith(String prefix) {
Trie cur = this;
for (int i = 0; i < prefix.length(); i++) {
int index = prefix.charAt(i) - 'a';
if (cur.dictionary[index] == null) return false;
cur = cur.dictionary[index];
}
return true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/执行用时30ms，击败82.01%
消耗内存60.95MB，击败15.68%
Thanks for reading!
力扣hot100-《图论》章节题解
周二 12月 30 2025 图论
2775 字 · 17 分钟