LeetCode Hot100(图论)

200. 岛屿数量

题意

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

题解

简单来看，只要每一个与1上下左右相互连接的就是同一块陆地，那么我们遍历整张图，加入当前点的状态为1，就是有一块陆地了，那么把与他相连的全部赋值为0就可以了，也就是没有价值了

代码

import java.util.*;public class Solution {public static void main(String[] args) {char arr[][]={{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};}public int numIslands(char[][] grid) {int sum=0;for(int i=0;i<grid.length;i++){for(int j=0;j<grid[i].length;j++){if(grid[i][j]=='1'){sum++;dfs(grid,i,j);}}}return sum;}static int []zou1={0,0,0,1,-1};static int []zou2={0,-1,1,0,0};public static void dfs(char [][] arr,int x,int y){for(int i=1;i<=4;i++){int x1=zou1[i]+x;int y1=zou2[i]+y;if(x1<0||y1<0||x1>=arr.length||y1>=arr[0].length||arr[x1][y1]=='0'){continue;}arr[x1][y1]='0';dfs(arr,x1,y1);}}}

994. 腐烂的橘子

题意

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

题解

我们这题跟上一题实际上差不多，但是当前题需要求的是最小的分钟数，我们假设当前为3*3，表格为211 111 112 也就是表格边缘有两个的话，实际上对于当前而言，我们应当遍历当前的两个，将与他相连的都赋值为2，也就是被感染了，然后这就是1次，下一次就变成了221 212 122 ，这一次也是同理，遍历所有的2，将他相连的1感染即可

代码

import java.util.*;public class Solution {public static void main(String[] args) {char arr[][]={{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};}static int []zou1={0,0,0,1,-1};static int []zou2={0,1,-1,0,0};public int orangesRotting(int[][] grid) {Queue<node>dp =new ArrayDeque<>();int sum=0;int ans=0;for(int i=0;i<grid.length;i++){for(int j=0;j<grid[i].length ;j++){if(grid[i][j]==1){sum++;}else if(grid[i][j]==2){dp.add(new node(i,j));}}}if(sum!=0&&dp.isEmpty()){return -1;}if(sum==0){return 0;}while(dp.size()>=1&&sum!=0){ans++;int f=dp.size();while(f>=1){f--;node now=dp.peek();dp.poll();for(int i=1;i<=4;i++){int x= now.x+zou1[i];int y=now.y+zou2[i];if(x<0||y<0||x>=grid.length||y>=grid[x].length||grid[x][y]!=1){continue;}grid[x][y]=2;dp.add(new node(x,y));sum--;}}}if(sum==0){return ans;}else{return -1;}}public  static class node{int x,y;node(int a,int b){x=a;y=b;}}}

207. 课程表

题意

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

题解

简单来看，我们将课程视为一张图，也就是遍历图上面有没有环，这个就比较简单，每一次找一个节点进行dfs，看看会不会再一次遍历到当前节点即可

代码

import java.util.*;public class Solution {public static void main(String[] args) {int  arr[][]={{0,1}};}static List<List<Integer>> ways = new ArrayList<>(3000);static int[]mark =new int[3000];static boolean ans=true;public boolean canFinish(int numCourses, int[][] prerequisites) {ans=true;ways = new ArrayList<>(numCourses+10);mark = new int[numCourses+10];for (int i = 0; i < numCourses; i++) {mark[i]=0;ways.add(new ArrayList<>());}for(int i=0;i<prerequisites.length;i++){ways.get(prerequisites[i][0]).add(prerequisites[i][1]);}for(int i=0;i<numCourses;i++){if(!ans){return ans;}if(mark[i]==0){dfs(i);}}return ans;}static void dfs(int u){if (mark[u] == 1) {ans = false;return;}if (mark[u] == 2) { return;}mark[u] = 1; for (Integer now : ways.get(u)) {dfs(now);}mark[u] = 2; }}

208. 实现 Trie (前缀树)

题意

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

题解

简单写一个字典树的题解我们令a=1,b=2等等，画图可得

这实际上就是一ke字典树的抽象模型，令a为根部节点，该图中就会存在abc,abde,abdd，也就是说，在我们进行插入操作的时候，插入的点与点之间的路径关系，但是如果有abd，那么怎么跟abde区分呢，实际上我们把结尾的坐标设置一个结束的按钮即可

代码

class Trie {boolean check;Trie[]child;public Trie() {check=false;child =new Trie[28];}public void insert(String word) {Trie node=this;char []arr=word.toCharArray();for(int i=0;i<arr.length;i++){char f=arr[i];int x=f-'a'+1;if(node.child[x]==null){node.child[x]=new Trie();}node=node.child[x];}node.check=true;}public boolean search(String word) {Trie node=find(word);if(node==null){return false;}if(node.check==false){return false;}return true;}public boolean startsWith(String prefix) {Trie node=find(prefix);if(node==null){return false;}return true;}public Trie find(String word){Trie node=this;char[]arr=word.toCharArray();for(int i=0;i<arr.length;i++){int f=arr[i]-'a'+1;if(node.child[f]==null){return null;}node=node.child[f];}return node;}
}