本文为力扣TOP100刷题笔记
笔者根据数据结构理论加上最近刷题整理了一套 数据结构理论加常用方法以下为该文章：
200. 岛屿数量
class Solution {
// DFS辅助方法，用于标记和"淹没"岛屿
void dfs(char[][] grid, int r, int c) {
int nr = grid.length; // 网格行数
int nc = grid[0].length; // 网格列数
// 边界检查及是否陆地的检查
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}
// 将当前陆地标记为已访问（'0'表示水或已访问）
grid[r][c] = '0';
// 向四个方向递归搜索
dfs(grid, r - 1, c); // 上
dfs(grid, r + 1, c); // 下
dfs(grid, r, c - 1); // 左
dfs(grid, r, c + 1); // 右
}
public int numIslands(char[][] grid) {
// 处理空网格的情况
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length; // 网格行数
int nc = grid[0].length; // 网格列数
int num_islands = 0; // 岛屿计数器
// 遍历整个网格
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
// 发现新岛屿
if (grid[r][c] == '1') {
++num_islands; // 增加岛屿计数
dfs(grid, r, c); // "淹没"整个岛屿
}
}
}
return num_islands;
}
}关键点解释
DFS标记过程：
将访问到的'1'标记为'0'，避免重复计数
向四个方向（上、下、左、右）递归搜索相连的陆地
岛屿计数逻辑：
每次遇到未被访问的'1'，表示发现新岛屿
调用DFS"淹没"整个岛屿，确保不会重复计数
边界条件处理：
检查网格坐标是否越界
处理空网格输入的情况
示例演示
给定网格：
text
1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1执行过程：
发现(0,0)的'1'，计数+1，DFS淹没左上角2×2岛屿
跳过已访问/水区域
发现(2,2)的'1'，计数+1，DFS淹没该孤立点
发现(3,3)的'1'，计数+1，DFS淹没右下角2×1岛屿
最终岛屿数量：3
994. 腐烂的橘子
class Solution {
public int orangesRotting(int[][] grid) {
if (grid == null || grid.length == 0) return -1;
int rows = grid.length;
int cols = grid[0].length;
int minutes = 0;
while (true) {
boolean changed = false;
int[][] newGrid = new int[rows][cols];
// 复制当前网格状态
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
newGrid[i][j] = grid[i][j];
}
}
// 递归处理每个橘子
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 2) {
changed |= infectAdjacent(grid, newGrid, i, j, rows, cols);
}
}
}
// 如果没有变化，退出循环
if (!changed) break;
// 更新网格并增加分钟数
grid = newGrid;
minutes++;
}
// 检查是否还有新鲜橘子
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 1) return -1;
}
}
return minutes;
}
// 递归感染相邻橘子的辅助方法
private boolean infectAdjacent(int[][] grid, int[][] newGrid, int i, int j, int rows, int cols) {
boolean changed = false;
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int[] dir : directions) {
int x = i + dir[0];
int y = j + dir[1];
if (x >= 0 && y >= 0 && x < rows && y < cols && grid[x][y] == 1) {
newGrid[x][y] = 2;
changed = true;
}
}
return changed;
}
}递归思路解析
外层循环：每分钟处理一次腐烂过程
网格复制：创建新网格来记录下一分钟的状态
递归处理：
遍历每个腐烂橘子(值为2)
使用
infectAdjacent方法递归感染相邻的新鲜橘子终止条件：
当没有更多橘子可以被感染时退出循环
最后检查是否还有剩余的新鲜橘子
为什么这不是纯递归
实际上，这个问题不太适合纯递归解决，因为：
多源点问题：多个腐烂橘子需要同时扩散
时间步长：需要按分钟同步处理所有腐烂
上面的解决方案使用了递归辅助方法，但整体结构仍然是迭代的（每分钟处理一次）。
纯递归的局限性
如果非要实现纯递归版本，会遇到以下问题：
难以同步时间：所有腐烂过程无法同步进行
重复计算：同一个橘子可能被多次处理
栈溢出风险：对于大网格会超出调用栈深度
207. 课程表
class Solution {
// 邻接表，存储图的边关系，edges.get(i)表示课程i的所有后续课程
List<List<Integer>> edges;
// 记录每个节点的访问状态：0=未访问，1=访问中，2=已访问完成
int[] visited;
// 全局标志，表示当前是否没有发现环（能否完成所有课程）
boolean valid = true;
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 初始化邻接表
edges = new ArrayList<List<Integer>>();
for (int i = 0; i < numCourses; ++i) {
edges.add(new ArrayList<Integer>());
}
// 初始化访问状态数组
visited = new int[numCourses];
// 构建图的边关系
// prerequisites中的每个元素[1,0]表示要学习课程1必须先完成课程0
// 所以在邻接表中，我们添加边 0→1
for (int[] info : prerequisites) {
edges.get(info[1]).add(info[0]);
}
// 对每个未访问的节点执行DFS
for (int i = 0; i < numCourses && valid; ++i) {
if (visited[i] == 0) {
dfs(i);
}
}
// 如果整个过程中没有发现环，则可以完成所有课程
return valid;
}
public void dfs(int u) {
// 标记当前节点为"访问中"
visited[u] = 1;
// 遍历当前节点的所有邻接节点（后续课程）
for (int v: edges.get(u)) {
// 如果邻接节点未被访问，递归访问
if (visited[v] == 0) {
dfs(v);
// 如果在递归过程中发现环，提前返回
if (!valid) {
return;
}
}
// 如果邻接节点正在访问中（在递归栈中），说明发现环
else if (visited[v] == 1) {
valid = false;
return;
}
// 如果邻接节点已访问完成(2)，不需要处理
}
// 当前节点访问完成，标记为"已访问"
visited[u] = 2;
}
}关键注释说明
邻接表edges：
使用ArrayList的ArrayList实现
edges.get(i)获取课程i的所有直接后续课程列表visited数组三种状态：
0：白色，未访问节点
1：灰色，正在访问中的节点（在递归栈中）
2：黑色，已完全访问完成的节点环检测逻辑：
在DFS过程中，如果遇到灰色节点（状态1），说明存在环
因为灰色节点表示该节点在当前的递归调用栈中，再次遇到说明形成了环
DFS过程：
先将节点标记为灰色（访问中）
递归访问所有邻接节点
最后将节点标记为黑色（访问完成）
提前终止：
一旦发现环（valid=false），立即终止后续的DFS过程
这个算法有效地利用DFS实现了有向无环图(DAG)的检测，解决了课程安排问题。
208. 实现 Trie (前缀树)
class Trie {
// 每个Trie节点包含：
// 1. 一个长度为26的子节点数组（对应26个小写字母）
// 2. 一个布尔值标记是否是某个单词的结尾
private Trie[] children;
private boolean isEnd;
// 构造函数：初始化一个空的Trie节点
public Trie() {
children = new Trie[26]; // 26个字母的子节点
isEnd = false; // 初始时不是单词结尾
}
// 向Trie中插入一个单词
public void insert(String word) {
Trie node = this; // 从根节点开始
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a'; // 计算字母对应的索引(0-25)
// 如果当前字符对应的子节点不存在，则创建新的子节点
if (node.children[index] == null) {
node.children[index] = new Trie();
}
// 移动到子节点
node = node.children[index];
}
// 标记单词的最后一个字符节点为结尾
node.isEnd = true;
}
// 搜索Trie中是否存在完整的单词
public boolean search(String word) {
Trie node = searchPrefix(word);
// 不仅要找到前缀，最后一个节点还必须标记为单词结尾
return node != null && node.isEnd;
}
// 检查Trie中是否有以给定前缀开头的单词
public boolean startsWith(String prefix) {
// 只需要找到前缀路径存在即可
return searchPrefix(prefix) != null;
}
// 私有辅助方法：搜索前缀
private Trie searchPrefix(String prefix) {
Trie node = this; // 从根节点开始
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
int index = ch - 'a'; // 计算字母对应的索引(0-25)
// 如果当前字符对应的子节点不存在，返回null
if (node.children[index] == null) {
return null;
}
// 移动到子节点
node = node.children[index];
}
// 返回前缀的最后一个字符节点
return node;
}
}关键注释说明
数据结构设计：
children数组：每个元素对应一个字母（a-z），存储指向子Trie节点的引用
isEnd标志：标记当前节点是否是某个单词的结尾插入操作(insert)：
从根节点开始，逐个字符处理
对于每个字符，检查对应的子节点是否存在，不存在则创建
最后将单词的最后一个字符节点标记为结尾
搜索操作(search)：
使用searchPrefix方法找到前缀的最后一个节点
检查该节点是否存在且被标记为单词结尾
前缀检查(startsWith)：
只需要检查前缀路径是否存在，不关心是否是完整单词
辅助方法(searchPrefix)：
通用的前缀查找方法
被search和startsWith方法复用
返回前缀路径的最后一个节点（如果存在）
时间复杂度分析
插入：O(L)，L为单词长度
搜索：O(L)，L为单词长度
前缀检查：O(P)，P为前缀长度
空间复杂度
最坏情况：O(N×M)，N是单词数量，M是平均单词长度
实际中由于共享前缀，空间效率通常比哈希表更好
这个Trie实现特别适合处理字符串的前缀相关问题，如自动补全、拼写检查等场景。