?本文為力扣TOP100刷題筆記

筆者根據數據結構理論加上最近刷題整理了一套 數據結構理論加常用方法以下為該文章：

力扣外傳之數據結構（一篇文章搞定數據結構）

200. 島嶼數量

class Solution {// DFS輔助方法，用于標記和"淹沒"島嶼void dfs(char[][] grid, int r, int c) {int nr = grid.length;    // 網格行數int nc = grid[0].length; // 網格列數// 邊界檢查及是否陸地的檢查if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {return;}// 將當前陸地標記為已訪問（'0'表示水或已訪問）grid[r][c] = '0';// 向四個方向遞歸搜索dfs(grid, r - 1, c); // 上dfs(grid, r + 1, c); // 下dfs(grid, r, c - 1); // 左dfs(grid, r, c + 1); // 右}public int numIslands(char[][] grid) {// 處理空網格的情況if (grid == null || grid.length == 0) {return 0;}int nr = grid.length;    // 網格行數int nc = grid[0].length; // 網格列數int num_islands = 0;     // 島嶼計數器// 遍歷整個網格for (int r = 0; r < nr; ++r) {for (int c = 0; c < nc; ++c) {// 發現新島嶼if (grid[r][c] == '1') {++num_islands;    // 增加島嶼計數dfs(grid, r, c);  // "淹沒"整個島嶼}}}return num_islands;}
}

關鍵點解釋

1. DFS標記過程：

   • 將訪問到的'1'標記為'0'，避免重復計數

   • 向四個方向（上、下、左、右）遞歸搜索相連的陸地

2. 島嶼計數邏輯：

   • 每次遇到未被訪問的'1'，表示發現新島嶼

   • 調用DFS"淹沒"整個島嶼，確保不會重復計數

3. 邊界條件處理：

   • 檢查網格坐標是否越界

   • 處理空網格輸入的情況

示例演示

給定網格：

text

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

執行過程：

1. 發現(0,0)的'1'，計數+1，DFS淹沒左上角2×2島嶼

2. 跳過已訪問/水區域

3. 發現(2,2)的'1'，計數+1，DFS淹沒該孤立點

4. 發現(3,3)的'1'，計數+1，DFS淹沒右下角2×1島嶼

5. 最終島嶼數量：3

994. 腐爛的橘子

class Solution {public int orangesRotting(int[][] grid) {if (grid == null || grid.length == 0) return -1;int rows = grid.length;int cols = grid[0].length;int minutes = 0;while (true) {boolean changed = false;int[][] newGrid = new int[rows][cols];// 復制當前網格狀態for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {newGrid[i][j] = grid[i][j];}}// 遞歸處理每個橘子for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (grid[i][j] == 2) {changed |= infectAdjacent(grid, newGrid, i, j, rows, cols);}}}// 如果沒有變化，退出循環if (!changed) break;// 更新網格并增加分鐘數grid = newGrid;minutes++;}// 檢查是否還有新鮮橘子for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (grid[i][j] == 1) return -1;}}return minutes;}// 遞歸感染相鄰橘子的輔助方法private boolean infectAdjacent(int[][] grid, int[][] newGrid, int i, int j, int rows, int cols) {boolean changed = false;int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};for (int[] dir : directions) {int x = i + dir[0];int y = j + dir[1];if (x >= 0 && y >= 0 && x < rows && y < cols && grid[x][y] == 1) {newGrid[x][y] = 2;changed = true;}}return changed;}
}

遞歸思路解析

1. 外層循環：每分鐘處理一次腐爛過程

2. 網格復制：創建新網格來記錄下一分鐘的狀態

3. 遞歸處理：

   • 遍歷每個腐爛橘子(值為2)

   • 使用infectAdjacent方法遞歸感染相鄰的新鮮橘子

4. 終止條件：

   • 當沒有更多橘子可以被感染時退出循環

