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;}
}
