Hot100中的：图论专题

图模板图分为有向图和无向图入度是指向当前节点的边数出度是当前节点指向其他节点的边数200.岛屿数量关键信息一句话总结遍历网格遇到陆地就用 DFS / BFS 把整块连通陆地淹掉并计数方法1BFSclassSolution{publicintnumIslands(char[][]grid){// bfs是这样的 联想我们之前的二叉树// bfs一层一层是左右节点延申出去的// 而这里的图是上下左右四个方向表示一层所以bfs可以一层一层intmgrid.length;intngrid[0].length;intcount0;for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1){bfs(grid,i,j);count;}}}returncount;}privatevoidbfs(char[][]grid,inti,intj){intmgrid.length;intngrid[0].length;Queueint[]queuenewLinkedList();queue.offer(newint[]{i,j});grid[i][j]0;while(!queue.isEmpty()){int[]curqueue.poll();intxcur[0];intycur[1];int[][]dirs{{1,0},{-1,0},{0,1},{0,-1}};for(int[]d:dirs){intnxxd[0];intnyyd[1];if(nx0nxmny0nyngrid[nx][ny]1){queue.offer(newint[]{nx,ny});grid[nx][ny]0;}}}}}方法2DFSclassSolution{publicintnumIslands(char[][]grid){intcount0;intmgrid.length;intngrid[0].length;for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1){dfs(grid,i,j);count;}}}returncount;}privatevoiddfs(char[][]grid,inti,intj){intmgrid.length;intngrid[0].length;if(im||i0||jn||j0||grid[i][j]0){return;}// 把当前陆地淹没grid[i][j]0;// 四个方向搜索dfs(grid,i-1,j);dfs(grid,i,j1);dfs(grid,i1,j);dfs(grid,i,j-1);}}方法3并查集1.什么是并查集并查集 用来判断两个东西是不是在同一个集合里它解决了判断这两个点是不是连在一起的问题classSolution{publicintnumIslands(char[][]grid){intmgrid.length;intngrid[0].length;UnionFindufnewUnionFind(m*n);intcount0;// 1.统计所有1for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1){count;}}}// 2.合并相邻的1for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1){// 有i行 每行n个 所以 i * n 在j列 所以 i * n j 二维变一维intindexi*nj;// 向下和向右已经包括了所有的覆盖情况 因为我们是从高到低 从左到右遍历的 联想八皇后!// 向下if(i1mgrid[i1][j]1){// 将这个index所在的数 与它下面一个数进行合并if(uf.union(index,(i1)*nj)){count--;}}// 向右if(j1ngrid[i][j1]1){if(uf.union(index,i*nj1)){count--;}}}}}returncount;}classUnionFind{// parent的index表示本身的值 value表示指向父集合 其实就是 index 最终属于 valueint[]parent;publicUnionFind(intn){parentnewint[n];for(inti0;in;i){parent[i]i;}}// 找到最终的父集合并且把路径全部指向最终的父集合publicintfind(intx){if(parent[x]!x){parent[x]find(parent[x]);}returnparent[x];}// 合并两个集合publicbooleanunion(intx,inty){introotXfind(x);introotYfind(y);if(rootXrootY){returnfalse;}parent[rootX]parent[rootY];returntrue;}}}反思我没有想到图的遍历需要用dfs和bfs进行搜索连通性问题、集合合并问题可以用并查集994.腐烂的橘子关键信息一句话总结多源 BFS扩散一层就是一分钟classSolution{publicintorangesRotting(int[][]grid){// 多源bfs 区别于岛屿对时间无要求 每个都bfs就好了intcount-1;intmgrid.length;intngrid[0].length;Queueint[]queuenewLinkedList();intfresh0;for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]2){queue.offer(newint[]{i,j});}if(grid[i][j]1){fresh;}}}if(fresh0){return0;}while(!queue.isEmpty()){intsizequeue.size();// 每一层算1分钟 刚开始不算 从0分钟开始count;for(inti0;isize;i){int[]curqueue.poll();intxcur[0];intycur[1];int[][]dirs{{1,0},{-1,0},{0,1},{0,-1}};for(int[]d:dirs){intnxxd[0];intnyyd[1];if(nx0nxmny0nyngrid[nx][ny]1){grid[nx][ny]2;fresh--;queue.offer(newint[]{nx,ny});}}}}if(fresh0){return-1;}returncount;}}反思我没有抓住它对时间的要求需要同时多源进行bfs而200题不需要多源进行只需要延申就行了207.课程表关键信息一句话总结用拓扑排序判断有向图中是否存在环classSolution{publicbooleancanFinish(intnumCourses,int[][]prerequisites){// 本质判断有向图是否存在环// 1.建图ListListIntegergraphnewArrayList();for(inti0;inumCourses;i){graph.add(newArrayList());}// 2.入度数组int[]indegreenewint[numCourses];// 3.构建邻接表和入度for(int[]p:prerequisites){intap[0];intbp[1];// b这个节点是a的前置graph.get(b).add(a);// a的前置(入度: 指向该节点的边的数量) 1indegree[a];}// 4.把所有入度为0的课程入队QueueIntegerqueuenewLinkedList();for(inti0;inumCourses;i){if(indegree[i]0){queue.offer(i);}}// 5.拓扑排序intcount0;while(!queue.isEmpty()){intcurqueue.poll();count;for(intnext:graph.get(cur)){indegree[next]--;if(indegree[next]0){queue.offer(next);}}}returncountnumCourses;}}反思我没有建模成功建模成判断图中是否存在环应该用拓扑排序208.实现Trie前缀树关键信息一句话总结把字符串拆成路径存进树里用共享前缀实现高效查找与前缀匹配分析isEnd用来标记是否是单词的结尾因为app和apple有共享前缀classTrie{classNode{Node[]childrennewNode[26];booleanisEnd;}privateNoderoot;publicTrie(){rootnewNode();}publicvoidinsert(Stringword){Nodenoderoot;for(charc:word.toCharArray()){intindexc-a;// 只要 new 过一次 这个 if 以后永远是 falseif(node.children[index]null){node.children[index]newNode();}nodenode.children[index];}node.isEndtrue;}publicbooleansearch(Stringword){Nodenodefind(word);if(node!nullnode.isEnd){returntrue;}returnfalse;}publicbooleanstartsWith(Stringprefix){if(find(prefix)!null){returntrue;}returnfalse;}privateNodefind(Strings){Nodenoderoot;for(charc:s.toCharArray()){intindexc-a;if(node.children[index]null){returnnull;}nodenode.children[index];}returnnode;}}/** * 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); */反思我没有想到共享前缀这个关键点我认为用一个数组或者链表就能完成然而要保证前缀所以有共享前缀不同分支所以就有了链表 哈希表