200. 岛屿数量 - 力扣（LeetCode）算法框架
网格问题的基本概念
我们首先明确一下岛屿问题中的网格结构是如何定义的，以方便我们后面的讨论。
网格问题是由m×n个小方格组成一个网格，每个小方格与其上下左右四个方格认为是相邻的，要在这样的网格上进行某种搜索。
岛屿问题是一类典型的网格问题。每个格子中的数字可能是 0 或者 1。我们把数字为 0 的格子看成海洋格子，数字为 1 的格子看成陆地格子，这样相邻的陆地格子就连接成一个岛屿。
在这样一个设定下，就出现了各种岛屿问题的变种，包括岛屿的数量、面积、周长等。不过这些问题，基本都可以用 DFS 遍历来解决。
DFS 的基本结构
网格结构要比二叉树结构稍微复杂一些，它其实是一种简化版的图结构。要写好网格上的 DFS 遍历，我们首先要理解二叉树上的 DFS 遍历方法，再类比写出网格结构上的 DFS 遍历。我们写的二叉树 DFS 遍历一般是这样的：
第一个要素是访问相邻结点。二叉树的相邻结点非常简单，只有左子结点和右子结点两个。二叉树本身就是一个递归定义的结构：一棵二叉树，它的左子树和右子树也是一棵二叉树。那么我们的 DFS 遍历只需要递归调用左子树和右子树即可。
第二个要素是判断 base case。一般来说，二叉树遍历的 base case 是root == null。这样一个条件判断其实有两个含义：一方面，这表示root指向的子树为空，不需要再往下遍历了。另一方面，在root == null的时候及时返回，可以让后面的root.left和root.right操作不会出现空指针异常。
对于网格上的 DFS，我们完全可以参考二叉树的 DFS，写出网格 DFS 的两个要素：
首先，网格结构中的格子有多少相邻结点？答案是上下左右四个。对于格子(r, c)来说（r 和 c 分别代表行坐标和列坐标），四个相邻的格子分别是(r-1, c)、(r+1, c)、(r, c-1)、(r, c+1)。换句话说，网格结构是「四叉」的。
其次，网格 DFS 中的 base case 是什么？从二叉树的 base case 对应过来，应该是网格中不需要继续遍历、grid[r][c]会出现数组下标越界异常的格子，也就是那些超出网格范围的格子。
这一点稍微有些反直觉，坐标竟然可以临时超出网格的范围？这种方法我称为「先污染后治理」—— 甭管当前是在哪个格子，先往四个方向走一步再说，如果发现走出了网格范围再赶紧返回。这跟二叉树的遍历方法是一样的，先递归调用，发现root == null再返回。
。
这一点稍微有些反直觉，坐标竟然可以临时超出网格的范围？这种方法我称为「先污染后治理」—— 甭管当前是在哪个格子，先往四个方向走一步再说，如果发现走出了网格范围再赶紧返回。这跟二叉树的遍历方法是一样的，先递归调用，发现root == null再返回。
这样，我们得到了网格 DFS 遍历的框架代码：
如何避免重复遍历
网格结构的 DFS 与二叉树的 DFS 最大的不同之处在于，遍历中可能遇到遍历过的结点。这是因为，网格结构本质上是一个「图」，我们可以把每个格子看成图中的结点，每个结点有向上下左右的四条边。在图中遍历时，自然可能遇到重复遍历结点。
这时候，DFS 可能会不停地「兜圈子」，永远停不下来，如下图所示：
如何避免这样的重复遍历呢？答案是标记已经遍历过的格子。以岛屿问题为例，我们需要在所有值为 1 的陆地格子上做 DFS 遍历。每走过一个陆地格子，就把格子的值改为 2，这样当我们遇到 2 的时候，就知道这是遍历过的格子了。也就是说，每个格子可能取三个值：
0 —— 海洋格子
1 —— 陆地格子（未遍历过）
2 —— 陆地格子（已遍历过）
我们在框架代码中加入避免重复遍历的语句：
void dfs(int[][] grid, int r, int c) {
// 判断 base case
if (!inArea(grid, r, c)) {
return;
}
// 如果这个格子不是岛屿，直接返回
if (grid[r][c] != 1) {
return;
}
grid[r][c] = 2; // 将格子标记为「已遍历过」
// 访问上、下、左、右四个相邻结点
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}
这样，我们就得到了一个岛屿问题、乃至各种网格问题的通用 DFS 遍历方法。以下所讲的几个例题，其实都只需要在 DFS 遍历框架上稍加修改而已。
200. 岛屿数量 - 力扣（LeetCode）
当代码在遍历二维数组
grid时，发现一个未被访问的陆地单元格（即grid[i][j] == '1'）。每当发现一个新的陆地单元格时，调用
dfs函数从该单元格开始深度优先搜索，将整个岛屿的所有陆地标记为已访问。关键点：每次调用
dfs函数时，count的值会增加 1，表示找到了一个新的岛屿。
class Solution {
public int numIslands(char[][] grid) {
//岛屿数量
int count=0;
//这个两层for循环是用来遍历整张二维表格中所有的陆地
//其中 i 表示行，j 表示列
for(int i=0;i<grid.length;i++)
{
for(int j=0;j<grid[0].length;j++)
{
//取出所有的陆地
if(grid[i][j] == '1'){
//深度递归，遍历所有的陆地
dfs(grid,i,j);
//用来统计有多少岛屿，岛屿是由多个陆地组成的，概念不一样
count++;
}
}
}
return count;
}
public void dfs(char[][] grid,int i, int j){
//防止 i 和 j 越界，也就是防止超出岛屿（上下左右）的范围。特别注意当遍历到海洋的时候也退出循环
if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]!='1') return;
//将遍历过的陆地改为已访问，防止重复遍历
grid[i][j]='2';
//上，
dfs(grid,i+1,j);
//下
dfs(grid,i-1,j);
//右
dfs(grid,i,j+1);
//左
dfs(grid,i,j-1);
}
}994. 腐烂的橘子 - 力扣（LeetCode）
BFS 可以看成是层序遍历。从某个结点出发，BFS 首先遍历到距离为 1 的结点，然后是距离为 2、3、4…… 的结点。因此，BFS 可以用来求最短路径问题。BFS 先搜索到的结点，一定是距离最近的结点。
再看看这道题的题目要求：返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。翻译一下，实际上就是求腐烂橘子到所有新鲜橘子的最短路径。那么这道题使用 BFS，应该是毫无疑问的了。
1. 初始化阶段
统计新鲜橘子的数量，
count++。记录所有腐烂橘子的位置，放到队列
queue中
2. BFS 时间层级迭代处理
time 用于记录经过的分钟数。
BFS 循环：
当队列不为空且仍有新鲜橘子时while（
count > 0 && !queue.isEmpty()），纵向层序。每次循环表示一分钟，
time++。for循环当前层级的腐烂橘子数量
queue.size()。对于每个腐烂橘子，调用
rotting方法，尝试将其上下左右相邻的新鲜橘子变成腐烂的橘子。
3. rotting 方法
检查 若
(i, j)是否越界，或者是否是空单元格（0）或已经腐烂的橘子（2）就返回。腐烂传播：
如果
(i, j)是新鲜橘子（grid[i][j] == 1），将其变成腐烂的橘子（grid[i][j] = 2）。将其位置
(i, j)添加到队列中，以便后续处理。新鲜橘子数量
count--。
4. 返回结果
如果最终仍有新鲜橘子（
count > 0），返回-1，表示无法使所有橘子腐烂。否则，返回经过的分钟数
time。class Solution { int count = 0; Queue<int[]> queue = new LinkedList<int[]>(); public int orangesRotting(int[][] grid) { int r = grid.length; int c = grid[0].length; //第一次遍历 扫描新鲜橘子和腐烂橘子分别记录 for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (grid[i][j] == 1) { count++;//新鲜橘子 } else if (grid[i][j] == 2) { queue.add(new int[]{i, j});//烂橘子 } } } //时间次数 int time = 0; //时间层级迭代处理 while (count > 0 && !queue.isEmpty()) { time++; int n = queue.size(); for (int i = 0; i < n; i++) { int[] orange = queue.poll(); int or = orange[0]; int oc = orange[1]; //获取腐烂橘子向四周扩散 rotting(grid, or - 1, oc);//上 rotting(grid, or + 1, oc);//下 rotting(grid, or, oc - 1);//左 rotting(grid, or, oc + 1);//右 } } //判断返回值 if (count > 0) { return -1; } else { return time; }} private void rotting(int[][] grid, int i, int j) { int r = grid.length; int c = grid[0].length; if (i < 0 || i >= r || j < 0 || j >= c || grid[i][j] == 0 || grid[i][j] == 2) { return; } if (grid[i][j] == 1) { grid[i][j] = 2; count--; queue.add(new int[]{i, j}); } } }207. 课程表 - 力扣（LeetCode）
- 拓扑排序：每次选入度为0的点。然后删除这个点和他的出边
每次只能选你能上的课
每次只能选入度为 0 的课，因为它不依赖别的课，是当下你能上的课。
假设选了 0，课 3 的先修课少了一门，入度由 2 变 1。
接着选 1，导致课 3 的入度变 0，课 4 的入度由 2 变 1。
接着选 2，导致课 4 的入度变 0。
现在，课 3 和课 4 的入度为 0。继续选入度为 0 的课……直到选不到入度为 0 的课。这很像 二叉树的BFS
让入度为 0 的课（二叉树最上层）入列，它们是能直接选的课。
然后逐个出列，出列代表着课被选，需要1.通过邻接表找到后续课程，2.减小相关课的入度。
如果相关课的入度新变为 0，安排它入列、再出列……直到没有入度为 0 的课可入列。public class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { // 入度数组 int[] inDegree = new int[numCourses]; // 邻接表 Map<Integer, List<Integer>> map = new HashMap<>(); // 构建入度数组和邻接表 for (int[] prerequisite : prerequisites) { int course = prerequisite[0]; int prerequisiteCourse = prerequisite[1]; // 每门课的入度需要被记录，我们关心入度值的变化。 inDegree[course]++; // 课程之间的依赖关系也要被记录 邻接表：用哈希表记录依赖关系 // key：课号 // value：依赖这门课的后续课（数组） if (!map.containsKey(prerequisiteCourse)) { map.put(prerequisiteCourse, new ArrayList<>()); } map.get(prerequisiteCourse).add(course); } // 所有入度为0的课程入队 Queue<Integer> queue = new LinkedList<>(); //让入度为 0 的课入列，它们是能直接选的课。 // 然后逐个出列，出列代表着课被选，需要减小相关课的入度。 // 如果相关课的入度新变为 0，安排它入列、再出列……直到没有入度为 0 的课可入列。 for (int i = 0; i < numCourses; i++) { if (inDegree[i] == 0) { queue.offer(i); } } int count = 0; // 已完成的课程数 while (!queue.isEmpty()) { int selected = queue.poll(); // 当前选的课，出队 count++; // 选课数+1 // 获取这门课对应的后续课 List<Integer> toEnQueue = map.get(selected); if (toEnQueue != null) { for (int nextCourse : toEnQueue) { inDegree[nextCourse]--; // 依赖它的后续课的入度-1 if (inDegree[nextCourse] == 0) { // 如果入度减为0，入队 queue.offer(nextCourse); } } } // 如果所有课程都被选了，返回 true，否则返回 false return count == numCourses; } }208. 实现 Trie (前缀树) - 力扣（LeetCode）
难点在于构造树，我们声明每个节点，维护两个值：
1.当前节点是否为一个单词的末尾字母。
2.当前节点的下一个节点可以去哪个字母。（下一个节点维护着一些字母
插入
描述：向 Trie 中插入一个单词 word
实现：这个操作和构建链表很像。首先从根结点root的子结点开始与 word 第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，这时开始不断开辟新的结点，直到插入完 word 的最后一个字符，同时还要将最后一个结点isEnd = true;，表示它是一个单词的末尾。
精确搜索search就是不断去看与word中对应的每一个字母，下一个节点是否维护了这个字母。最后要判断当前节点是否为end，不然就是前缀了。
class Trie {
class TrieNode {
private boolean isEnd;
TrieNode[] next;
public TrieNode() {
isEnd = false;
next = new TrieNode[26];
}
}
//根节点
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// 插入单词到 Trie 中
public void insert(String word) {
//定位当前节点
TrieNode node=root;//root是空的哦！！！！！！！！！
for (char c : word.toCharArray()) {
int index = c - 'a'; // 计算字符对应的索引
if (node.next[index] == null) {
node.next[index] = new TrieNode(); // 如果当前节点为空，创建新节点
}
node = node.next[index]; // 移动到下一个节点
}
node.isEnd = true; // 标记单词的结尾
}
//精确搜索
public boolean search(String word) {
TrieNode node=root;
for(char c:word.toCharArray())
{
int index=c-'a';
if(node.next[index]==null)
{
return false;
}
node=node.next[index];
}
return node.isEnd;//还要判断是否到了结尾
}
public boolean startsWith(String prefix) {
TrieNode node=root;
for(char c:prefix.toCharArray())
{
int index=c-'a';
if(node.next[index]==null)
{
return false;
}
node=node.next[index];
}
return true;//与前面比，判断是否遍历完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);
*/