力扣hot图论部分
目录
题目链接
岛屿数量思路及其代码
代码如下
腐烂的橘子思路及其代码
注意事项
代码
课程表的思路及其代码
注意事项
代码
前缀树的思路及其代码
思路
代码
题目链接
200. 岛屿数量 - 力扣（LeetCode）
994. 腐烂的橘子 - 力扣（LeetCode）
207. 课程表 - 力扣（LeetCode）
208. 实现 Trie (前缀树) - 力扣（LeetCode）
其中简单分个类 岛屿数量是FloodFill（洪水灌溉算法）专题
腐烂的橘子是多源BFS专题
课程表是拓扑排序专题
前缀树是一种数据结构
岛屿数量思路及其代码
其实思路都是大同小异的。不过我提一提我的细节处理部分。
排除已经遍历过的岛屿的方法
引入向量数组去处理4个方向
代码如下
class Solution { int[] dx={0,0,1,-1}; int[] dy={1,-1,0,0}; int size=0; boolean[][] visit; public int numIslands(char[][] grid) { Queue<int[]> queue=new LinkedList<>(); int m=grid.length; int n=grid[0].length; visit=new boolean[m][n]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]=='1'&&visit[i][j]==false){ queue.offer(new int[]{i,j}); // grid[i][j]='0'; visit[i][j]=true; while(!queue.isEmpty()){ int[] t=queue.poll(); int a=t[0]; int b=t[1]; for(int h=0;h<4;h++){ int x=a+dx[h]; int y=b+dy[h]; // if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]=='1'){ if(x>=0&&x<m&&y>=0&&y<n&&visit[x][y]==false&&grid[x][y]=='1'){ queue.offer(new int[]{x,y}); //将已经遍历过的修改为0 // grid[x][y]='0'; visit[x][y]=true; } } } size++; } } } return size; } }腐烂的橘子思路及其代码
思路还是同岛屿数量，代码都长得差不多.
注意事项
怎么判断是否还有新鲜橘子呢
注意一个烂橘子同时腐烂周围的橘子算1次，如果有两个烂橘子分别同时腐烂周围的橘子也算一次
所以说引入queue.size()和is_Infected就很重要。
代码
class Solution { int fresh=0; boolean[][] visit; int[] dx={0,0,1,-1}; int[] dy={1,-1,0,0}; boolean isInfected=false; int minute=0; public int orangesRotting(int[][] grid) { int m=grid.length; int n=grid[0].length; visit=new boolean[m][n]; //先统计所有新鲜的橘子数 for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]==1){ fresh++; } // fresh++; } } if(fresh==0){ return 0; } Queue<int[]> queue=new LinkedList<>(); //先找到所有腐烂的橘子，然后加入queue种 for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]==2){ queue.offer(new int[]{i,j}); visit[i][j]=true; } } } while(!queue.isEmpty()){ //因为可能一次有多个腐烂橘子加入队列 同时是腐烂周围的橘子，本质上都是算一分钟 int size=queue.size(); for(int i=0;i<size;i++){ int[] t=queue.poll(); int a=t[0]; int b=t[1]; for(int h=0;h<4;h++){ int x=a+dx[h]; int y=b+dy[h]; if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1&&visit[x][y]==false){ queue.offer(new int[]{x,y}); visit[x][y]=true; fresh--; isInfected=true; } } } if(isInfected){ minute++; //记得还原 isInfected=false; } } return fresh>0?-1:minute; } }课程表的思路及其代码
首先解决这道题，你需要直到什么是拓扑排序。
本质就是判断图是否有环即可
注意事项
怎么去建图，我认为很关键
代码
class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { int m=prerequisites.length; // int n=prerequisites[0].length; //统计入度 int[] in=new int[numCourses]; //建图 Map<Integer,List<Integer>> map=new HashMap<>(); for(int i=0;i<m;i++){ int a=prerequisites[i][0]; int b=prerequisites[i][1]; //关系是b->a if(!map.containsKey(b)){ map.put(b,new ArrayList<>()); } map.get(b).add(a); in[a]++; } //进行拓扑排序 //进行BFS（找到所有入度为0的放入队列） Queue<Integer> queue=new LinkedList<>(); for(int i=0;i<numCourses;i++){ if(in[i]==0){ queue.offer(i); } } while(!queue.isEmpty()){ int t=queue.poll(); //删除与入度为0的点相连的边 for(int x:map.getOrDefault(t,new ArrayList<>())){ in[x]--; if(in[x]==0){ queue.offer(x); } } } for(int p:in){ if(p!=0){ return false; } } return true; } }前缀树的思路及其代码
这道题我第一次写的时候，有点浮躁，看题解没看懂。今天在一次写的时候，突然看懂了.
主要是看的灵神的题解
思路
insert的具体插入图（插入apple）
代码
class Trie { public static class Node{ Node[] son=new Node[26]; boolean end=false; } public Node root=new Node(); public void insert(String word) { Node cur=root; for(char c:word.toCharArray()){ int m=c-'a'; if(cur.son[m]==null){ cur.son[m]=new Node(); } cur=cur.son[m]; } cur.end=true; } public boolean search(String word) { return find(word)==2; } public boolean startsWith(String prefix) { return find(prefix)!=0; } public int find(String word){ Node cur=root; for(char c:word.toCharArray()){ int m=c-'a'; if(cur.son[m]==null){ return 0; } cur=cur.son[m]; } //返回2为完全匹配 返回1为前缀匹配 return cur.end?2:1; } } /** * 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); */