devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode刷题笔记（5）：搜索_prodegree 刷题

作者：知新_RL | 2024-07-08 16:52:29

赞

踩

prodegree 刷题

广度优先搜索（BFS）一般由队列实现，其模板为：

  1. void BFS(int s){
  2.   queue<int> q;
  3.   q.push(s);
  4.   while(!q.empty()){
  5.     取队首元素top;
  6.     访问队首元素top;
  7.     队首元素出队pop;
  8.     for(下一层未入队结点){
  9.       入队，并设置为已入队
  10.     }
  11.   }
  12. }

深度优先搜索（DFS）可以用递归（调用系统栈实现）或栈实现。

栈模板

  1. void DFS(int s){
  2.   stack<int> st;
  3.   st.push(s);
  4.   while(!st.empty()){
  5.     取栈顶元素top;
  6.     访问队顶元素top;
  7.     栈顶元素出栈pop;
  8.     for(下一层未入栈结点){
  9.       入队，并设置为已入栈
  10.     }
  11.   }
  12. }

递归模板

  1. void DFS(){
  2.   if(抵达边界条件) return;
  3.   修改某些边界条件或标志量;
  4.   //岔道口，剪枝减少计算量
  5.   if(满足某条件){//递归进入分支
  6.     DFS();
  7.   }
  8. }

1、岛屿的最大面积（695）

搜索问题经典模板题，先介绍BFS思路：遍历二维数组每一个位置，如果是0跳过，如果为1，则判断其相邻4个位置是否为1（前提不能出界）。为防止重复访问，增加辅助数组标记，如果入过队则标记已访问。（当然本题可以直接把访问过的结点置为0更简单）直到所有数组被访问。

  1. class Solution {
  2. public:
  3.     //辅助方向数组，用于移动访问上下左右4个方向
  4.     vector<int> directions{-1,0,1,0,-1};
  5.     
  6.     int BFS(vector<vector<int>>& grid,int x,int y){
  7.       if(grid[x][y]==0) return 0;
  8.       queue<pair<int,int>> q;      
  9.       q.push({x,y});
  10.       grid[x][y] = 0;//置为0表示已访问过
  11.       int area = 0;
  12.       while(!q.empty()){
  13.         pair<int,int> top = q.front();
  14.         q.pop();
  15.         ++area;
  16.         for(int i=0;i<4;i++){
  17.           int newX = top.first + directions[i];
  18.           int newY = top.second + directions[i+1];
  19.           if(newX>=0 && newX<grid.size() && newY>=0 && newY<grid[newX].size() && grid[newX][newY]==1){
  20.             grid[newX][newY] = 0;
  21.             
  22.             q.push({newX,newY});
  23.           }
  24.         }
  25.       }
  26.       return area;
  27.     }
  28.     
  29.     int maxAreaOfIsland(vector<vector<int>>& grid) {
  30.       int maxArea = 0;
  31.       for(int i=0; i<grid.size();i++){
  32.         for(int j=0; j<grid[i].size(); j++){
  33.           maxArea = max(maxArea,BFS(grid,i,j));
  34.         }
  35.       }
  36.       return maxArea;
  37.  
  38.     }
  39. };

pair和队列混合使用不太习惯，其实可以用两个queue分别存储x和y坐标。

DFS思路，可以用栈也可以用递归方式，递归更易于实现，但一般为了防止出现递归栈满的情况，用栈比较合适。

  1. class Solution {
  2. public:
  3.           
  4.     int maxAreaOfIsland(vector<vector<int>>& grid) {
  5.       vector<int> directions{-1,0,1,0,-1};
  6.       int maxArea = 0, m = grid.size(), n = grid[0].size();
  7.       stack<pair<int,int>> st;
  8.       for(int x=0; x<m; x++){
  9.         for(int y=0; y<n; y++){
  10.           int area = 0;
  11.           if(grid[x][y]==1){           
  12.             grid[x][y] = 0;
  13.             st.push({x,y});
  14.             while(!st.empty()){
  15.               auto [r,c] = st.top();
  16.               st.pop();              
  17.               ++area;
  18.               for(int i=0;i<4;i++){
  19.                 int newx = r + directions[i];
  20.                 int newy = c + directions[i+1];
  21.                 if(newx>=0 && newx<m && newy>=0 && newy<n && grid[newx][newy]==1 ){
  22.                   st.push({newx,newy});
  23.                   grid[newx][newy] = 0;
  24.                 }
  25.               }
  26.             }
  27.           }
  28.           maxArea = max(maxArea,area);
  29.         }
  30.       }
  31.       return maxArea;
  32.     }
  33. };

语法：stack或queue中加入pair元素，使用.push({x,y})，读取auto[x,y] = .top()

