算法刷题Day30 | 332.重新安排行程、51. N皇后、37. 解数独

news/2024/5/4 4:09:55/文章来源:https://blog.csdn.net/hhw_hhw/article/details/137546571

0 引言

听说今天的题目很难，但是我呢，必须拿下。

1 重新安排行程

🎈 文档讲解
🎈 视频讲解
🎈 做题状态：

其实这道题就是有向图的深度有限搜索，使用递归的方式。其实也就是二叉树的前中后序遍历。
图的广度有限搜索也就对应二叉树的层次遍历，采用队列结构和while循环。

1.1 我的解题

其实就是回溯问题，只不过要想好终止条件，以及分支条件。但是我这个暴力搜索的方法超时了。

class Solution {
public:// 这个感觉就是递归，为什么需要回溯呢，会存在多条路径所以需要回溯void backTracing(vector<vector<string>>& tickets, vector<bool>& used, vector<string>& path, vector<vector<string>>& paths){// 终止条件if (path.size() == tickets.size() + 1){paths.emplace_back(path);return;}// 单层回溯逻辑for (int i = 0; i < tickets.size(); i++){// 如果当前路径没有使用过，且是满足路径的要求的话，则添加if (used[i] == false && tickets[i][0] == path[path.size() - 1]){path.emplace_back(tickets[i][1]);used[i] = true;backTracing(tickets, used, path, paths);path.pop_back();used[i] = false;}}}vector<string> findItinerary(vector<vector<string>>& tickets) {vector<bool> used(tickets.size(), false);vector<string> path = {"JFK"};vector<vector<string>> paths;backTracing(tickets, used, path, paths);// 从paths中找出字典排序最小的结果int minIndex = 0;for (int i = 1; i < paths.size(); i++){       if (paths[i] < paths[minIndex]){minIndex = i;}}  return paths[minIndex];}
};

1.2 更好的解法

首先得理解下面这段代码的含义。

unordered_map<string, map<string, int>> targets;
targets["JFK"]["TIS"]++;

targets["JFK"]["TIS"]++;

这行代码在做几件事情：
首先，它试图访问targets这个unordered_map的键为"JFK"的元素。如果"JFK"不存在于targets中，C++会自动创建这个键，并将其映射到一个新的（空的）内部map容器。
接着，它试图访问内部map（即"JFK"键对应的值）的键为"TIS"的元素。同样地，如果"TIS"不存在于这个内部map中，C++会自动创建这个键，并将其映射到一个int类型的值，这个值默认初始化为0（这是int类型的默认值）。
最后，++操作符会将"TIS"对应的值增加1。这意味着，我们就把从"JFK"到"TIS"的票数增加了1。

2 N皇后

🎈 文档讲解
🎈 视频讲解
🎈 做题状态：

2.1 我的解题

我感觉不算太难，就是比较繁琐，时间复杂度需要控制。主要是判断当前位置是否合法，也就是根据行列号，棋盘元素进行判断。回溯直接就是模板。

我一开始写的代码判断是否有皇后可以优化，因为判断是一行一行往下的，所以皇后一定是在当前行的上面才有。所以在判断斜线方向是否有皇后时，只需判断上面的行的元素即可。也就是判断45°和135°。不需要判断225°和315°这两个方向。

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;}
};