my-leetcode-logs-20230904

47. 全排列 II（C++回溯算法实现）

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

    void backtracing(vector<int>& nums, vector<bool>& used){
        //在叶子结点收集元素
        if(path.size() == nums.size()){
            result.push_back(path);
            return;
        }

        for(int i = 0;i < nums.size();i ++){
            // 判断同层中是否已经使用了相同的元素
            if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false){
                continue;//表示已经使用过了
            }

            //表示当前元素没有使用过
            if(used[i] == false){
                used[i] = true;
                path.push_back(nums[i]);
                backtracing(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false);
        backtracing(nums, used);
        return result;
    }
};

51. N 皇后（C++回溯法实现）

class Solution {
public:
    vector<vector<string>> result;

    //判断是否合法
    bool isValid(int row, int col, vector<string>& chessboard, int n){
        //检查列
        for(int i = 0;i < row;i ++){
            if(chessboard[i][col] != '.'){
                return false;
            }
        }

        //检查左上角45度
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            if(chessboard[i][j] != '.'){
                return false;
            }
        }

        //检查右下角135度
        for(int i = row - 1, j = col + 1; i >=0 && j < n; i--, j++){
            if(chessboard[i][j] != '.'){
                return false;
            }
        }
        return true;
    }

    void backtracing(int n, int row, vector<string>& chessboard){
        if(row == n){//表示到最后一层了
            result.push_back(chessboard);
            return;
        }

        //循环棋盘，然后判断是否合法
        for(int col = 0; col < n; col++){
            if(isValid(row, col, chessboard, n)){//如果合法，那么修改棋盘
                chessboard[row][col] = 'Q';//放置皇后
                backtracing(n, row + 1, chessboard);
                chessboard[row][col] = '.';
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        result.clear();
        std::vector<std::string> chessboard(n, std::string(n, '.'));
        backtracing(n, 0, chessboard);
        return result;
    }
};