递归方式

  1. class Solution {
  2. public:
  3.     vector<int> directions{-1,0,1,0,-1};
  4.     int DFS(vector<vector<int>>& grid,int r,int c){
  5.       //边界条件
  6.       if(grid[r][c]==0) return 0;
  7.       grid[r][c] = 0;
  8.       int area = 1;
  9.       for(int i=0; i<4; i++){
  10.         int x = r + directions[i], y = c + directions[i+1];
  11.         if(x>=0 && x<grid.size() && y>=0 && y<grid[0].size()){
  12.           area += DFS(grid,x,y);
  13.         }
  14.       }
  15.       return area;
  16.     }          
  17.     int maxAreaOfIsland(vector<vector<int>>& grid) {
  18.       if(grid.empty() || grid[0].empty()) return 0;
  19.       int maxArea = 0;
  20.       for(int i=0;i<grid.size();i++){
  21.         for(int j=0;j<grid[0].size();j++){
  22.           maxArea = max(maxArea,DFS(grid,i,j));
  23.         }
  24.       }
  25.       return maxArea;
  26.     }
  27. };

2、省份数量（547）

本质上是求连通子图个数。
思路一：DFS\BFS。以DFS为例，对城市 i ，考察还未访问的城市 j 与之是否同省（对应值为1），若同省，则递归对j进行上述过程，并标记 j 被访问。本质上就是一次调用DFS函数把某一个省的城市都找出来并标记，则调用DFS次数就是省份数量。

递归写法

  1. class Solution {
  2. public:
  3.   
  4.     void DFS(vector<vector<int>>& isConnected,int i,vector<bool>& isFind){
  5.       isFind[i] = true;
  6.       for(int j = 0; j<isConnected.size(); j++){
  7.         if(isConnected[i][j]==1 && !isFind[j]){
  8.           DFS(isConnected,j,isFind);
  9.         }
  10.       }
  11.     }
  12.     int findCircleNum(vector<vector<int>>& isConnected) {
  13.       int n = isConnected.size(),numProvices = 0;
  14.       //vector初始化方法为同一值
  15.       vector<bool> isFind(n,false);
  16.       for(int i=0; i<n; i++){
  17.         if(!isFind[i]){
  18.           DFS(isConnected,i,isFind);
  19.           ++numProvices;         
  20.         }
  21.       }
  22.       return numProvices;
  23.     }
  24. };

栈实现方法 

  1. class Solution {
  2. public:
  3.     int findCircleNum(vector<vector<int>>& isConnected) {
  4.       int n = isConnected.size(),numProvices = 0;
  5.       //vector初始化方法为同一值
  6.       vector<bool> visited(n,false);
  7.       for(int i=0; i<n; i++){        
  8.         if(!visited[i]){
  9.           stack<int> st;
  10.           st.push(i);
  11.           visited[i] =true;
  12.           while(!st.empty()){
  13.             int first = st.top();
  14.             st.pop();
  15.             for(int j=0; j<n; j++){
  16.               if(isConnected[first][j]==1 && !visited[j]){
  17.                 st.push(j);
  18.                 visited[j] = true;
  19.               }
  20.             }
  21.           }
  22.           ++numProvices;
  23.         }
  24.         
  25.       }
  26.       return numProvices;
  27.     }
  28. };

方法二：使用并查集

并查集的核心思想是：用数组father[ i ]存储数组 i 的父节点，从而实现合并（集合的合并）和查找（判断两个元素是否在一个集合）的操作。我们可以进行路径压缩，使同一个集合元素共有一个父节点。

集合数量统计可以开辟一个bool数组，记录是否为根节点。当然由于进行了路径压缩，也可以直接看father[i] == i的数量。

  1. class Solution {
  2. public:
  3.     //查找x所在集合的根节点
  4.     int findFather(vector<int>& father,int x){
  5.       int a = x;
  6.       //找到父节点
  7.       while(x!=father[x]){
  8.         x = father[x];
  9.       }
  10.       //路径压缩
  11.       while(a!=father[a]){
  12.         int z = a;
  13.         a = father[a];
  14.         father[z] = x;
  15.       }
  16.       return x;
  17.     }
  18.  
  19.     
  20.     int findCircleNum(vector<vector<int>>& isConnected) {
  21.       int n = isConnected.size(),numProvices = 0;     
  22.       vector<int> father(n);// 存放父节点
  23.       vector<int> isRoot(n,false);//记录每个结点是否作为根节点，便于统计省份数目
  24.       // 父节点初始化
  25.       for(int i=0; i<n; i++){
  26.         father[i] = i;
  27.       }
  28.  
  29.       for(int i=0; i<n; i++){
  30.         for(int j=0; j<i; j++){//合并同省份城市所在集合
  31.           if(isConnected[i][j]==1){
  32.             int faI = findFather(father,i);
  33.             int faJ = findFather(father,j);
  34.             if(faI != faJ){
  35.               father[faI] = faJ;
  36.             }
  37.           }
  38.         }
  39.       }
  40.  
  41.       //i的跟结点为findFather[i]
  42.       for(int i=0;i<n;i++){
  43.         isRoot[findFather(father,i)] = true;
  44.       }
  45.  
  46.       for(int i=0;i<n;i++){
  47.         numProvices += isRoot[i];
  48.       }
  49.       
  50.       return numProvices;
  51.     }
  52. };

