本系列為筆者的 Leetcode 刷題記錄，順序為 Hot 100 題官方順序，根據(jù)標簽命名，記錄筆者總結(jié)的做題思路，附部分代碼解釋和疑問解答，01~07為C++語言，08及以后為Java語言。

01 島嶼數(shù)量

class Solution {public int numIslands(char[][] grid) {}
}

方法一：深度優(yōu)先搜索

class Solution {//方法：深度優(yōu)先搜索//核心：grid[i][j] = '0'; i=row j=column//1.創(chuàng)建遞歸方法public void dfs(char[][] grid, int i, int j){int row = grid.length;int column = grid[0].length;if(i<0 || j<0 || i>=row || j>=column || grid[i][j] == '0'){return;}//?grid[i][j] = '0';//2.上下左右dfs(grid, i+1, j);dfs(grid, i-1, j);dfs(grid, i, j+1);dfs(grid, i, j-1);}public int numIslands(char[][] grid) {if(grid == null || grid.length == 0){return 0;}int row = grid.length;int column = grid[0].length;int ans = 0;for(int i=0; i<row; i++){for(int j=0; j<column; j++){if(grid[i][j] == '1'){ans++;dfs(grid, i, j);}}}return ans;}
}

那為什么正常我們不判斷 grid[0].length == 0 呢？

• grid == null：直接返回
• grid.length == 0：沒有任意行，不用繼續(xù)
• 至于 grid[0].length 是否為 0，在 Leetcode 官方測試用例中不會出現(xiàn)奇怪的“0列”矩陣(如 [[], [], []])。就算出現(xiàn)你訪問也在之后（第一個循環(huán)里 i < row 直接就不會進 j 的循環(huán)）

方法二：廣度優(yōu)先搜索

class Solution {//方法：廣度優(yōu)先搜索//核心：grid[i][j] = '0'public int numIslands(char[][] grid) {if(grid == null || grid.length == 0){return 0;}int row = grid.length;int column = grid[0].length;int ans = 0;for(int i=0; i<row; i++){for(int j=0; j<column; j++){if(grid[i][j] == '1'){ans++;grid[i][j] = '0';//1.創(chuàng)建并加入Deque<Integer> queue = new LinkedList<>();queue.offer(i * column + j);while(!queue.isEmpty()){//2.彈出并判斷int id = queue.poll();int r = id / column;int c = id % column;//3.上下左右孩子結(jié)點if(r-1 >= 0 && grid[r-1][c] == '1'){queue.offer((r-1) * column + c);grid[r-1][c] = '0';}if(r+1 < row && grid[r+1][c] == '1'){queue.offer((r+1) * column + c);grid[r+1][c] = '0';}if(c-1 >= 0 && grid[r][c-1] == '1'){queue.offer(r * column + (c-1));grid[r][c-1] = '0';}if(c+1 < column && grid[r][c+1] == '1'){queue.offer(r * column + (c+1));grid[r][c+1] = '0';}}}}}return ans;}
}

02 腐爛的橘子

class Solution {//方法：多源廣度優(yōu)先搜索int[] di = {-1, 0, 1, 0};int[] dj = {0, -1, 0, 1};public int orangesRotting(int[][] grid) {if(grid == null || grid.length == 0){return -1;}//1.創(chuàng)建并加入Deque<Integer> queue = new LinkedList<>();Map<Integer, Integer> map = new HashMap<>();int row = grid.length;int column = grid[0].length;int ans = 0;for(int i=0; i<row; i++){for(int j=0; j<column; j++){if(grid[i][j] == 2){int id = i * column + j; //二維展開一維queue.offer(id);map.put(id, 0);}}}//2.彈出并判斷while(!queue.isEmpty()){int id = queue.poll();int i = id / column;int j = id % column;//3.上下左右孩子結(jié)點for(int k=0; k<4; k++){int ni = i + di[k];int nj = j + dj[k];if(ni>=0 && ni<row && nj>=0 && nj<column && grid[ni][nj]==1){grid[ni][nj] = 2; //核心步驟int nid = ni * column + nj;queue.offer(nid);map.put(nid, map.get(id) + 1);ans = map.get(nid); //核心步驟}}}//4.檢查是否有正常橘子for(int[] ro : grid){for(int v : ro){if(v == 1){return -1;}}}return ans;}
}

① map建立的意義是什么，不能每次直接ans++嗎？

不能簡單用 ans++，因為擴散不是簡單的線性遞增，而是層級遞進，且同一層可能同時有多個節(jié)點擴散。

② ans = map.get(nid); 不用搞一個Math.max之類的嗎，萬一更新后比之前小呢？

bfs的特性是按層級遍歷，從起點到每個節(jié)點的路徑最短，不存在“后更新時間更小”的情況。

