详细布置

今天这三道题都非常难，那么这么难的题，为啥一天做三道？

因为 一刷 也不求大家能把这么难的问题解决，所以 大家一刷的时候，就了解一下题目的要求，了解一下解题思路，不求能直接写出代码，先大概熟悉一下这些题，二刷的时候，随着对回溯算法的深入理解，再去解决如下三题。

大家今天的任务，其实是 对回溯算法章节做一个总结就行。

重点是看 回溯算法总结篇：

https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html

332.重新安排行程（可跳过）

https://programmercarl.com/0332.%E9%87%8D%E6%96%B0%E5%AE%89%E6%8E%92%E8%A1%8C%E7%A8%8B.html

Tips：如果单纯的回溯搜索（深搜）并不难，难还是难在容器的选择和使用上。

我的题解：

class Solution {
public:
// unordered_map<出发机场, map<到达机场, 航班次数>> targets
    unordered_map<string, map<string, int>> targets;
    vector<string> result;

    bool backtracking(int ticketNum){
        if(result.size() == ticketNum){
            return true;
        }

        for(pair<const string,int>& target : targets[result[result.size() - 1]]){
            if(target.second > 0){
                result.push_back(target.first);
                target.second--;
                if(backtracking(ticketNum)) return true;
                result.pop_back();
                target.second++;
            }
        }
        return false;
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for(const vector<string>& vec:tickets){
            targets[vec[0]][vec[1]]++;
        }
        result.push_back("JFK");
        backtracking(tickets.size() + 1);
        return result;
    }
};

51. N皇后（可跳过）

https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html

视频讲解：https://www.bilibili.com/video/BV1Rd4y1c7Bq

Tips：N皇后问题其实想明白思路之后，回溯这部分并不复杂，复杂的还是数据结构的选择以及对是否满足条件的判定。

棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里了。

我的题解：

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

    void backtracking(int n, int row){
        if(row == n){
            result.push_back(path);
            return;
        }

        for(int i = 0; i<n; i++){
            if(check(i,row, n)){
                path[row][i] = 'Q';
                backtracking(n,row+1);
                path[row][i] = '.';
            }
        }
    }

    bool check(int col, int row, int n){
        for(int i = 0; i < row; i++){
            if(path[i][col] == 'Q'){
                return false;
            }
        }

        for(int i = row - 1, j = col - 1; i>=0 && j>=0; i--,j--){
            if(path[i][j] == 'Q'){
                return false;
            }
        }

        for(int i = row - 1, j = col + 1; i>=0 && j < n; i--,j++){
            if(path[i][j] == 'Q'){
                return false;
            }
        }
        return true;
    }

    vector<vector<string>> solveNQueens(int n) {
        path = vector<string>(n,string(n,'.'));
        backtracking(n, 0);
        return result;
    }
};

37. 解数独（可跳过）

https://programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html

视频讲解：https://www.bilibili.com/video/BV1TW4y1471V

Tips：一波分析之后，再看代码会发现其实也不难，唯一难点就是理解二维递归的思维逻辑。

再就是对九宫格起始位置的计算是比较巧妙的。

我的题解：

class Solution {
public:

    bool backtracking(vector<vector<char>>& board){
        for(int i = 0;i<9 ;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]=='.'){
                    for(int k='1'; k<='9';k++){
                        if(judge(board,i,j,k)){
                            board[i][j] = k;
                            if(backtracking(board)) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    bool judge(vector<vector<char>>& board, int row, int col, char num){
        for(int i = 0; i<9; i++){
            if(board[i][col] == num || board[row][i] == num){
                return false;
            }
        }

        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for(int i = startRow; i< startRow + 3; i++){
            for(int j = startCol; j < startCol + 3; j++){
                if(board[i][j] == num){
                    return false;
                }
            }
        }
        return true;
    }

    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);
    }
};

总结

https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html