语法：初始化vector数组为同一数组,vector<int> isRoot(n,false);

3、太平洋大西洋水流问题（417）

如果对每个位置进行搜索判断，不剪枝情况下时间复杂度非常高，因此反向思考，从4个边界向中间高处流，可以被抵达的点就是答案，这样只需要考察4个边界。

  1. class Solution {
  2. public:
  3.     vector<int> directions{-1,0,1,0,-1};
  4.     //判断(r,c)向高处流能到达哪些点
  5.     void dfs(vector<vector<int>>& heights,vector<vector<bool>>& can_reach,int r,int c){
  6.       if(can_reach[r][c]) return;
  7.       can_reach[r][c] = true;
  8.       for(int i=0; i<4; i++){
  9.         int x = r + directions[i], y = c + directions[i+1];
  10.         if(x>=0 && x<heights.size() && y>=0 && y<heights[0].size() && heights[r][c]<=heights[x][y]){
  11.           dfs(heights,can_reach,x,y);
  12.           
  13.         }
  14.       }
  15.     }
  16.     vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
  17.       if(heights.size()==0 || heights[0].size()==0) return {};
  18.       int m = heights.size(), n = heights[0].size();
  19.       //标记各点能否抵达太平洋或者大西洋
  20.       vector<vector<bool>> can_reach_p (m,vector<bool>(n,false));
  21.       vector<vector<bool>> can_reach_a (m,vector<bool>(n,false));
  22.       for(int i=0; i<m; i++){
  23.         //考察哪些点能抵达左右边界
  24.         dfs(heights,can_reach_p,i,0);
  25.         dfs(heights,can_reach_a,i,n-1);
  26.       }
  27.       for(int i=0; i<n; i++){
  28.         //考察哪些点能抵达上下边界
  29.         dfs(heights,can_reach_p,0,i);
  30.         dfs(heights,can_reach_a,m-1,i);
  31.       }
  32.  
  33.       vector<vector<int>> ans;
  34.       for(int i=0; i<m; i++){
  35.         for(int j=0; j<n; j++){
  36.           if(can_reach_p[i][j] && can_reach_a[i][j]){
  37.             ans.push_back(vector<int>{i,j});
  38.           }
  39.         }
  40.       }
  41.       return ans;
  42.     }
  43. };

语法：初始化二维vector，如vector<vector<bool>> can_reach_p (m,vector<bool>(n,false));

4、全排列（46）

全排列过程可以这样递归实现。递归过程：让n个元素轮流作为首位，对剩余n-1个元素进行全排列，我们可以用交换的方法，把每个元素交换到首位。递归边界：当只有1个元素，全排列即为本身。

对n-1个结点完成全排列后，我们需要恢复之前的状态，把后面的元素交换到首位，这就涉及到回溯法。回溯法比起DFS多了一个递归后修改回原结点状态的过程（使用引用传递状态）。

  1. class Solution {
  2. public:
  3.     void backtracking(vector<int>& nums,int level,vector<vector<int>>& ans){
  4.       //边界，交换到最后一个元素
  5.       if(level == nums.size()-1){
  6.         ans.push_back(nums);
  7.         return;
  8.       }
  9.       //level位元素和之后所有元素逐一交换，然后递归，之后回溯法修改回原状态
  10.       for(int i=level; i<nums.size(); i++){
  11.         swap(nums[i],nums[level]);
  12.         backtracking(nums,level+1,ans);
  13.         swap(nums[i],nums[level]);//回溯，修改回原状态
  14.       }
  15.     }
  16.     vector<vector<int>> permute(vector<int>& nums) {
  17.       vector<vector<int>> ans;
  18.       backtracking(nums,0,ans);
  19.       return ans;
  20.     }
  21. };

5、组合（77）

递归链条：从区间[st, n]中选出k个整数，如果选中st，则在[st+1, n]中选择k-1个整数；没选中st，则在[st+1, n]中选择k个整数。

递归边界：如果n-st+1<k，无法实现组合；如果k=0，已经找到k个数组合了。

回溯法运用：用nums数组存储已经选中的数字，用pop_back维持未选中的状态。

  1. class Solution {
  2. public:
  3.     //参数k表示还需选中的数字个数
  4.     void backtracking(int st, int n, int k,vector<int>& nums,vector<vector<int>>& ans){
  5.       if(n-st+1 < k) return;//剩余元素不足k个，无法实现组合
  6.       if(k == 0) {//已经本组组合找齐元素了
  7.         ans.push_back(nums);
  8.         return;
  9.       }
  10.       
  11.       //选中st
  12.       nums.push_back(st);
  13.       backtracking(st+1,n,k-1,nums,ans);
  14.       //没选中st
  15.       nums.pop_back();
  16.       backtracking(st+1,n,k,nums,ans);
  17.  
  18.     }
  19.     vector<vector<int>> combine(int n, int k) {
  20.       vector<int> nums;
  21.       vector<vector<int>> ans;
  22.       backtracking(1,n,k,nums,ans);
  23.       return ans;
  24.     }
  25. };