③ queue.remove()是從隊列的頭部出去還是尾部出去？

queue.poll() 或 queue.remove() 默認是從隊列頭部移除元素，即先進先出。

④ if(v == 1)為什么v直接是數(shù)字，而不是grid[][] = 1這樣的格式？

• for(int[] ro : grid)，ro 是二維數(shù)組中的每一行（一維數(shù)組）。
• for(int v : ro)，v 是當(dāng)前行中的每個元素，也就是 grid 中的單元格值。

03 課程表

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {}
}

方法一：深度優(yōu)先搜索

class Solution {//1.構(gòu)造鄰接表、訪問數(shù)組、環(huán)判斷符號；List<List<Integer>> edges;int[] visited;boolean valid = true;public boolean canFinish(int numCourses, int[][] prerequisites) {//2.初始化鄰接表、訪問數(shù)組edges = new ArrayList<List<Integer>>();for(int i=0; i<numCourses; i++){edges.add(new ArrayList<Integer>());}for(int[] info : prerequisites){edges.get(info[1]).add(info[0]);}visited = new int[numCourses];//3.遍歷結(jié)點并調(diào)用dfs方法for(int i=0; i<numCourses && valid; i++){if(visited[i] == 0){dfs(i);}}return valid;}public void dfs(int u){visited[u] = 1;for(int v : edges.get(u)){if(visited[v] == 0){dfs(v);if(!valid){return;}}else if(visited[v] == 1){valid = false;return;}}visited[u] = 2;}
}

方法二：廣度優(yōu)先搜索

class Solution {//1.構(gòu)造鄰接表、入度數(shù)組、訪問結(jié)點數(shù)量；List<List<Integer>> edges;int[] indeg;int visited = 0;public boolean canFinish(int numCourses, int[][] prerequisites) {//2.初始化鄰接表、入度數(shù)組edges = new ArrayList<>();for(int i=0; i<numCourses; i++){edges.add(new ArrayList<>());}indeg = new int[numCourses];for(int[] info : prerequisites){edges.get(info[1]).add(info[0]);indeg[info[0]]++; //入度增加}//3.廣度優(yōu)先搜索（queue）//a.創(chuàng)建并加入Deque<Integer> queue = new LinkedList<>();for(int i=0; i<numCourses; i++){if(indeg[i] == 0){queue.offer(i);visited++;}}//b.彈出并判斷while(!queue.isEmpty()){int u = queue.poll();//c.左右孩子結(jié)點for(int v : edges.get(u)){indeg[v]--; //入度減小if(indeg[v] == 0){queue.offer(v);visited++;}}}return visited == numCourses;       }
}

04 實現(xiàn) Trie（前綴樹）

class Trie {public Trie() {}public void insert(String word) {}public boolean search(String word) {}public boolean startsWith(String prefix) {}
}/*** 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);*/

class Trie {private Trie[] children;private boolean isEnd;public Trie() {children = new Trie[26];isEnd = false;}public void insert(String word) {Trie node = this;for(int i=0; i<word.length(); i++){char ch = word.charAt(i);int index = ch - 'a';if(node.children[index] == null){node.children[index] = new Trie();}node = node.children[index];}node.isEnd = true;}public boolean search(String word) {Trie node = searchPrefix(word);return node != null && node.isEnd == true;}public boolean startsWith(String prefix) {return searchPrefix(prefix) != null;}private Trie searchPrefix(String prefix) {Trie node = this;for(int i=0; i<prefix.length(); i++){char ch = prefix.charAt(i);int index = ch - 'a';if(node.children[index] == null){return null;}node = node.children[index];}return node;}
}

① 求什么的長度是.length而不是.length()？

.length返回數(shù)組的長度

.length()返回字符串的長度

② node.children[index]是啥玩意兒？

private Trie[] children;

這表示每個 Trie 節(jié)點里都有一個 children 數(shù)組，里面存放的是該節(jié)點的子節(jié)點，每個子節(jié)點也是一個 Trie 類型的對象。

• children 數(shù)組長度為 26，我們只處理小寫字母 a~z，每個位置對應(yīng)一個字母。
• children[0] 就是指向存儲字母 'a' 的那個子節(jié)點，
• children[1] 指向 'b' 的子節(jié)點，依此類推。

③ return node != null && node.isEnd; 當(dāng)中 node.isEnd 不太理解？

isEnd 是每個Trie節(jié)點里的一個布爾變量，表示這個節(jié)點是不是有單詞“在此結(jié)束”的標志。

舉例：

• 假設(shè)你插入了 "app" 和 "apple" 兩個單詞。
• 路徑a -> p -> p -> l -> e 在Trie里都存在，同時在 "app" 的最后字符的節(jié)點（第二個 p）和 "apple" 的最后字符節(jié)點（e）上，isEnd 都會標記為true。