代码随想录训练营第三十天|332.重新安排行程51. N皇后37. 解数独

本文主要是介绍代码随想录训练营第三十天|332.重新安排行程51. N皇后37. 解数独，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

332.重新安排行程

采用哈希表方式进行储存出发点和到达点，终止条件是result中的机场数量为机票+1；

重点在于哈希表的运用和遍历方法

51. N皇后

wtf?

回溯算法非常形象的N叉树解法：

输入n，row col,chessboard

终止条件：棋盘行数==n

单层循环逻辑，Q所在位置的上下左右和斜线都无Q即为合法，合法就放进去ok

class Solution {
private:
vector<vector<string>> result;
// n 为输入的棋盘大小
// row 是当前递归到棋盘的第几行了
void backtracking(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'; // 放置皇后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;}}// 检查 45度角是否有皇后for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {if (chessboard[i][j] == 'Q') {return false;}}// 检查 135度角是否有皇后for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if (chessboard[i][j] == 'Q') {return false;}}return true;
}
public:vector<vector<string>> solveNQueens(int n) {result.clear();std::vector<std::string> chessboard(n, std::string(n, '.'));backtracking(n, 0, chessboard);return result;}
};

有的时候画个图真的用管用的