6、单词搜索（79）

递归过程：如果当前字符board[r][c]与目标单词的字母word[idx]相同，则对其上下左右（不出界）且没有被访问的结点，进行递归判断，看其是否是word[idx+1]。

递归边界：当idx == word.size()-1，且当前字符board[r][c]与目标单词的字母word[idx]相同，则找到了该单词。

回溯：如果子递归找不到该单词，重新设置board[r][c]为未访问。

  1. class Solution {
  2. public:
  3.     vector<int> directions{-1,0,1,0,-1};
  4.     void backtracking(vector<vector<char>>& board,string word,vector<vector<bool>>& visited,int r, int c, bool& flag,int idx){
  5.       
  6.       if(visited[r][c]==false && board[r][c] == word[idx]){
  7.         if(idx = word.length()-1){
  8.           flag = true;
  9.           return;
  10.         }
  11.         visited[r][c] = true;//(r,c)已被选用
  12.         for(int i=0;i<4;i++){
  13.           int x = r + directions[i], y = c + directions[i+1];
  14.           if(x>=0 && x<board.size() && y>=0 && y<board[0].size()){
  15.             backtracking(board,word,visited,x,y,flag,idx+1);
  16.           }
  17.         }
  18.         visited[r][c] = false;
  19.         
  20.       }
  21.     }
  22.     bool exist(vector<vector<char>>& board, string word) {
  23.       int m = board.size(), n = board[0].size();
  24.       bool flag = false;
  25.       vector<vector<bool>> visited(m,vector<bool>(n,false));
  26.       for(int i=0;i<m;i++){
  27.         for(int j=0;j<n;j++){
  28.           backtracking(board,word,visited,i,j,flag,0);
  29.           if(flag) return true;
  30.         }
  31.       }
  32.       return false;
  33.     }
  34. };

7、N 皇后（51）

经典N皇后问题，同样采用回溯法。
递归过程：N皇后排列结果必定是每行和每列仅有1个皇后，因此我们可以按行填入。当我们在第row行第 i 个位置放入一个皇后时，则第i个位置对应的竖行、左、右斜行都不可再填入（用对应数组标识），然后对第row+1行递归，寻找合适位置填入下一个皇后。
递归边界：当放置第N行时（编号0~N-1），已经找到一种摆法，保存结果。
回溯：递归后，把第row行第 i 个位置摆放的皇后，第i个位置对应竖行、左、右斜行修改回来。

N皇后的问题的难点主要在于选中一个位置放入皇后，要如何把其对应的行，列，左右斜行给修改，使之不能再填入别的皇后。特别是要注意到同一斜行与其行、列号的关系。

  1. class Solution {
  2. public: 
  3.     void backtracking(vector<vector<string>>& ans,vector<string>& board, vector<bool>& columns, vector<bool>& ldiag, vector<bool>& rdiag,int row,int n){
  4.       //已经摆放了n个皇后了
  5.       if(row == n){
  6.         ans.push_back(board);
  7.         return;
  8.       }
  9.       //在第row行寻找合适位置放入皇后
  10.       for(int i=0; i<n; i++){
  11.         //判断第i个位置对应的列、左、右斜行是否已有皇后
  12.         //以左上为原点，从左上到右下给左斜行编号[0~2n-1]，其左斜行号 = 行号 + 列号
  13.         //从右上到左下给右斜行编号[0~2n-1]，其右斜行号 = 行号 - 列号 + (n-1)
  14.         if(columns[i] || ldiag[row+i] || rdiag[row - i + n -1]){
  15.           continue;
  16.         }
  17.         //在找到的合适位置放入皇后，并修改对应列、左、右斜行
  18.         board[row][i] = 'Q';
  19.         columns[i] = ldiag[row+i] = rdiag[row - i + n -1] = true;
  20.         //对第row+1行递归
  21.         backtracking(ans,board,columns,ldiag,rdiag,row+1,n);
  22.         //回溯
  23.         board[row][i] = '.';
  24.         columns[i] = ldiag[row+i] = rdiag[row - i + n -1] = false;
  25.       }
  26.     }
  27.     vector<vector<string>> solveNQueens(int n) {
  28.       vector<vector<string>> ans;
  29.       if(n==0) return ans; 
  30.       //存储摆放结果
  31.       vector<string> board(n,string(n,'.')); 
  32.       //ldiag和rdiag为左右斜行，n*n方格有2n-1个左、右斜行    
  33.       vector<bool> columns(n,false), ldiag(2*n-1,false),rdiag(2*n-1,false);
  34.       backtracking(ans,board,columns,ldiag,rdiag,0,n);
  35.       return ans;
  36.     }
  37. };

