算法笔记-这次真的学会了递归

//先记录一下最初的错误解法，C++
class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        if(A.size() == 0){
            return;
        }
        int num = A.size();  //最下面的圆盘的下标
        hanoi(num , A , B , C);
    }
    void hanoi(int n , vector<int>& A, vector<int>& B, vector<int>& C){
        if(n == 1) {
            C.push_back(A[n - 1]);
            return ;
        } 
        hanoi(n - 1 , A , C , B);
        C.push_back(A[n - 1]); //问题出在这里欧~！
        hanoi(n - 1 , B , A , C);
    }
};

//出错了，如下图所示。为什么把A中的元素push_back到C里，答案不对呢？
//仔细想想汉诺塔的移动过程，我们
//1. 首先要把n-1个圆盘【借助C从A移动到B】，此时A柱子上只有1个圆盘（即第n个），B柱子上有n-1个圆盘，C柱子是空的；
//2. 然后把第n个圆盘从A移动到C，此时A柱子是空的，B柱子上还是有n-1个圆盘，C柱子上有1个圆盘（即第n个）
//3. 然后把n-1个圆盘【借助A从B移动到C】。
//需要注意的是，被借助的柱子，初始状态应该是空的才对！也就是说，无论是A还是B或者C柱子，在移动的过程中都需要有【清空】的时候才对。那么！push_back只是取值啊，没有真正的移动，在这个过程中A永远不会是空。
//用remove欧~
//当然了还要注意的一个问题是：自定义函数hanoi里的A、B、C，和题目中指定好的A柱子、B柱子、C柱子是不一样的。hanoi函数的参数A表示的是【源柱子】，参数B表示的是【中间柱子】，参数C表示的是【目标柱子】。所以有的题解会把A叫做from，B叫做process，C叫做to，是蛮清晰的。
//对了。输入样例是【从大到小】的。

//正确答案！
class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        if(A.size() == 0){
            return;
        }
        int num = A.size();  //最下面的圆盘的【下标】
        hanoi(num , A , B , C);
    }
    void hanoi(int n , vector<int>& A, vector<int>& B, vector<int>& C){
        if(n == 0)  return ;
        hanoi(n - 1 , A , C , B);
        C.push_back(A.back());//是A.back(),不是A[n-1]啊，因为输入是【从大到小的！！】，最小的在最后面
        A.pop_back();
        hanoi(n - 1 , B , A , C);
    }
};

//chessboard的类型是一维string类型的数组：vector<string>,存放单个棋盘合法的摆放情况
//result的类型是二维数组：vector<vector<string>>，存放所有的chessboard
class Solution {
public:
    vector<vector<string>> result; //存放结果

    void backtracking(int n, int row, vector<string>& chessboard){
        if(row == n){ //终止条件：搜索到了最后一行
            result.emplace_back(chessboard);
            return;
        }
        for(int col = 0; col < n ; col ++){//按列搜索，需要注意上界：col < n 不能取等！（一开始就是这里WA了
            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) {
        result.clear();  //这句话最好加上
        vector<string> chessboard(n, string(n, '.'));  //初始化单个棋盘
        backtracking(n, 0, chessboard);
        return result;
    }
};