摘要
- 今天以尝试较难的题目为主，为日后复习做准备。
- DFS可以看做一个“拆边”的过程，用回溯法来搜索合适的“拆边”方案。
- N皇后和数独问题都可以通过模拟过程，抽象出构造答案的树形结构，用回溯法搜索答案。
- 数独问题的有一个剪枝条件隐含在枚举[1-9]仍不能填入当前位置，说明之前填入的数字也要调整，应该直接返回到上一层进行调整，而不能跳过当前位置。
LeetCode332 重新安排行程
- 这道题目也是图论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皇后
- 在放下一枚皇后之前，应该判断当前位置是否能让皇后彼此之间不互相攻击。即判断在同一行、同一列，同一条斜线（注意有两条，一条平行于主对角线，一条垂直于主对角线）上不能有两枚皇后。不难直接写出以下函数：（
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 解数独
- 回溯法基本都是在模拟构造答案的过程，将答案的构造过程抽象为树形结构进行搜索：。填写数独，首先就要判断当前位置能填写什么数字，不难根据数独的规则直接写出如下剪枝函数
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，非常容易忘记写，导致代码逻辑不对。