8、最短的桥（934）

本题首先要认识到，从一个岛到另一岛的最短距离 = 从一个岛进行宽度优先搜索找到另一个岛扩展层数 -1。具体思路：

（1）先用深度优先搜索，把第一个岛的结点全部找出加入队列；

（2）bfs向外拓展，直到找到另一个岛，所有入队的结点把值改为2，标记为已访问。

  1. class Solution {
  2. public:
  3.     queue<pair<int,int>> q;
  4.     vector<int> directions{-1,0,1,0,-1};
  5.     void dfs(vector<vector<int>>& grid,int r,int c){
  6.       grid[r][c] = 2;
  7.       q.push({r,c});
  8.       for(int i=0; i<4; i++){
  9.         int x = r + directions[i], y = c + directions[i+1];
  10.         if(x>=0 && x<grid.size() && y>=0 && y<grid.size() && grid[x][y]==1){
  11.           dfs(grid,x,y);
  12.         }
  13.       }
  14.     }
  15.     int shortestBridge(vector<vector<int>>& grid) {           
  16.       int n = grid.size();
  17.       //先用dfs找出一个岛的所有结点入队，并把1改为2用于标识已访问
  18.       int flag = false;
  19.       for(int i=0; i<n; i++){
  20.         for(int j=0; j<n; j++){
  21.           if(grid[i][j]==1){
  22.             dfs(grid,i,j);
  23.             flag = true;
  24.             break;
  25.           }
  26.         }
  27.         if(flag) break;
  28.       }
  29.  
  30.       //用bfs向外搜索，到碰见1时向外搜索的层数-1即为桥数
  31.       int layer = 0;
  32.       while(!q.empty()){
  33.         ++layer;
  34.         //把本层全部取出
  35.         int num = q.size();
  36.         while(num--){
  37.           auto [r,c] = q.front();
  38.           q.pop();
  39.           for(int k=0; k<4; k++){
  40.             int x = r + directions[k], y = c + directions[k+1];
  41.             if(x>=0 && x<n && y>=0 && y<n){
  42.               if(grid[x][y]==1) return layer-1;//拓展到另一个岛
  43.               else if(grid[x][y]==2) continue;//已入队结点
  44.               else if(grid[x][y]==0) {//0结点入队，并修改为2标记已入过队
  45.                 grid[x][y] = 2;
  46.                 q.push({x,y});
  47.               }
  48.             }
  49.           }
  50.         }
  51.       }
  52.       return 0;
  53.     }
  54. };

9、被围绕的区域（130）

本题类似于前面的找岛问题，不同在于不考虑有边界点的岛。我的思路是：用数组存储岛的结点，再用一个标志变量flag存储该岛是否存在边界结点，如果不存在，则把数组中的结点修改为X。

  1. class Solution {
  2. public:
  3.     vector<int> direction{-1,0,1,0,-1};
  4.     void dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, vector<pair<int,int>>& pos, int r,int c,bool& flag){
  5.       visited[r][c] = true;
  6.       if(r==0 || r==board.size()-1 || c==0 || c==board[0].size()-1){//边界上的结点
  7.         flag = false;
  8.         
  9.       }
  10.       pos.push_back({r,c});
  11.       for(int i=0;i<4;i++){
  12.         int x = r + direction[i], y = c + direction[i+1];
  13.         if(x>=0 && x<board.size() && y>=0 && y<board[0].size() && board[x][y]=='O' && !visited[x][y]){
  14.           dfs(board,visited,pos,x,y,flag);
  15.         }
  16.       }
  17.     }
  18.  
  19.     void solve(vector<vector<char>>& board) {
  20.       
  21.       int m = board.size(), n = board[0].size();
  22.       vector<vector<bool>> visited(m,vector<bool>(n,false));
  23.       for(int i=0; i<m; i++){
  24.         for(int j=0; j<n; j++){
  25.           if(board[i][j]=='O' && !visited[i][j]){
  26.             bool flag = true;//判断岛是否有边界结点
  27.             vector<pair<int,int>> pos;//存储岛的结点
  28.             dfs(board,visited,pos,i,j,flag);
  29.             if(flag){
  30.               for(auto[x,y]: pos){
  31.               board[x][y] = 'X';
  32.               }
  33.             }
  34.             
  35.           }
  36.         }
  37.       }
  38.     }
  39. };

