力扣top100(day03-02)--图论
本文为力扣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→1for (int[] info : prerequisites) {edges.get(info[1]).add(info[0]);}// 对每个未访问的节点执行DFSfor (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)// 如果当前字符对应的子节点不存在，返回nullif (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实现特别适合处理字符串的前缀相关问题，如自动补全、拼写检查等场景。