西部数据网站备案流程,太原小店区最新消息今天,wordpress 论坛整合,常德经开区网站问题模板 为什么要将格子标记为【已遍历】—避免 重复遍历 #xff08;这是因为#xff0c;网格结构本质上是一个「图」#xff0c;我们可以把每个格子看成图中的结点#xff0c;每个结点有向上下左右的四条边。在图中遍历时#xff0c;自然可能遇到重复遍历结点。这时候这是因为网格结构本质上是一个「图」我们可以把每个格子看成图中的结点每个结点有向上下左右的四条边。在图中遍历时自然可能遇到重复遍历结点。这时候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(gridnull||grid.length0)return 0;int cnt0;int mgrid.length;int n grid[0].length;for(int i0;im;i){for(int j0;jn;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返回值变成了 1dfs(上下左右)的面积
class Solution {public int maxAreaOfIsland(int[][] grid) {int m grid.length;int n grid[0].length;int max_area0;for(int i 0;im;i){for(int j0;jn;j){int temp_areadfs(grid,i,j);max_areaMath.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 1dfs(grid,r-1,c)dfs(grid,r1,c)dfs(grid,r,c-1)dfs(grid,r,c1);}boolean inArea(int[][] grid,int r,int c){return r0rgrid.lengthc0cgrid[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;Queueint[] 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 (r1 M grid[r1][c] 1) {grid[r1][c] 2;count--;queue.add(new int[]{r1, c});}if (c-1 0 grid[r][c-1] 1) {grid[r][c-1] 2;count--;queue.add(new int[]{r, c-1});}if (c1 N grid[r][c1] 1) {grid[r][c1] 2;count--;queue.add(new int[]{r, c1});}}}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];ListListInteger adjacent new ArrayList();QueueInteger list new LinkedList();for(int i0;inumCourses;i)adjacent.add(new ArrayList());for(int[] tmp : prerequisites) {indegree[tmp[0]];adjacent.get(tmp[1]).add(tmp[0]);}//将所以入度为0的节点入队for(int i0;inumCourses;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 numCourses0;}
}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();nodenode.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;}nodenode.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;}nodenode.next[c-a];}return true;}
}
注意 startwith和search的区别 startwith 走完prefix循环就可以返回true; 而search走完循环还要看是不是到最终的叶结点了 不然 比如word为prefix 而树中是prefixxx 也会错误的search为true
