问题模板
为什么要将格子标记为【已遍历】—避免 重复遍历
（这是因为，网格结构本质上是一个「图」，我们可以把每个格子看成图中的结点，每个结点有向上下左右的四条边。在图中遍历时，自然可能遇到重复遍历结点。这时候，DFS 可能会不停地「兜圈子」，永远停不下来

void dfs(int[][] grid, int r, int c) {// 判断 base caseif (!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;
}

200. 岛屿数量

class Solution {public int numIslands(char[][] grid) {if(grid==null||grid.length==0)return 0;int cnt=0;int m=grid.length;int n =grid[0].length;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]=='1'){cnt++;dfs(grid,i,j);}}}return cnt;}void dfs(char[][] grid, int r, int c) {// 判断 base caseif (!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(char[][] grid, int r, int c) {return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;}
}

695. 岛屿的最大面积

这道题同样根据dfs模板走，只不过区别是dfs返回值变成了 1+dfs(上下左右)的面积

class Solution {public int maxAreaOfIsland(int[][] grid) {int m = grid.length;int n = grid[0].length;int max_area=0;for(int i = 0;i<m;i++){for(int j=0;j<n;j++){int temp_area=dfs(grid,i,j);max_area=Math.max(max_area,temp_area);}}return max_area;}int  dfs(int[][] grid,int r,int c){int m = grid.length;int n= grid[0].length;if(!inArea(grid,r,c))return 0;//不是岛屿 直接返回if(grid[r][c]!=1)return 0;grid[r][c]=2;return 1+dfs(grid,r-1,c)+dfs(grid,r+1,c)+dfs(grid,r,c-1)+dfs(grid,r,c+1);}boolean inArea(int[][] grid,int r,int c){return r>=0&&r<grid.length&&c>=0&&c<grid[0].length;}
}

463. 岛屿的周长

岛屿的周长是计算岛屿全部的「边缘」，而这些边缘就是我们在 DFS 遍历中，dfs 函数返回的位置。
当我们的 dfs 函数因为「坐标 (r, c) 超出网格范围」返回的时候，实际上就经过了一条黄色的边；而当函数因为「当前格子是海洋格子」返回的时候，实际上就经过了一条蓝色的边

class Solution {public int islandPerimeter(int[][] grid) {for (int r = 0; r < grid.length; r++) {for (int c = 0; c < grid[0].length; c++) {if (grid[r][c] == 1) {// 题目限制只有一个岛屿，计算一个即可return dfs(grid, r, c);}}}return 0;}int dfs(int[][] grid, int r, int c) {// 函数因为「坐标 (r, c) 超出网格范围」返回，对应一条黄色的边if (!inArea(grid, r, c)) {return 1;}// 函数因为「当前格子是海洋格子」返回，对应一条蓝色的边if (grid[r][c] == 0) {return 1;}// 函数因为「当前格子是已遍历的陆地格子」返回，和周长没关系if (grid[r][c] != 1) {return 0;}grid[r][c] = 2;return 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;}
}

另一类bfs问题

994. 腐烂的橘子

想象以污染的橘子为污染源，然后将相邻的橘子一层一层污染，考虑BFS

class Solution{
public int orangesRotting(int[][] grid) {int M = grid.length;int N = grid[0].length;Queue<int[]> queue = new LinkedList<>();int count = 0; // count 表示新鲜橘子的数量for (int r = 0; r < M; r++) {for (int c = 0; c < N; c++) {if (grid[r][c] == 1) {count++;} //一开始，我们找出所有腐烂的橘子，将它们放入队列，作为第 0 层的结点。//就是污染源else if (grid[r][c] == 2) {queue.add(new int[]{r, c});}}}int round = 0; // round 表示腐烂的轮数，或者分钟数while (count > 0 && !queue.isEmpty()) {round++;int n = queue.size();for (int i = 0; i < n; i++) {int[] orange = queue.poll();int r = orange[0];int c = orange[1];//将相邻方向依次污染if (r-1 >= 0 && grid[r-1][c] == 1) {grid[r-1][c] = 2;count--;queue.add(new int[]{r-1, c});}if (r+1 < M && grid[r+1][c] == 1) {grid[r+1][c] = 2;count--;queue.add(new int[]{r+1, c});}if (c-1 >= 0 && grid[r][c-1] == 1) {grid[r][c-1] = 2;count--;queue.add(new int[]{r, c-1});}if (c+1 < N && grid[r][c+1] == 1) {grid[r][c+1] = 2;count--;queue.add(new int[]{r, c+1});}}}if (count > 0) {return -1;} else {return round;}
}
}

207. 课程表

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {//判断是否是有向无环图-------》拓扑排序//通过课程前置条件列表 prerequisites 可以得到课程安排图的 邻接表 adjacency//统计课程安排图中每个节点的入度，生成 入度表 indegrees。//借助一个队列 queue，将所有入度为 0 的节点入队。//拓扑排序过程//删顶点 再把顶点的出边删掉，即对应所有邻接节点的入度-1//当入度 −1后邻接节点 cur 的入度为 0，说明 cur 所有的前驱节点已经被 “删除”，//此时将 cur 入队。int[] indegree = new int[numCourses];List<List<Integer>> adjacent  = new ArrayList<>();Queue<Integer> list = new LinkedList<>();for(int i=0;i<numCourses;i++)adjacent.add(new ArrayList<>());for(int[] tmp : prerequisites) {indegree[tmp[0]]++;adjacent.get(tmp[1]).add(tmp[0]);}//将所以入度为0的节点入队for(int i=0;i<numCourses;i++){if(indegree[i]==0)list.add(i);}//排序过程while(!list.isEmpty()){int pre =list.poll();numCourses--;//他的邻接节点入度--for(int tmp :adjacent.get(pre)){indegree[tmp]--;if(indegree[tmp]==0)list.add(tmp);}}return numCourses==0;}
}

208. 实现 Trie (前缀树)

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();}public void insert(String word) {TrieNode node = root;for(char c : word.toCharArray()){if(node.next[c-'a']==null)node.next[c-'a']=new TrieNode();node=node.next[c-'a'];}node.isEnd = true;}public boolean search(String word) {TrieNode node = root;for(char c :word.toCharArray()){if(node.next[c-'a']==null){return false;}node=node.next[c-'a'];}return node.isEnd;}public boolean startsWith(String prefix) {TrieNode node = root;for(char c :prefix.toCharArray()){if(node.next[c-'a']==null){return false;}node=node.next[c-'a'];}return true;}
}

注意 startwith和search的区别
startwith 走完prefix循环就可以返回true;
而search走完循环还要看是不是到最终的叶结点了
不然 比如word为prefix 而树中是prefixxx 也会错误的search为true