代码随想录算法训练营刷题复习8 ：回溯算法——子集、排列、棋盘问题

51 阅读 0 评论 0 点赞

回溯算法

子集问题

①res,path; backtracking函数
②无递归终止条件判断，直接path存入res；
③递归需要startIndex；
④(补充)“有重复元素、不能包含重复的解集” 在for循环多加判断条件：i>0 && used[i-1]==false && nums[i]==nums[i-1] 跳过同层重复元素的处理

78. 子集
递归终止条件可以省略（与for循环的判断条件一致），每次递归调用的时候先把结果写入到res中
90. 子集 II
此题关于“有重复元素、不能包含重复的解集”的处理方法与组合问题中的一致。其他没有什么强调的了。

78. 子集
递归终止条件可以省略（与for循环的判断条件一致），每次递归调用的时候先把结果写入到res中

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    void backtracking(vector<int>& nums, int startIndex) {
        res.push_back(path);

        for(int i=startIndex;i<nums.size();i++) {
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
        }

    }

    vector<vector<int>> subsets(vector<int>& nums) {
        backtracking(nums,0);
        return res;
    }
};

90. 子集 II
此题关于“有重复元素、不能包含重复的解集”的处理方法与组合问题中的一致。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtracking(vector<int>& nums,int startIndex, vector<bool>& used) {
        res.push_back(path);

        for(int i=startIndex;i<nums.size();i++) {
            if(i>0 && used[i-1]==false && nums[i]==nums[i-1]) {
                continue;
            }
            path.push_back(nums[i]);
            used[i]=true;
            backtracking(nums,i+1,used);
            path.pop_back();
            used[i]=false;
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<bool> used(nums.size(),false);
        backtracking(nums,0,used);
        return res;
    }
};

排列问题

全排列需要对所有元素进行排列，
①终止条件：path.size == nums.size()
②for遍历元素集合为所有元素，用used控制不重复
③有重复元素，要求解集不重复的处理条件：i>0 && nums[i]==nums[i-1] && used[i-1]==false

46. 全排列
排列问题，path写入res中一定是包含了nums的所有元素，只是排列顺序不同
遍历的元素集合为所有元素，只是需要used数组，标记已使用过的元素避免出现重复
47. 全排列 II
还是强调对于不重复解集的处理

46. 全排列
排列问题，path写入res中一定是包含了nums的所有元素，只是排列顺序不同
遍历的元素集合为所有元素，只是需要used数组，标记已使用过的元素避免出现重复

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    void backtracking(vector<int>& nums, vector<bool>& used) {
        if(path.size()==nums.size()) {
            res.push_back(path);
        }

        for(int i=0;i<nums.size();i++) {
            if(used[i]==true)
                continue;
            path.push_back(nums[i]);
            used[i]=true;
            backtracking(nums,used);
            path.pop_back();
            used[i]=false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(),false);
        backtracking(nums,used);
        return res;
    }
};

47. 全排列 II
还是强调对于不重复解集的处理

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    void backtracking(vector<int>& nums, vector<bool>& used) {
        if(path.size()==nums.size()) {
            res.push_back(path);
        }
        for(int i=0;i<nums.size();i++) {
            if(used[i]==true) {
                continue;
            }else if(i>0 && nums[i]==nums[i-1] && used[i-1]==false){
                continue;
            }
            path.push_back(nums[i]);
            used[i]=true;
            backtracking(nums,used);
            path.pop_back();
            used[i]=false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<bool> used(nums.size(),false);
        backtracking(nums,used);
        return res;
    }
};

棋盘问题

需要定义棋盘（或题目给出），一层or两层循环（看题目逻辑），单独的isValid函数判断放置是否合理
①backtracking函数，棋盘选择按行递归或者逐元素递归
②isValid函数判断放置是否合理

51. N 皇后
1.构建棋盘 vector chessboard(n,string(n,‘.’));
2.逐行使用回溯，使用isValid函数判断放置位置是否合理
3.isValid函数，判断列、45度方向、135度方向放置是否合理
37. 解数独
1.双层循环，i j定位到要放数字的点，isValid判断是否符合逻辑，使用回溯递归调用
2.isValid判断行、列，以及内部小九格是否有重复数字

51. N 皇后
1.构建棋盘 vector chessboard(n,string(n,‘.’));
2.逐行使用回溯，使用isValid函数判断放置位置是否合理
3.isValid函数，判断列、45度方向、135度方向放置是否合理

class Solution {
public:
    vector<vector<string>> res;
    void backtracking(int n,int row,vector<string>& chessboard) {
        if(row == n) {
            res.push_back(chessboard);
            return;
        }
        for(int col = 0;col<n;col++) {
            if(isValid(row,col,chessboard,n)) {
                chessboard[row][col] = 'Q';
                backtracking(n,row+1,chessboard);
                chessboard[row][col] = '.';
            }
        }
    }
    bool isValid(int row,int col, vector<string>& chessboard,int n) {
        for(int i = 0;i<row;i++) {
            if(chessboard[i][col]=='Q') {
                return false;
            }
        }
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--) {
            if(chessboard[i][j]=='Q') {
                return false;
            }
        }
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++) {
            if(chessboard[i][j]=='Q') {
                return false;
            }
        }
        return true;
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<string> chessboard(n,string(n,'.'));
        backtracking(n,0,chessboard);
        return res;
    }
};

37. 解数独
1.双层循环，i j定位到要放数字的点，isValid判断是否符合逻辑，使用回溯递归调用
2.isValid判断行、列，以及内部小九格是否有重复数字

class Solution {
public:
    bool backtracking(vector<vector<char>>& board) {
        for(int i=0;i<board.size();i++) {
            for(int j=0;j<board[0].size();j++) {
                if(board[i][j]=='.') {
                    for(char c = '1';c<='9';c++) {
                        if(isValid(i,j,c,board)) {
                            board[i][j]=c;
                            if(backtracking(board)) {
                                return true;
                            }board[i][j]='.';
                        }
                            
                    }
                    return false;
                }
            }
        }
        return true;
    }

    bool isValid(int row,int col,char k,vector<vector<char>>& board) {
        for(int i=0;i<9;i++) {
            if(board[row][i] == k)
                return false;
        }
        for(int i=0;i<9;i++) {
            if(board[i][col] == k)
                return false;
        }
        
        int row_1 = (row/3)*3;
        int col_1 = (col/3)*3;
        for(int i=row_1;i<row_1+3;i++) {
            for(int j=col_1;j<col_1+3;j++) {
                if(board[i][j]==k)
                    return false;
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};

本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！

转载请注明出处：免费源码网-免费的源码资源网站 » 代码随想录算法训练营刷题复习8 ：回溯算法——子集、排列、棋盘问题

点赞(0) 打赏

本文分类：文章资讯
本文标签：代码随想录算法训练营刷题复习8 ：回溯算法——子集、排列、棋盘问题
浏览次数：51 次浏览
本文链接：https://freeymw.com/article/13836.html

上一篇 > springboot代理配置，本地访问测试环境数据库、测试环境elasticsearch
下一篇 > GIF转字符画

评论列表共有 0 条评论

暂无评论

代码随想录算法训练营刷题复习8 ：回溯算法——子集、排列、棋盘问题

回溯算法

子集问题

排列问题

棋盘问题

评论列表 共有 0 条评论

发表评论 取消回复

评论列表共有 0 条评论

发表评论取消回复