前言
????????本文用于整理LeetCode Hot100中題目解答，因題目比較簡單且更多是為了面試快速寫出正確思路，只做簡單題意解讀和一句話題解方便記憶。但代碼會全部給出，方便大家整理代碼思路。
200. 島嶼數量
一句話題意
????????求所有上下左右的‘1’的連通塊數量。
一句話題解
????????DFS or BFS 搜一下就行了。
class Solution {int[][] fx = {{1,0},{0,1},{-1,0},{0,-1}};int n;int m;char[][] grid;void dfs(int x,int y){grid[x][y]='0';for(int i=0;i<4;i++){int xx=x+fx[i][0];int yy=y+fx[i][1];if(xx<0||xx>=n||yy<0||yy>=m||grid[xx][yy]=='0')continue;dfs(xx,yy);}}public int numIslands(char[][] grid) {this.grid=grid;int ans=0;n=grid.length;m=grid[0].length;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]=='1'){dfs(i,j);ans++;}}}return ans;}
}994. 腐爛的橘子
一句話題意
????????給定一個二維數組，二維數組上的每個2為一個爛掉的橘子，1為正常橘子，0為空位。每個壞橘子會每秒向周圍四個方向腐爛好的橘子，空位不能傳播，問最少多少時間全壞。
一句話題解
????????多源點廣搜，將所有壞的橘子放進去，沒搜到一個好的橘子就讓他變壞，然后接著搜即可。
class Solution {class Node {int x,y,t;Node(int x,int y,int t){this.x=x;this.y=y;this.t=t;}}public int orangesRotting(int[][] grid) {Queue<Node> q = new LinkedList<>();int ans=0;int sum=0;int n=grid.length;int m=grid[0].length;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==2)q.add(new Node(i,j,0));else if(grid[i][j]==1)sum++;}}int[][] fx={{1,0},{0,1},{-1,0},{0,-1}};while(q.size()>0){Node o = q.poll();ans=Math.max(ans,o.t);if(sum==0)continue;for(int i=0;i<4;i++){int xx=o.x+fx[i][0];int yy=o.y+fx[i][1];if(xx<0||xx>=n||yy<0||yy>=m||grid[xx][yy]!=1)continue;grid[xx][yy]=0;sum--;q.add(new Node(xx,yy,o.t+1));}}if(sum!=0)ans=-1;return ans;}
}207. 課程表
一句話題意
????????給定一些課程的前后學習關系，問是否能全部學習。
一句話題解
??????????拓撲排序。
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {List<List<Integer>> to = new ArrayList<>();int[] in = new int[numCourses];for (int i = 0; i < numCourses; i++)to.add(new ArrayList<>());for (int[] a : prerequisites) {to.get(a[1]).add(a[0]);in[a[0]]++;}Queue<Integer> q = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (in[i] == 0)q.add(i);}while (q.size() > 0) {int x = q.poll();numCourses--;for (Integer y : to.get(x)) {in[y]--;if (in[y] == 0)q.add(y);}}return numCourses == 0;}
}
208. 實現 Trie (前綴樹)
一句話題意
請你實現 Trie 類：
-
Trie()初始化前綴樹對象。 -
void insert(String word)向前綴樹中插入字符串word。 -
boolean search(String word)如果字符串word在前綴樹中，返回true（即，在檢索之前已經插入）；否則，返回false。 -
boolean startsWith(String prefix)如果之前已經插入的字符串word的前綴之一為prefix，返回true；否則，返回false。
一句話題解
????????實現一棵26岔樹。
class Trie {Trie[] children;boolean isEnd;public Trie() {children = new Trie[26];isEnd = false;}public void insert(String word) {Trie node = this;for(char c: word.toCharArray()){if(node.children[c-'a'] == null){node.children[c-'a'] = new Trie();}node = node.children[c-'a'];}node.isEnd = true;}public boolean search(String word) {Trie node = this.searchPrefix(word);return node!=null&&node.isEnd;}public boolean startsWith(String prefix) {return this.searchPrefix(prefix) != null;}public Trie searchPrefix(String s){Trie node = this;for(Character c:s.toCharArray()){if(node.children[c-'a']==null)return null;node=node.children[c-'a'];}return node;}
}
