摘要

• 今天以尝试较难的题目为主，为日后复习做准备。
• DFS可以看做一个“拆边”的过程，用回溯法来搜索合适的“拆边”方案。
• N皇后和数独问题都可以通过模拟过程，抽象出构造答案的树形结构，用回溯法搜索答案。
• 数独问题的有一个剪枝条件隐含在枚举[1-9]仍不能填入当前位置，说明之前填入的数字也要调整，应该直接返回到上一层进行调整，而不能跳过当前位置。

LeetCode332 重新安排行程

332. 重新安排行程 - 力扣（Leetcode）

• 这道题目也是图论DFS的经典题目，虽然目前复习进度还没有到图的部分，但这道题目套用回溯法的模板也还算能写。
• 直观地去理解DFS，就是一个“拆边”的过程，把所有边拆完了（在本题中是将所有边拆完，即“用完所有的机票”），就到达回溯法树形结构的叶节点了，此时就要判断是否要收集答案。
• 以LeetCode的示例2为例，先模拟一下“安排行程”的过程

• 题目还要求按字典序返回最小的行程组合，为了满足这一要求，每次选取下一个目的地时，应该优先选取字典序最小的目的地，这蕴含了“贪心”的思想。
• 拆边的过程如下图，当前所在节点用青蓝色表示，题目要求从“JFK”开始

• 取以上每一步的当前节点，即得到答案：["JFK","ATL","JFK","SFO","ATL","SFO"]

• 这道题目如果不使用STL的话，要自己实现从地点名到数组下标的映射，以便保存机票数组对应的图的邻接矩阵。我目前阶段的复习以逻辑和概念为主，这次先不重复造轮子了，之后补一个不用STL的map的题解。

• 既然要DFS，首先肯定要在代码中把图表示出来，图的实现有两种，一是邻接表，二是邻接矩阵。使用STL的map能很方便的实现邻接矩阵，通过哈希映射，就不需要我们自己手动将地点名映射到数组下标来构建邻接矩阵了。这道题目的图是可以有很多重边的，所以邻接矩阵的值是可以大于1的，用来记录到底从起点到终点有几条边。

unordered_map<string, map<string, int>> ticketsMap;
for (auto& iter : tickets) {
    ticketsMap[iter[0]][iter[1]]++;
}

• 以上代码的含义为：unordered_map<起点机场，map<终点机场，有几张票>>

• 另外要注意的是，map会自动按key值对存入的二元组进行排序，这里key值为终点机场string，所以用map保存时自动按字典序升序排列了终点机场。这样就能保证先尝试的下一个机场的字典序是较小的，从而我们第一次得到的一条合法路径的字典序应该是最小的。

• 其实，处理好如何保存图的邻接矩阵，并利用map解决了字典序的问题，这道题目用回溯法的模板就比较好解决了，至于再往后的优化，还是之后复习到图的部分后再回来继续学习吧。

• 另外要注意的是，对于图的问题，叶节点的深度是不确定的，所以没有明确的递归终止条件。但有收集答案的条件，即第一次得到合法路径时直接返回当前路径到主函数。

完整的题解代码如下

class Solution {
public:
    void backtracking(unordered_map<string, map<string, int>>& ticketsMap,
                    vector<string>& res, int ticketsNum, bool& reach)
    {
        if (res.size() == ticketsNum + 1) {
            reach = true;
            return;
        }
        for (auto& iter :  ticketsMap[res.back()]) {
            if (iter.second) {
                res.push_back(iter.first);
                iter.second--;
                backtracking(ticketsMap, res, ticketsNum, reach);
                if (reach) return;
                iter.second++;
                res.pop_back();
            }
        }
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, map<string, int>> ticketsMap;
        for (auto& iter : tickets) {
            ticketsMap[iter[0]][iter[1]]++;
        }
        vector<string> res;
        res.push_back("JFK");
        bool reach = false;
        backtracking(ticketsMap, res, tickets.size(), reach);
        return res;
    }
};

LeetCode51 N皇后

51. N 皇后 - 力扣（Leetcode）

• 在放下一枚皇后之前，应该判断当前位置是否能让皇后彼此之间不互相攻击。即判断在同一行、同一列，同一条斜线（注意有两条，一条平行于主对角线，一条垂直于主对角线）上不能有两枚皇后。不难直接写出以下函数：（cur表示当前棋盘的状态）

bool isNotValid(vector<string>& cur, int row, int col, int n) {
    // 同一行
    for (int i = 0; i < n; i++) {
        if (cur[row][i] == 'Q' && i != col) return true;
    }
    // 同一列
    for (int i = 0; i < n; i++) {
        if (cur[i][col] == 'Q' && i != row) return true;
    }
    
    // 同一斜线（平行于主对角线的斜线）
    for (int i = 1; row - i >= 0 && col - i >= 0; i++) {
        if (cur[row - i][col - i] == 'Q') return true;
    }
    for (int i = 1; row + i < n && col + i < n; i++) {
        if (cur[row + i][col + i] == 'Q') return true;
    }
    
    // 同一斜线（垂直于主对角线的斜线）
    for (int i = 1; row - i >= 0 && col + i < n; i++) {
        if (cur[row - i][col + i] == 'Q') return true;
    }
    for (int i = 1; row + i < n && col - i >= 0; i++) {
        if (cur[row + i][col - i] == 'Q') return true;
    }
    return false;
}

