133. Clone Graph
題目網址：https://leetcode.cn/problems/clone-graph/
題意：給一無向連通圖的 node, 請返回該圖的 copy。
圖中每個 node 都包含它的 val (int) 和其 neighbors (list[node])
Solution 1：
想法：利用 DFS
class Solution {public: Node* cloneGraph(Node* node) { if (!node) { return node; } return dfs(node); }private: unordered_map<Node*, Node*> visited; // {old : new}, 用來記錄已生成的 node Node* dfs(Node* node){ // 若 node 已經生成過, 則返回其 copy if (visit ...
695. Max Area of Island
題目網址：https://leetcode.cn/problems/max-area-of-island/
題意：給一 m x n 的矩陣 grid。
島嶼是由一些相鄰的 1 （代表土地）所構成的組合, 這里的「相鄰」要求兩個 1 必須在水平 or 垂直的四個方向上相鄰。
假設 grid 的邊界都被 0（代表水）包圍著。
返回 grid 中最大的島嶼面積。如果沒有島嶼, 則返回 0。
Solution：
想法：利用 DFS, 以每一個 grid[i][j] 作為起點做 DFS 計算 area, 一旦拜訪過, 就將 grid[i][j] 設為 0, 避免遞迴遍歷時 area 重複計算
若 grid[i][j] == 1 : area++, 並遞迴遍歷四個方向
若 grid[i][j] == 0 : 直接返回
class Solution {public: int maxAreaOfIsland(vector<vector<int>>& grid) { m = grid.size(), n = grid[0 ...
417. Pacific Atlantic Water Flow
題目網址：https://leetcode.cn/problems/pacific-atlantic-water-flow/
題意：今有一 m x n 矩形島嶼, 與太平洋和大西洋相鄰。
太平洋位於島嶼的左邊界和上邊界
大西洋位於島嶼的右邊界和下邊界
給一 m x n 整數 array heights, 其中 heights[r][c] 代表座標 (r, c) 高於海平面的高度
相鄰 cell 的高度 小於或等於 目前 cell 的高度, 則雨水可以直接流向相鄰 cell
求哪些位置的雨水能同時流進太平洋和大西洋？
Solution 1：
想法：利用 DFS, 從邊界開始往內陸行進, 若高度越來越高則代表水可往邊界流, 藉此可找到抵達太平洋和大西洋的兩個集合, 然後取交集
最左和最上的邊界一定能抵達太平洋（由這兩邊界向內延伸）
最右和最下的邊界一定能抵達大西洋（由這兩邊界向內延伸）
typedef pair<int, int> pii;class Solution {public: vector<vector<int>& ...
130. Surrounded Regions
題目網址：https://leetcode.cn/problems/surrounded-regions/
題意：給一 m x n 的矩陣 board, 由若干個 char 'X' 和 'O', 找到所有被 'X' 圍繞的區域, 並用 'X' 來替代這些區域裡的 'O'。
Solution：
想法：利用 DFS, 題目希望我們找出被 X 包圍的區域, 但我們可以反向思考, 從邊界出發（因為邊界上的 O 一定不會被 X 包圍）, 往內陸延伸找出那些沒有被 X 包圍的區域, 概念同 417. Pacific Atlantic Water Flow。因此步驟如下：
找出沒有被 X 包圍的 O 區域, 並把這些區域設為 #（區分是否被 X 包圍）
遍歷 board, 將 O 設為 X（因為沒被設為 # 的區域就是被 X 包圍的 O 區域）
遍歷 board, 將 # 設為 O
class Solution {public: void solve(vector<vector<c ...
994. Rotting Oranges
題目網址：https://leetcode.cn/problems/rotting-oranges/
題意：給一 m x n 的網格 grid, 其中每個 cell 有三種可能：
0 代表沒橘子
1 代表新鮮橘子
2 代表腐爛的橘子
每分鐘, 腐爛的橘子周圍 4 個方向上相鄰的新鮮橘子都會腐爛。
返回 grid 中沒有新鮮橘子所必須經過的最短時間。如果不可能, 則返回 -1 。
Solution：
想法：利用 BFS, 因為 grid 一開始可能有多顆腐爛的橘子
typedef pair<int, int> pii;class Solution {public: int orangesRotting(vector<vector<int>>& grid) { m = grid.size(), n = grid[0].size(); int res = 0, fresh = 0; for (int i = 0; i < m; ++i) { ...