   • 最后檢查是否還有剩余的新鮮橘子

為什么這不是純遞歸

實際上，這個問題不太適合純遞歸解決，因為：

1. 多源點問題：多個腐爛橘子需要同時擴散

2. 時間步長：需要按分鐘同步處理所有腐爛

上面的解決方案使用了遞歸輔助方法，但整體結構仍然是迭代的（每分鐘處理一次）。

純遞歸的局限性

如果非要實現純遞歸版本，會遇到以下問題：

1. 難以同步時間：所有腐爛過程無法同步進行

2. 重復計算：同一個橘子可能被多次處理

3. 棧溢出風險：對于大網格會超出調用棧深度

207. 課程表

class Solution {// 鄰接表，存儲圖的邊關系，edges.get(i)表示課程i的所有后續課程List<List<Integer>> edges;// 記錄每個節點的訪問狀態：0=未訪問，1=訪問中，2=已訪問完成int[] visited;// 全局標志，表示當前是否沒有發現環（能否完成所有課程）boolean valid = true;public boolean canFinish(int numCourses, int[][] prerequisites) {// 初始化鄰接表edges = new ArrayList<List<Integer>>();for (int i = 0; i < numCourses; ++i) {edges.add(new ArrayList<Integer>());}// 初始化訪問狀態數組visited = new int[numCourses];// 構建圖的邊關系// prerequisites中的每個元素[1,0]表示要學習課程1必須先完成課程0// 所以在鄰接表中，我們添加邊 0→1for (int[] info : prerequisites) {edges.get(info[1]).add(info[0]);}// 對每個未訪問的節點執行DFSfor (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;}// 如果鄰接節點已訪問完成(2)，不需要處理}// 當前節點訪問完成，標記為"已訪問"visited[u] = 2;}
}

關鍵注釋說明

1. 鄰接表edges：

   • 使用ArrayList的ArrayList實現

   • edges.get(i)獲取課程i的所有直接后續課程列表

2. visited數組三種狀態：

   • 0：白色，未訪問節點

   • 1：灰色，正在訪問中的節點（在遞歸棧中）

   • 2：黑色，已完全訪問完成的節點

3. 環檢測邏輯：

   • 在DFS過程中，如果遇到灰色節點（狀態1），說明存在環

   • 因為灰色節點表示該節點在當前的遞歸調用棧中，再次遇到說明形成了環

4. DFS過程：

   • 先將節點標記為灰色（訪問中）

   • 遞歸訪問所有鄰接節點

   • 最后將節點標記為黑色（訪問完成）

5. 提前終止：

   • 一旦發現環（valid=false），立即終止后續的DFS過程

這個算法有效地利用DFS實現了有向無環圖(DAG)的檢測，解決了課程安排問題。

208. 實現 Trie (前綴樹)

class Trie {// 每個Trie節點包含：// 1. 一個長度為26的子節點數組（對應26個小寫字母）// 2. 一個布爾值標記是否是某個單詞的結尾private Trie[] children;private boolean isEnd;// 構造函數：初始化一個空的Trie節點public Trie() {children = new Trie[26];  // 26個字母的子節點isEnd = false;           // 初始時不是單詞結尾}// 向Trie中插入一個單詞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';  // 計算字母對應的索引(0-25)// 如果當前字符對應的子節點不存在，則創建新的子節點if (node.children[index] == null) {node.children[index] = new Trie();}// 移動到子節點node = node.children[index];}// 標記單詞的最后一個字符節點為結尾node.isEnd = true;}// 搜索Trie中是否存在完整的單詞public boolean search(String word) {Trie node = searchPrefix(word);// 不僅要找到前綴，最后一個節點還必須標記為單詞結尾return node != null && node.isEnd;}// 檢查Trie中是否有以給定前綴開頭的單詞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';  // 計算字母對應的索引(0-25)// 如果當前字符對應的子節點不存在，返回nullif (node.children[index] == null) {return null;}// 移動到子節點node = node.children[index];}// 返回前綴的最后一個字符節點return node;}
}

關鍵注釋說明

1. 數據結構設計：

   • children數組：每個元素對應一個字母（a-z），存儲指向子Trie節點的引用

   • isEnd標志：標記當前節點是否是某個單詞的結尾

2. 插入操作(insert)：

   • 從根節點開始，逐個字符處理

   • 對于每個字符，檢查對應的子節點是否存在，不存在則創建

   • 最后將單詞的最后一個字符節點標記為結尾

3. 搜索操作(search)：

   • 使用searchPrefix方法找到前綴的最后一個節點

   • 檢查該節點是否存在且被標記為單詞結尾

4. 前綴檢查(startsWith)：

   • 只需要檢查前綴路徑是否存在，不關心是否是完整單詞

5. 輔助方法(searchPrefix)：

   • 通用的前綴查找方法

   • 被search和startsWith方法復用

   • 返回前綴路徑的最后一個節點（如果存在）

時間復雜度分析

• 插入：O(L)，L為單詞長度

• 搜索：O(L)，L為單詞長度

• 前綴檢查：O(P)，P為前綴長度

空間復雜度

• 最壞情況：O(N×M)，N是單詞數量，M是平均單詞長度

• 實際中由于共享前綴，空間效率通常比哈希表更好

這個Trie實現特別適合處理字符串的前綴相關問題，如自動補全、拼寫檢查等場景。