• 当然，这是最直接也是最简陋的判断方式。简洁的判断方式有很多，之后再继续复习。
• 有了以上函数，就可以在回溯法中对不符合要求的摆放方式进行剪枝，最终收集到符合要求的摆放方式。
  • 逐行放置皇后，判断当前的摆放方案是否合法
  • 不合法则直接剪枝，无需再继续尝试
  • 递归的终止条件为最后一行摆放完成。

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

• N皇后问题还有很多可以深入讨论的地方，以上这种模拟摆放的实现方式虽然直观，但不是效率最高的方法。直观有时候意味着对问题的抽象程度还不够，所以效率不够高也是自然的。

LeetCode37 解数独

37. 解数独 - 力扣（Leetcode）

• 回溯法基本都是在模拟构造答案的过程，将答案的构造过程抽象为树形结构进行搜索：。填写数独，首先就要判断当前位置能填写什么数字，不难根据数独的规则直接写出如下剪枝函数

bool isValid(int row, int col, char k, vector<vector<char>>& board) {
    // 同一行或同一列
    for (int i = 0; i < board.size(); i++) {
        if (i != col && board[row][i] == k) return false;
        if (i != row && board[i][col] == k) return false; 
    }
    // 同一个九宫格
    int Row = row / 3 * 3;
    int Col = col / 3 * 3;
    for (int i = Row; i < Row + 3; i++) {
        for (int j = Col; j < Col + 3; j++)
            if (i != row && j != col && board[i][j] == k) return false;
    }
    return true;
}

• 递归的终止条件：先统计输入的矩阵已经有多少个数字，保存在count中，当count等于81时，说明已经数独的矩阵已经被填满，可以直接返回结果了。

完整的题解代码如下，用row控制逐行填写矩阵，减少不必要的遍历

class Solution {
public:
    bool isValid(int row, int col, char k, vector<vector<char>>& board) {
        // 同一行或同一列
        for (int i = 0; i < board.size(); i++) {
            if (i != col && board[row][i] == k) return false;
            if (i != row && board[i][col] == k) return false; 
        }
        // 同一个九宫格
        int Row = row / 3 * 3;
        int Col = col / 3 * 3;
        for (int i = Row; i < Row + 3; i++) {
            for (int j = Col; j < Col + 3; j++)
                if (i != row && j != col && board[i][j] == k) return false;
        }
        return true;
    }
    void backtracking(vector<vector<char>>& board, bool& solved,
                    int& count, int row)
    {
        if (count == board.size() * board.size()) {
            solved = true;
            return;
        }
        for (int i = row; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] != '.') continue;

                for (char k = '1'; k <= '9'; k++) {
                    if (isValid(i, j, k, board)) {
                        count++;
                        board[i][j] = k;
                        // 用三目表达式控制换行
                        backtracking(board, solved, count, j < 8 ? row : row + 1);
                        if (solved) return;
                        board[i][j] = '.';
                        count--;
                    }
                }
                // 如果程序执行到这里
                // 表示这个位置不能填入任何数，前面填入的数字也需要调整，直接返回
                return;
                // 不能跳过当前位置再去填下一个位置
            }
        }
    }
    void solveSudoku(vector<vector<char>>& board) {
        bool solved = false;
        int count = 0;
        // 统计固定好的数字个数
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] != '.') count++;
            }
        }
        backtracking(board, solved, count, 0);
    }
};

• 填数独问题中，有一个剪枝方式和之前的题目都不同，我在这里卡了一会

for (int i = row; i < board.size(); i++) {
    for (int j = 0; j < board[0].size(); j++) {
        if (board[i][j] != '.') continue;

        for (char k = '1'; k <= '9'; k++) {
            if (isValid(i, j, k, board)) {
                count++;
                board[i][j] = k;
                // 用三目表达式控制换行
                backtracking(board, solved, count, j < 8 ? row : row + 1);
                if (solved) return;
                board[i][j] = '.';
                count--;
            }
        }
        // 如果程序执行到这里
        // 表示这个位置不能填入任何数，前面填入的数字也需要调整，直接返回
        return;/**/
        // 不能跳过当前位置再去填下一个位置
    }
}

• 后跟/**/的那句return是很关键的剪枝，
  • 这个剪枝不是在尝试填入数字之前进行的，
  • 而是尝试完所有数字后仍然不能进入下一层递归才进行的剪枝
  • 与在尝试枚举当前位置的元素之前进行的剪枝不同，这种剪枝是在尝试枚举当前位置的元素之后进行的。
  • 因为没有显式的if来描述剪枝条件，剪枝条件暗含在尝试了所有元素仍不能填入当前位置，只有短短的一句return，非常容易忘记写，导致代码逻辑不对。