目錄
- 深搜
- 200. 島嶼數量
- 695. 島嶼的最大面積
- 130. 被圍繞的區域
- 547. 省份數量
- 417. 太平洋大西洋水流問題
- 回溯
- 廣搜
- 111. 二叉樹的最小深度
- 752. 打開轉盤鎖
- 深搜與廣搜結合
- 934. 最短的橋
深搜
深搜DFS，在搜索到一個新節點時，立即對該新節點進行遍歷，需要用到棧實現，或者使用與棧等價的遞歸實現。
深搜也可以用來檢測環路：記錄每個遍歷過的節點的父節點，若有一個節點被再次遍歷且父節點不同，則說明有環。
有時我們可能會需要對已經搜索過的節點進行標記，以防止在遍歷時重復搜索某個節點，這種做法叫做狀態記錄或者記憶化。
200. 島嶼數量
class Solution {
public:void dfs(vector<vector<char>>& grid,int m,int n,int i,int j){//如果越界或者為海域，退出if(i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') return;//標記為海域grid[i][j] = '0';dfs(grid,m,n,i-1,j);dfs(grid,m,n,i+1,j);dfs(grid,m,n,i,j-1);dfs(grid,m,n,i,j+1);return ;}int numIslands(vector<vector<char>>& grid) {int m = grid.size();int n = grid[0].size();int time = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == '1'){dfs(grid,m,n,i,j);time++;}}}return time;}
};
695. 島嶼的最大面積
一般來說，深搜可以分為主函數和輔助函數。
主函數用于遍歷所有的所有搜索位置，判斷是否可以開始搜索，如果可以即用輔助函數進行搜索。
輔助函數負責深搜的遞歸調用或者(棧)實現。
class Solution {
public:vector<int> direction {-1,0,1,0,-1};//輔助函數int dfs(vector<vector<int>>& grid, int r, int c){if(grid[r][c] == 0) return 0;//否則清除標志grid[r][c] = 0;//此時島嶼已經有1面積了，接下來進行對四個方向進行深搜int x,y,area = 1;for(int i = 0; i < 4; i++){//新起點x = r + direction[i];y = c + direction[i+1];//如果不越界，則繼續深搜if(x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size())area += dfs(grid,x,y);}//最后返回以r，c為起點的島嶼面積，并且在地圖上清除這個島嶼，防止多次搜索。return area;}//主函數int maxAreaOfIsland(vector<vector<int>>& grid) {if(grid.empty() || grid[0].empty()) return 0;int max_area = 0;for(int i = 0; i < grid.size(); i++){for(int j = 0; j < grid[0].size(); j++){if(grid[i][j] == 1){max_area = max(max_area,dfs(grid,i,j));}}}return max_area;}
};
輔助函數還可以寫成這樣，我更傾向于這種寫法：
//輔助函數
int dfs(vector<vector<int>>& grid, int r, int c)
{//如果該點越界或者為海域，退出遞歸if(r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() || grid[r][c] == 0) return 0;//否則說明該點為島嶼，面積+1,同時清除記錄grid[r][c] = 0;//返回以該點搜索起點的面積結果return 1 + dfs(grid,r-1,c) + dfs(grid,r,c+1) + dfs(grid,r+1,c) + dfs(grid,r,c-1);
}
130. 被圍繞的區域
class Solution {
public:void dfs(vector<vector<char>>& board,int m,int n,int i,int j){//遞歸退出條件if(i < 0 || i >= m || j < 0 || j >= n || board[i][j] == 'X' || board[i][j] == 'A') return;//否則進行標記，然后繼續深搜board[i][j] = 'A';dfs(board,m,n,i-1,j);dfs(board,m,n,i+1,j);dfs(board,m,n,i,j-1);dfs(board,m,n,i,j+1);return;}void solve(vector<vector<char>>& board) {int m = board.size();int n = board[0].size();//用dfs將邊界的相連的0全部置為Afor(int i = 0; i < m ; i++){dfs(board,m,n,i,0);dfs(board,m,n,i,n-1);}for(int j = 0; j < n ; j++){dfs(board,m,n,0,j);dfs(board,m,n,m-1,j);}//進行覆蓋操作，只有為A的不進行覆蓋for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j] == 'A') board[i][j] = 'O';else board[i][j] = 'X';}}return;}
};
547. 省份數量
分析：求無向圖中的連通域個數，輸入矩陣即為無向圖的鄰接矩陣
深搜思路：遍歷所有城市，對于每個城市，如果該城市沒有被訪問過，則從該城市開始深度優先搜索，通過矩陣得到與該城市直接相連的城市有哪些，這些城市與該城市屬于同一個連通分量，然后對這些城市繼續深搜，直到同一個連通分量的所有城市都被訪問到，就可以得到一個省份。
class Solution {
public:void dfs(vector<vector<int>>& isConnected,int i,vector<bool>& visited) {for(int j = 0; j < isConnected.size(); j++){//繼續遍歷與頂點相鄰的頂點，使用visited數組防止重復訪問if(isConnected[i][j] == 1 && visited[j] == false){//標記當前訪問過的頂點visited[j] = true;dfs(isConnected,j,visited);}}return;}int findCircleNum(vector<vector<int>>& isConnected) {int n = isConnected.size();int count = 0;//標識頂點是否被訪問vector<bool> visited(n,false);for(int i = 0; i < n; i++){//如果當前頂點沒有被訪問，說明是一個新的連通域，遍歷這個連通域且計數+1if(!visited[i]){dfs(isConnected,i,visited);count++;}}return count;}
};
417. 太平洋大西洋水流問題
1、邊界可以去往旁邊的一個海洋
也就是說邊界與海洋是連通的，所以需要從外往內擴散，獲得與邊界連通的區域（也就是高度相等或者高度比當前區域高的位置）
2、為了防止重復遍歷，添加visited數組
3、將連通的部分放到兩個子集中，一個是和太平洋連通的區域，一個是和大西洋連通的區域。然后對兩個求交集即可。
class Solution {
public:vector<int> direction{-1,0,1,0,-1};bool Isvaild(int x,int y,vector<vector<int>>& matrix){if(x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size()) return true;else return false;}//輔函數void dfs(vector<vector<int>>& matrix,vector<vector<bool>>& can_reach,int r,int c){//如果這個點遍歷過了，退出if(can_reach[r][c]) return;can_reach[r][c] = true;int x,y;//向四個方向擴散for(int i = 0; i < 4; i++){x = r + direction[i];y = c + direction[i+1];if(Isvaild(x,y,matrix) && matrix[r][c] <= matrix[x][y])dfs(matrix,can_reach,x,y);}}//主函數vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix){if(matrix.empty() || matrix[0].empty()) return {};vector<vector<int>> ans;int m = matrix.size();int n = matrix[0].size();//記錄能與p洋連通的區域vector<vector<bool>> can_reach_p(m,vector<bool>(n,false));//記錄能與a洋連通的區域vector<vector<bool>> can_reach_a(m,vector<bool>(n,false));//遍歷上下邊界for(int i = 0; i < m; i++){//擴散深搜dfs(matrix,can_reach_p,i,0);dfs(matrix,can_reach_a,i,n-1);}//遍歷左右邊界for(int j = 0; j < n; j++){//擴散深搜dfs(matrix,can_reach_p,0,j);dfs(matrix,can_reach_a,m-1,j);}//將所有遍歷結果進行取交集for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(can_reach_p[i][j] && can_reach_a[i][j])ans.push_back(vector<int>{i,j});}}return ans;}
};
回溯
回溯之前，已經做過一些題目了，都是一些經典題目，直接放在這兒。
算法題復習（回溯）
廣搜
模板如下：
//計算從起點start到終點target的最短距離
int BFS(Node start,Node target)
{queue<Node> q; //核心數據結構Set<Node> visited; //避免走回頭路q.push(start); //將起點加入隊列visited.insert(start);int steps = 0; //記錄擴散步數while(!q.empty()){//更新步數step++;int sz = q.size();//將當前隊列中的所有節點向四周擴散for(int i = 0; i < sz; i++){Node cur = q.front();q.pop();//判斷是否到達終點if(cur == target) return step;//將cur相鄰的節點加入隊列for(Node x: cur.adj()){//如果沒有遍歷過if(visited.find(x) == visited.end()){q.push(x);visited.insert(x);}}}}
}
cur.adj表示與cur相鄰的節點。visited主要是防止走回頭路，二叉樹結構沒有子節點到父節點的指針，所以不會走回頭路不需要visited。
不同于深度優先搜索，廣搜是一層一層遍歷的，因此需要用到先入先出的隊列，常常用來處理最短路徑問題。
深搜和廣搜都可以處理可達性問題，即從一個節點開始是否能到達另一個節點。因為深搜可以利用遞歸快速實現，所以很多人習慣使用深搜。但是實際工程中，很少使用遞歸，容易產生棧溢出。
111. 二叉樹的最小深度
start：root根節點
target：最靠近根節點的的葉子節點
if(cur.left == nullptr && cur.right == nullptr) //到達了葉子節點
class Solution {
public:int minDepth(TreeNode* root) {int result = 0;queue<TreeNode*> que;if(root == nullptr) return 0;que.push(root);while(!que.empty()){result++;int sz = que.size();for(int i = 0; i < sz; i++){TreeNode* cur = que.front();que.pop();//如果走到終點，返回結果if(cur->left == nullptr && cur->right == nullptr) return result;//否則繼續if(cur->left != nullptr) que.push(cur->left);if(cur->right != nullptr) que.push(cur->right);}}return result;}
};
752. 打開轉盤鎖
計算從初始狀態“0000”撥出目標狀態的最少次數，如果永遠無法撥出，則返回-1.
列表 deadends 包含了一組死亡數字，一旦撥輪的數字和列表里的任何一個元素相同，這個鎖將會被永久鎖定，無法再被旋轉。
從0000開始，按照廣度的思想，轉一次有8種可能：
1000、9000、0100、0900、…
可以抽象成一幅圖，每個節點有8個相鄰的節點，求最短距離，此時可以用上BFS。
使用下面的初步代碼，是按照BFS來尋找的最小密碼組合，不過顯然是有問題的。
class Solution {
public:string plusOne(string s,int j){string result = s;if(result[j] == '9') result[j] = '0';else result[j] = result[j] + 1;return result;}string minusOne(string& s,int j){string result = s;if(result[j] == '0') result[j] = '9';else result[j] = result[j] - 1;return result;}int openLock(vector<string>& deadends, string target) {queue<string> q;string start = "0000";q.push(start);int time = 0;while(!q.empty()){time++;int sz = q.size();for(int i = 0; i < sz; i++){string cur = q.front();q.pop();//判斷是否到達終點if(cur == target) return time;//將一個節點相鄰的節點加入隊列for(int j = 0; j < 4; j++){string up = plusOne(cur,j);q.push(up);string down = minusOne(cur,j);q.push(down);}}}return time;}
};
存在的問題如下：
1、會走回頭路，比如"0000"撥到"1000"，但是等從隊列中拿出"1000"，還會撥出"0000"
2、沒有對deadends進行處理，按道理來說，這些死亡密碼不能出現，遇到這些密碼的時候需要跳過。
修改后的代碼如下：
class Solution {
public:string plusOne(string s,int j){string result = s;if(result[j] == '9') result[j] = '0';else result[j] = result[j] + 1;return result;}string minusOne(string& s,int j){string result = s;if(result[j] == '0') result[j] = '9';else result[j] = result[j] - 1;return result;}int openLock(vector<string>& deadends, string target) {//記錄需要跳過的死亡密碼set<string> deads;for(string s : deadends) deads.insert(s);//記錄已經窮舉過的密碼，防止走回頭陸set<string> visited;queue<string> q;string start = "0000";q.push(start);visited.insert(start);int time = 0;while(!q.empty()){int sz = q.size();for(int i = 0; i < sz; i++){string cur = q.front();q.pop();//判斷是否合法if(deads.find(cur) != deads.end()) continue; //判斷是否到達終點if(cur == target) return time;//將一個節點相鄰的節點加入隊列，如果是存在過的就不需要加入隊列了for(int j = 0; j < 4; j++){string up = plusOne(cur,j);if(visited.find(up) == visited.end()){q.push(up);visited.insert(up);}string down = minusOne(cur,j);if(visited.find(down) == visited.end()){q.push(down);visited.insert(down);}}}time++;}return -1;}
};
深搜與廣搜結合
934. 最短的橋
class Solution {
public:vector<int> direction{-1,0,1,0,-1};void dfs(vector<vector<int>>& A,queue<pair<int,int>>& points,int m,int n,int i,int j){//如果越界了或者遍歷過了，不繼續向深處遍歷if(i < 0 || j < 0 || i >= m || j >= n || A[i][j] == 2) return;//如果是海域,插入隊列中if(A[i][j] == 0){points.push({i,j});return ;}A[i][j] = 2;//繼續深度遍歷dfs(A,points,m,n,i-1,j);dfs(A,points,m,n,i+1,j);dfs(A,points,m,n,i,j-1);dfs(A,points,m,n,i,j+1);return;} int shortestBridge(vector<vector<int>>& A) {int m = A.size();int n = A[0].size();//深度遍歷，尋找第一個島嶼int flag = 0;queue<pair<int,int>> points;for(int i = 0; i < m; i++){if(flag == 1) break;for(int j = 0; j < n; j++){//深度遍歷完一個島嶼后，立即退出if(A[i][j] == 1){flag = 1;dfs(A,points,m,n,i,j);break;}}}//開始廣度遍歷int level = 0;while(!points.empty()){int N = points.size();level++;while(N--){auto [r,c] = points.front();points.pop();//向四周廣度遍歷for(int k = 0; k < 4; k++){int x = r + direction[k];int y = c + direction[k+1];if(x >= 0 && x < m && y >= 0 && y < n){//如果還是第1個島嶼if(A[x][y] == 2) continue;if(A[x][y] == 1) return level;//如果還是0，則是繼續入隊列points.push({x,y});//將該坐標并入第1個島嶼A[x][y] = 2;}}}}return level;}
};
知識總結以及源碼分析》)
