回溯算法---Backtracking Algorithm

文章目录

• 一、回溯算法的定义
• 二、回溯算法的模型

  • 深度优先搜索
  • 广度优先搜索

• 三、有关回溯算法的题型

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector subordinates;
};
*/
 
class Solution {
public:
    int DFS(unordered_map<int,Employee*>&info,int id)
    {
        int sumImportance=info[id]->importance;
        //深度探索员工一的下属然后往下探索员工二的下属……
        for(auto e:info[id]->subordinates)
        {
            sumImportance+=DFS(info,e);
            
        }
        //最后返回员工的数据结构中的重要度的和
        return sumImportance;
    }
    int getImportance(vector employees, int id) {
        //如果此时没有保存员工的数据结构则返回空的重要度
        if(employees.empty())
        return 0;
        //为了使时间效率更高可以使用哈希的结构，因为哈希的查找效率比较高
        unordered_map<int,Employee*> info;
        //将员工的信息的数据结构放入哈希表中        
        for(auto e:employees)
        {
            info[e->id]=e;
        }
        return DFS(info,id);//将哈希表中的内容进行深度优先搜索操作
    }
};

2.图像渲染OJ链接

int nextp[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
class Solution {
public:
    void DFS(vectorint>>&image,vectorint>>&book,int row,int col,int sr,int sc,int oldColor,int newColor)
    {
        image[sr][sc]=newColor;
        book[sr][sc]=1;
 
        for(int i=0;i<4;i++)
        {
            int newX=sr+nextp[i][0];
            int newY=sc+nextp[i][1];
            if(newX>=row||newX<0)
            {
                continue;
            }
            if(newY>=col||newY<0)
            {
                continue;
            }
            if(image[newX][newY]==oldColor&&book[newX][newY]==0)
            {
                DFS(image,book,row,col,newX,newY,oldColor,newColor);
            }
        }
    }
    vectorint>> floodFill(vectorint>>& image, int sr, int sc, int color) {
        if(image.empty())
        {
            return image;
        }
        vectorint>> book(image.size(),vector<int>(image[0].size(),0));
        int oldColor=image[sr][sc];
        DFS(image,book,image.size(),image[0].size(),sr,sc,oldColor,color);
        return image;
    }
};

3.岛屿的周长OJ链接

int nextp[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//给定方向矩阵
class Solution {
public:
    int DFS(vectorint>> &grid,int row,int col,int x,int y)
    {
        if(x>=row||x<0||y>=col||y<0||grid[x][y]==0)  return 1;
        
        if(grid[x][y]==2)  return 0;
 
        grid[x][y]=2;//标记此时位置已经搜索过
        int s=0;
        //对于此时的位置进行深度优先遍历操作
        for(int k=0;k<4;k++)
        {
            int newX=x+nextp[k][0];
            int newY=y+nextp[k][1];
 
            //对于该位置进行深度优先遍历求出此时的位置有效的边界长度
            s+=DFS(grid,row,col,newX,newY);
        }
        return s;
    }
    int islandPerimeter(vectorint>>& grid) {
        if(grid.empty())
        return 0;
 
        int row=grid.size();
        int col=grid[0].size();
        int c=0;
 
        for(int i=0;i
        {
            for(int j=0;j
            {
                //对于陆地进行深度优先遍历操作
                if(grid[i][j]==1)
                c+=DFS(grid,row,col,i,j);
            }
        }
        return c;
    }
};

4.被围绕的区域OJ链接

int nextp[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
class Solution {
public:
    void DFS(vectorchar>>&board,int row,int col,int sr,int sc)
    {
        board[sr][sc]='*';//标记此时为‘O’深度探索是否被
        for(int i=0;i<4;i++)
        {
            int newX=sr+nextp[i][0];//将此时的方向进行四个方向进行深度优先遍历操作
            int newY=sc+nextp[i][1];
            if(newX<0||newX>=row)//需要对此时的方向进行判断是否是越界行为，如果是越界行为则此时跳过去，进行下一个方向的深度优先遍历操作
            {
                continue;
            }
            if(newY<0||newY>=col)
            {
                continue;
            }
            if(board[newX][newY]!='*'&&board[newX][newY]!='X')//
            //继续搜索‘O’
            {
                DFS(board,row,col,newX,newY);
            }
        }
}
    void solve(vectorchar>>& board) {
        if(board.empty())
        return;
        int row=board.size();
        int col=board[0].size();
        //第一行和最后一行进行深度优先遍历
        for(int j=0;j
        {
            if(board[0][j]=='O')
            DFS(board,row,col,0,j);
            if(board[row-1][j]=='O')
            DFS(board,row,col,row-1,j);
        }       
        //第一列和最后一列进行深度优先遍历
        for(int i=0;i
        {
            if(board[i][0]=='O')
            DFS(board,row,col,i,0);
            if(board[i][col-1]=='O')
            DFS(board,row,col,i,col-1);
        }
        //最后将深度搜索的结果进行修改
        for(int i=0;i
        {
            for(int j=0;j
            {
                if(board[i][j]=='*')//最后将所有的'*'改为‘O’
                {
                    board[i][j]='O';
                }
                else if(board[i][j]=='O')//最后将所有的'O'改为‘X’
                {
                    board[i][j]='X';
                }
            }
        }
    }
};

5.岛屿数量OJ链接

int nextp[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//定义一个方向矩阵
class Solution {
public:
    void DFS(vectorchar>>&grid,vectorint>>&book,int row,int col,int x,int y)
    {
        book[x][y]=1;//标记此时的位置已经走过
 
        for(int k=0;k<4;k++)//对于当前x，y的位置进行方向遍历操作
        {
            int newX=x+nextp[k][0];//对于x的横向坐标
            int newY=y+nextp[k][1];//对于y的纵向坐标
 
            if(newX>=row||newX<0||newY>=col||newY<0)//考虑一下边界的问题，如果此时走到了边界应该访问下一个位置
                continue;
            if(grid[newX][newY]=='1'&&book[newX][newY]==0)
                DFS(grid,book,row,col,newX,newY);
        }
    }
    int numIslands(vectorchar>>& grid) {
        if(grid.empty())
        return 0;
 
        int row=grid.size();
        int col=grid[0].size();
        //标记矩阵
        vectorint>> book(row,vector<int>(col,0));
        int amount=0;
 
        for(int i=0;i
            for(int j=0;j
                if(grid[i][j]=='1'&&book[i][j]==0)
                {
                    amount++;
                    DFS(grid,book,row,col,i,j);
                }
        return amount;
    }
};

6.岛屿的最大面积OJ链接

int nextp[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//给定方向矩阵
int s=0;//定义全局变量来求出每个岛屿的面积
class Solution {
public:
    void DFS(vectorint>>&grid,int row,int col,int x,int y)
    {
        //如果此时为陆地则进行S++
        if(grid[x][y]==1)
        s++;
        grid[x][y]=2;//同时标记此时已经走过
 
        for(int k=0;k<4;k++)//从当前位置进行方向遍历
        {
            int newX=x+nextp[k][0];
            int newY=y+nextp[k][1];
            if(newX<0||newX>=row||newY<0||newY>=col)
                continue;
            if(grid[newX][newY]==1)//从陆地开始进行深度遍历
            DFS(grid,row,col,newX,newY);
        }
    }
    int maxAreaOfIsland(vectorint>>& grid) {
        if(grid.empty())
        return 0;
        
        int row=grid.size();
        int col=grid[0].size();
        int maxS=0;
 
        for(int i=0;i
            for(int j=0;j
                if(grid[i][j]==1)//从陆地开始进行深度优先遍历操作
                //将每一个位置进行比较，找出最大那个岛屿的面积
                {
                    DFS(grid,row,col,i,j);
                    maxS=max(maxS,s);
                    s=0;
                }
        return maxS;
    }
};

7.电话号码的字母组合OJ链接

map<char,string> hashTable={{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
class Solution {
public:
    void DFS(string& digits,vector&resultString,string curStr,int curDepth)
    {
        //如果此时遍历到最后一个
        if(curDepth==digits.size())
        {
            resultString.push_back(curStr);
            return;
        }
        //利用哈希映射的方式进行
        string strMap=hashTable[digits[curDepth]];
        for(char ch:strMap)
        {
            DFS(digits,resultString,curStr+ch,curDepth+1);
        }
    }
    vector letterCombinations(string digits) {
        //将所有的结果集保存到resultString
        vector resultString;
        if(digits.empty())
        return resultString;
        //从第一个位置开始进行深度优先遍历深度优先遍历
        DFS(digits,resultString,"",0);
        return resultString;      
    }
};

8.组合总和OJ链接

class Solution {
public:
    void DFS(vector<int>&candidates,vectorint>>&solutions,vector<int>&solution,int curSum,int position,int target)
    {
        //如果当前遍历所得到的结果刚好为所给的target值
        //那么将当前所遍历的结果集保留在solutions
        if(curSum==target)
        {
            solutions.push_back(solution);
        }   
        //如果遍历出的和是大于，则说明此时条件不满足
        if(curSum>target)
        {
            return;
        }
        //从position位置开始进行深度优先遍历操作
        for(int i=position;isize();i++)
        {
            if(candidates[i]>target)//如果此时的所给出的candidats中
            // //的值比所给的target大，那么直接结束当前所在位置的优先遍历
            {
                continue;
            }
            //不满足上述条件说明此时的curSum的值小于target
            //可以将当前的candidates[i]放入到当前的结果集中
            //然后接着往后进行深度优先遍历操作
            solution.push_back(candidates[i]);
            DFS(candidates,solutions,solution,curSum+candidates[i],i,target);
            solution.pop_back();
        }
    }
    vectorint>> combinationSum(vector<int>& candidates, int target) {
    //定义一个二维数组保留所有结果集
    vectorint>> solutions;
    //保留当前的结果集
    vector<int> solution;
    //记录当前结果集中的和
    int curSum=0;
    //进行深度优先遍历
    DFS(candidates,solutions,solution,curSum,0,target);
     return solutions;
    }
};

9.活字印刷OJ链接

class Solution {
public:
    void DFS(string &tiles,string curStr,vector<int>&useString,unordered_set&hashTable)
    {
        //如果此时深度优先遍历的字符串不为空，则此时的所得到的的字符串放入当前的哈希表中，将自动进行去重的处理
        if(!curStr.empty())
        hashTable.insert(curStr);
        //深度优先遍历每一个位置
        for(int i=0;isize();i++)
        {
            if(useString[i])//如果当前的位置已经被访问过，则说明此时当前位置不需要访问
            continue;
            useString[i]=1;//标记当前位置
            DFS(tiles,curStr+tiles[i],useString,hashTable);//继续往下进行深度优先遍历的操作
            //需要进行回退的操作
            useString[i]=0;
        }
    }
    int numTilePossibilities(string tiles) {
        if(tiles.empty())
        return 0;
        
        //利用unoreded_set容器的特性，将容器内的内容自动进行去重操作
        unordered_set hashTable;
        //先将当前的tiles进行初始化的操作
        vector<int> useString(tiles.size(),0);
        //进行深度优先遍历操作
        DFS(tiles,"",useString,hashTable);
        return hashTable.size();
    }
};

10.N皇后OJ链接

class Solution {
public:
    //深度优先遍历
    void DFS(vectorint,int>>>&solutions,vectorint,int>>&solution,int curRow,int n)
    {
        //如果当前行等于n则将一种solution方案放入solutions中
        if(curRow==n)
        {
            solutions.push_back(solution);
        }
        for(int i=0;i
        {
            //判断当前皇后所在的位置是否能够满足条件
            if(isValid(solution,curRow,i))
            {
                //如果满足条件则将此时的坐标记录下来
                solution.push_back(make_pair(curRow,i));
                //继续深度优先遍历下一行
                DFS(solutions,solution,curRow+1,n);
                //第一列遍历后回溯下来遍历第二行
                solution.pop_back();
            }
        }
    }
    bool isValid(vectorint,int>>&solution,int curRow,int col)
    {
        //遍历方案中的点
        //如果此时该皇后中的纵坐标与方案中的纵坐标相同或者横坐标与纵坐标的和等于当前皇后的横纵坐标之和或者是方案中横纵坐标之差等于当前皇后的横纵坐标之差
        for(auto i:solution)
        {
            if(i.second==col||i.first+i.second==curRow+col||i.first-i.second==curRow-col)
            {
                return false;
            }
        }
        return true;
    }
    vector> transformString(vectorint,int>>>&solutions,int n)
    {
        vector> resultString;//保留最后方案中的字符串
        for(vectorint,int>>&solution:solutions)
        {
            //利用构造函数先进行所有的字符变为'.'最后再将皇后位置变为'Q'
            vector tmpString(n,string(n,'.'));
            for(pair<int,int> &i:solution)
            {
                tmpString[i.first][i.second]='Q';
            }
            resultString.push_back(tmpString);
        }
        return resultString;
    }
    vector> solveNQueens(int n) {
        vectorint,int>>> solutions;//将不同解法的方案存放
        vectorint,int>> solution;//存放一种方案中的n个皇后的摆放
        //将n*n的棋盘从第一个位置开始进行深度优先遍历
        DFS(solutions,solution,0,n);
        //将深度优先遍历后的每一种方案都转化为字符型
        return transformString(solutions,n);
    }
};

11.N皇后IIOJ链接