参考题解发现更优思路：可以先对边界点进行dfs，把包含边界点的岛修改为‘A’。之后对所有结点遍历，若结点为'A'，则改回‘O’，若结点为'O'则修改为'X'。

  1. class Solution {
  2. public:
  3.     int n, m;
  4.  
  5.     void dfs(vector<vector<char>>& board, int x, int y) {
  6.         if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') {
  7.             return;
  8.         }
  9.         board[x][y] = 'A';
  10.         dfs(board, x + 1, y);
  11.         dfs(board, x - 1, y);
  12.         dfs(board, x, y + 1);
  13.         dfs(board, x, y - 1);
  14.     }
  15.  
  16.     void solve(vector<vector<char>>& board) {
  17.         n = board.size();
  18.         if (n == 0) {
  19.             return;
  20.         }
  21.         m = board[0].size();
  22.         for (int i = 0; i < n; i++) {
  23.             dfs(board, i, 0);
  24.             dfs(board, i, m - 1);
  25.         }
  26.         for (int i = 1; i < m - 1; i++) {
  27.             dfs(board, 0, i);
  28.             dfs(board, n - 1, i);
  29.         }
  30.         for (int i = 0; i < n; i++) {
  31.             for (int j = 0; j < m; j++) {
  32.                 if (board[i][j] == 'A') {
  33.                     board[i][j] = 'O';
  34.                 } else if (board[i][j] == 'O') {
  35.                     board[i][j] = 'X';
  36.                 }
  37.             }
  38.         }
  39.     }
  40. };
  41.

10、二叉树的所有路径（257）

采用回溯法。

递归过程：一个结点左子树不为空时，把左子树值加入str，向左子树递归，递归完回溯，把插入值去掉，恢复str；右子树同理。

递归边界，一个结点左右子树都为空时，到达了叶子结点，把str加入ans，返回。

  1. class Solution {
  2. public:
  3.     void dfs(vector<string>& ans, string& str,TreeNode* root){
  4.       if(root->left == nullptr && root->right == nullptr){//抵达叶子结点
  5.         ans.push_back(str);
  6.         return;
  7.       }
  8.       if(root->left != nullptr){
  9.         int pos = str.size();
  10.         str += "->";   
  11.         str += to_string(root->left->val);//to_stirng函数把int转化为string
  12.         dfs(ans,str,root->left);
  13.         //回溯，把插入的左子树部分删除
  14.         str.erase(str.begin()+pos,str.end());
  15.       }
  16.       if(root->right != nullptr){
  17.         int pos = str.size();
  18.         str += "->";   
  19.         str += to_string(root->right->val);
  20.         dfs(ans,str,root->right);
  21.         str.erase(str.begin()+pos,str.end());
  22.       }
  23.  
  24.  
  25.     }
  26.     vector<string> binaryTreePaths(TreeNode* root) {
  27.       if(root == nullptr) return {};
  28.       //因为根节点前面没有->，所以把把根节点值先加入
  29.       string str = to_string(root->val);
  30.       vector<string> ans;
  31.       dfs(ans,str,root);
  32.       return ans;
  33.     }
  34. };

语法：to_string()把数值型数据（如int\double\long等）转化为string。

在仔细思考，其实这题中存储某条路径的str不需要引用传递，直接用形参就复制了一份副本，不需要删除回溯这个操作了。

  1. class Solution {
  2. public:
  3.     void construct_paths(TreeNode* root, string path, vector<string>& paths) {
  4.         if (root != nullptr) {
  5.             path += to_string(root->val);
  6.             if (root->left == nullptr && root->right == nullptr) {  // 当前节点是叶子节点
  7.                 paths.push_back(path);                              // 把路径加入到答案中
  8.             } else {
  9.                 path += "->";  // 当前节点不是叶子节点，继续递归遍历
  10.                 construct_paths(root->left, path, paths);
  11.                 construct_paths(root->right, path, paths);
  12.             }
  13.         }
  14.     }
  15.  
  16.     vector<string> binaryTreePaths(TreeNode* root) {
  17.         vector<string> paths;
  18.         construct_paths(root, "", paths);
  19.         return paths;
  20.     }
  21. };

11、全排列 II（47）

本题是全排列的变形题，区别在于本题存在重复的元素，在回溯法的过程中会产生重复结果。这些重复结果产生的原因是，重复元素背交换到pos位，因此可以建立一个集合，存储pos中出现过的元素，只有没出现在pos位上的元素才能执行后续操作和递归。

  1. class Solution {
  2. public:
  3.     void backtracking(vector<int>& nums,vector<vector<int>>& ans,int pos){
  4.       if(pos == nums.size()-1){
  5.         ans.push_back(nums);
  6.         return;
  7.       }
  8.       unordered_set<int> s;
  9.       for(int i=pos; i<nums.size(); i++){        
  10.         if(!s.count(nums[i])){
  11.           s.insert(nums[i]);
  12.           swap(nums[i],nums[pos]);
  13.           backtracking(nums,ans,pos+1);
  14.           swap(nums[i],nums[pos]);
  15.         }
  16.       }
  17.     }
  18.     vector<vector<int>> permuteUnique(vector<int>& nums) {
  19.       vector<vector<int>> ans;
  20.       backtracking(nums,ans,0);
  21.       return ans;
  22.     }
  23. };

12、组合总和（39）

组合数的变形题，要求从组合出k个数变成了组合数字的和为target。仍然可以用回溯法，设candidates共有n个数。

递归过程：若选中第k个数时，则对[k,n-1]继续递归，使[k,n-1]中选中的数字和等于sum - candidates[k]；若不选中第k个数时，回溯，去掉选中candidates[k]，的则对[k+1,n-1]继续递归，使[k+1,n-1]中选中的数字和等于sum 。

递归边界：若当前sum=0，则保存答案返回；若sum<0或是k==n，则直接返回。

  1. class Solution {
  2. public:
  3.     void backtracking(vector<vector<int>>& ans,vector<int>& candidates,vector<int>& nums,int sum,int k){
  4.       if(sum == 0){//这一边界条件要放在上面，不然可能会在sum=0,而candidates.size()时直接返回
  5.         ans.push_back(nums);
  6.         return;
  7.       }
  8.       if(sum<0 || k==candidates.size()){
  9.         return;
  10.       }            
  11.       //选中candidates[k]
  12.       nums.push_back(candidates[k]);
  13.       backtracking(ans,candidates,nums,sum - candidates[k],k);
  14.       //未选中candidates[k]
  15.       nums.pop_back();      
  16.       backtracking(ans,candidates,nums,sum,k+1);
  17.     }
  18.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
  19.       vector<vector<int>> ans;
  20.       vector<int> nums;
  21.       backtracking(ans,candidates,nums,target,0);
  22.       return ans;
  23.     }
  24. };

13、组合总和 II（40）

变式题，这一题里元素本身就包含重复元素，每个元素只能用一次。难点在于如何产生不重复的结果。如下例：

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

candiates中有两个1，但是只能产生一个[1,7]的结果，因此需要改进递归条件。为了不让重复的元素执行相同的递归过程，得到相同的递归结果，对相同元素，只取一个进行递归即可。为此，我们先把candiates进行排序，相同元素会连续排列，选中第一个进行递归，不选中时跳到下一个不同元素进行递归。

  1. class Solution {
  2. public:
  3.     void backtracking(vector<vector<int>>& ans,vector<int>& candidates,vector<int>& nums,int sum,int k){
  4.       if(sum == 0){//这一边界条件要放在上面，不然可能会在sum=0,而candidates.size()时直接返回
  5.         ans.push_back(nums);
  6.         return;
  7.       }
  8.       if(sum<0 || k==candidates.size()){
  9.         return;
  10.       }            
  11.       //选中candidates[k]
  12.       nums.push_back(candidates[k]);
  13.       backtracking(ans,candidates,nums,sum - candidates[k],k+1);
  14.       //未选中candidates[k]，为了不产生重复结果，跳到下一个不同的元素递归
  15.       nums.pop_back();
  16.       int i=k+1;
  17.       for(i=k+1;i<candidates.size();i++){
  18.         if(candidates[i]!=candidates[k]) break;
  19.       }
  20.       backtracking(ans,candidates,nums,sum,i);
  21.     }
  22.     vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
  23.         sort(candidates.begin(),candidates.end());
  24.         vector<vector<int>> ans;
  25.         vector<int> nums;
  26.         backtracking(ans,candidates,nums,target,0);
  27.         return ans;
  28.     }
  29. };

14、解数独（37）

这题看成是N皇后问题的扩展题，都是不同方格间填入元素的存在制约关系，需要利用这一关系剪枝，搜索出最终结果。N皇后是行、列、斜行间的制约关系，数独是行、列、九宫格内的制约关系。所以思路也类似。维系row, col, block的辅助数组，记录(r, c)点所在行、列、块内已经使用过的数字。

递归思路：如果(r, c)点是'.’，则根据对应row, col, block，选出所有可能值填入，并修改row, col, block辅助状态，之后移动到下一个点递归，然后回溯，把填入值、辅助数组值改回来，；如果(r, c)点已经有数字，直接递归下一个点。

递归边界：按行优先移动点，当递归到(9,0)点时，说明已经得到答案，保存结果后返回。

  1. class Solution {
  2. public:
  3.     //记录每一行、列、九宫格已经使用的数字
  4.     bool row[9][10] = {false}, col[9][10] = {false}, block[3][3][10] = {false};
  5.     char ans[9][9];//记录最终答案
  6.     void backtracking(vector<vector<char>>& board,int r,int c){
  7.       if(r==9 && c==0){
  8.         for(int i=0;i<9;i++){
  9.           for(int j=0;j<9;j++){
  10.             ans[i][j] = board[i][j];
  11.           }
  12.         }
  13.         return;
  14.       }
  15.       int x,y;//下一个递归点
  16.       if(c==8) {
  17.             x = r+1;
  18.             y = 0;
  19.       }else{
  20.             x = r;
  21.             y = c+1;
  22.       }
  23.       if(board[r][c]=='.'){
  24.         //寻找1-9间的合适值填入
  25.         for(int i=1;i<10;i++){
  26.           if(row[r][i] || col[c][i] || block[r/3][c/3][i]){
  27.             //(r,c)所在行、列或九宫格已经有数字i
  28.             continue;
  29.           }
  30.           row[r][i] = col[c][i] = block[r/3][c/3][i] = true;
  31.           board[r][c] = '0' + i;
  32.           
  33.           backtracking(board,x,y);
  34.           //回溯
  35.           row[r][i] = col[c][i] = block[r/3][c/3][i] = false;
  36.           board[r][c] = '.';
  37.         }
  38.       }else{
  39.         backtracking(board,x,y);
  40.       }
  41.  
  42.     }
  43.     
  44.     void solveSudoku(vector<vector<char>>& board) {
  45.       //更新记录表
  46.       for(int i=0;i<9;i++){
  47.         for(int j=0;j<9;j++){          
  48.           if(board[i][j]!='.'){
  49.             int num = board[i][j] - '0';
  50.             row[i][num] = true;
  51.             col[j][num] = true;
  52.             block[i/3][j/3][num] = true;
  53.           }
  54.         }
  55.       }
  56.  
  57.       backtracking(board,0,0);
  58.       for(int i=0;i<9;i++){
  59.           for(int j=0;j<9;j++){
  60.             board[i][j] = ans[i][j];
  61.           }
  62.         }
  63.       
  64.     }
  65. };

15、最小高度树（310）

本题最直接的思路是，把边读入，按邻接表存储图。以每个结点为根结点，进行dfs或bfs，求出当前树的高度，并更新最小树高，保存结果。但这样的方法时间复杂度较高，在结点很多时会超过时间界限。

  1. class Solution {
  2. public:
  3.     
  4.     vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
  5.       vector<vector<int>> G(n);
  6.       for(int i=0;i<n-1;i++){
  7.         int a = edges[i][0], b = edges[i][1];
  8.         G[a].push_back(b);
  9.         G[b].push_back(a);
  10.       }
  11.       
  12.       vector<int> ans;
  13.       int min_depth = n;
  14.       for(int i=0; i<n; i++){
  15.         int depth = -1;
  16.         vector<bool> visited(n,false);
  17.         queue<int> q;
  18.         q.push(i);
  19.         visited[i] = true;
  20.         while(!q.empty()){
  21.           int size = q.size();
  22.           ++depth;
  23.           for(int j=0; j<size;j++){
  24.             int root = q.front();
  25.             q.pop();
  26.             for(int k=0; k<G[root].size(); k++){
  27.               int node = G[root][k];
  28.               if(!visited[node]){
  29.                 q.push(node);
  30.                 visited[node] = true;
  31.               }
  32.             }
  33.           }
  34.         }
  35.  
  36.         if(min_depth>depth){
  37.           min_depth = depth;
  38.           ans.clear();
  39.           ans.push_back(i);
  40.         }else if(min_depth == depth){
  41.           ans.push_back(i);
  42.         }
  43.       }
  44.       return ans;
  45.     }
  46. };

参考大佬解答，注意发现以图中心的结点作为根，树高会更小，而用边缘结点（如叶子）树高会较大。如下图示例：0、2、3都是边缘叶子结点，所以树高都较大，而中心的1作为根，则树高较小。

 既然度为1的边缘结点会是不可能作为最小树高结点，那么我们可以逐步剥去剩余图中度为1的边缘结点，在剥完所有结点时，最后被剥去的那层结点就是答案。

  1. class Solution {
  2. public:
  3.     
  4.     vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
  5.       if(n==1) return {0};
  6.       vector<vector<int>> G(n);
  7.       for(int i=0;i<n-1;i++){//邻接表存储图
  8.         int a = edges[i][0], b = edges[i][1];
  9.         G[a].push_back(b);
  10.         G[b].push_back(a);
  11.       }
  12.       
  13.       vector<int> ans,degree(n);      
  14.       queue<int> q;
  15.       //统计结点的度，并把度为1的结点存进队列
  16.       for(int i=0;i<n;i++){
  17.         degree[i] = G[i].size();
  18.         if(G[i].size()==1) {
  19.           q.push(i);          
  20.         }
  21.       }
  22.  
  23.       //向内层结点进行bfs搜索
  24.       while(!q.empty()){
  25.         //还有内层结点，把存储的上一层结点清空
  26.         ans.clear();
  27.         
  28.         int size = q.size();
  29.         for(int i=0; i<size; i++){
  30.           int root = q.front();
  31.           ans.push_back(root);//存储本层结点
  32.           --degree[root];//该结点被剥去，度减少为0，避免重复入队
  33.           q.pop();  
  34.           //bfs搜索，把剥去外层结点后度变为1的结点加入队列       
  35.           for(int j=0; j<G[root].size(); j++){
  36.             int node = G[root][j];
  37.             --degree[node];
  38.             if(degree[node]==1){
  39.               q.push(node);              
  40.             }
  41.           }
  42.         }
  43.       }      
  44.       return ans;
  45.     }
  46. };

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/799409
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号