青岛品牌网站制作,团购网站开发,汕头高端网站建设,网站建设要程序员吗332 重新安排行程#xff08;hard#xff09;
给你一份航线列表 tickets #xff0c;其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK#xff08;肯尼迪国际机场#xff09;出发的先生…332 重新安排行程hard
给你一份航线列表 tickets 其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK肯尼迪国际机场出发的先生所以该行程必须从 JFK 开始。如果存在多种有效的行程请你按字典排序返回最小的行程组合。
例如行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小排序更靠前。 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
思路
这道题目有几个难点
一个行程中如果航班处理不好容易变成一个圈成为死循环有多种解法字母序靠前排在前面让很多同学望而退步如何该记录映射关系呢 使用回溯法也可以说深搜 的话那么终止条件是什么呢搜索的过程中如何遍历一个机场所对应的所有机场。
1. 如何理解死循环 对于死循环我来举一个有重复机场的例子 为什么要举这个例子呢就是告诉大家出发机场和到达机场也会重复的如果在解题的过程中没有对集合元素处理好就会死循环。
2. 记录映射关系
有多种解法字母序靠前排在前面让很多同学望而退步如何该记录映射关系呢
一个机场映射多个机场机场之间要靠字母序排列一个机场映射多个机场可以使用std::unordered_map如果让多个机场之间再有顺序的话就是用std::map或者std::multimap或者 std::multiset。
这样存放映射关系可以定义为 unordered_mapstring, multiset targets 或者 unordered_mapstring, mapstring, int targets。
含义如下
unordered_mapstring, multiset targetsunordered_map出发机场, 到达机场的集合 targetsunordered_mapstring, mapstring, int targetsunordered_map出发机场, map到达机场, 航班次数 targets这两个结构我选择了后者因为如果使用unordered_mapstring, multisetstring targets 遍历multiset的时候不能删除元素一旦删除元素迭代器就失效了。
再说一下为什么一定要增删元素呢正如开篇我给出的图中所示出发机场和到达机场是会重复的搜索的过程没及时删除目的机场就会死循环。
所以搜索的过程中就是要不断的删multiset里的元素那么推荐使用unordered_mapstring, mapstring, int targets。
在遍历 unordered_map出发机场, map到达机场, 航班次数 targets的过程中可以使用航班次数这个字段的数字做相应的增减来标记到达机场是否使用过了。
如果“航班次数”大于零说明目的地还可以飞如果“航班次数”等于零说明目的地不能飞了而不用对集合做删除元素或者增加元素的操作。
相当于说我不删我就做一个标记
3. 回溯法
这道题目我使用回溯法那么下面按照我总结的回溯模板来
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}本题以输入[[“JFK”, “KUL”], [“JFK”, “NRT”], [“NRT”, “JFK”]为例抽象为树形结构如下 开始回溯三部曲
递归函数参数
在讲解映射关系的时候已经讲过了使用unordered_mapstring, mapstring, int targets; 来记录航班的映射关系我定义为全局变量。
当然把参数放进函数里传进去也是可以的我是尽量控制函数里参数的长度。
参数里还需要ticketNum表示有多少个航班终止条件会用上。
代码如下
// unordered_map出发机场, map到达机场, 航班次数 targets
unordered_mapstring, mapstring, int targets;
bool backtracking(int ticketNum, vectorstring result) {注意函数返回值用的是bool
一般函数返回值都是void这次为什么是bool呢
因为我们只需要找到一个行程就是在树形结构中唯一的一条通向叶子节点的路线所以找到了这个叶子节点了直接返回
当然本题的targets和result都需要初始化代码如下
for (const vectorstring vec : tickets) {targets[vec[0]][vec[1]]; // 记录映射关系
}
result.push_back(JFK); // 起始机场递归终止条件
拿题目中的示例为例输入: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]] 这是有4个航班那么只要找出一种行程行程里的机场个数是5就可以了。
所以终止条件是我们回溯遍历的过程中遇到的机场个数如果达到了航班数量1那么我们就找到了一个行程把所有航班串在一起了。
代码如下
if (result.size() ticketNum 1) {return true;
}单层搜索的逻辑
回溯的过程中如何遍历一个机场所对应的所有机场呢
这里刚刚说过在选择映射函数的时候不能选择unordered_mapstring, multiset targets 因为一旦有元素增删multiset的迭代器就会失效当然可能有牛逼的容器删除元素迭代器不会失效这里就不在讨论了。
可以说本题既要找到一个对数据进行排序的容器而且还要容易增删元素迭代器还不能失效。
所以选择unordered_mapstring, mapstring, int targets 来做机场之间的映射。
遍历过程如下
for (pairconst string, int target : targets[result[result.size() - 1]]) {if (target.second 0 ) { // 记录到达机场是否飞过了result.push_back(target.first);target.second--;if (backtracking(ticketNum, result)) return true;result.pop_back();target.second;}
}可以看出 通过unordered_mapstring, mapstring, int targets里的int字段来判断 这个集合里的机场是否使用过这样避免了直接去删元素。
代码实现
class Solution {
private:
// unordered_map出发机场, map到达机场, 航班次数 targets
unordered_mapstring, mapstring, int targets;
bool backtracking(int ticketNum, vectorstring result) {if (result.size() ticketNum 1) {return true;}for (pairconst string, int target : targets[result[result.size() - 1]]) {if (target.second 0 ) { // 记录到达机场是否飞过了result.push_back(target.first);target.second--;if (backtracking(ticketNum, result)) return true;result.pop_back();target.second;}}return false;
}
public:vectorstring findItinerary(vectorvectorstring tickets) {targets.clear();vectorstring result;for (const vectorstring vec : tickets) {targets[vec[0]][vec[1]]; // 记录映射关系}result.push_back(JFK); // 起始机场backtracking(tickets.size(), result);return result;}
};注意
for (pairconst string, int target : targets[result[result.size() - 1]])一定要加上引用即 target因为后面有对 target.second 做减减操作如果没有引用单纯复制这个结果就没记录下来那最后的结果就不对了。
加上引用之后就必须在 string 前面加上 const因为map中的key 是不可修改了这就是语法规定了
详细解析 代码实现文章 51 N皇后hard
按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
思路标准回溯法再加一个isValid函数判断当前棋子是否可以放即可
首先来看一下皇后们的约束条件
不能同行不能同列不能同斜线
确定完约束条件来看看究竟要怎么去搜索皇后们的位置其实搜索皇后的位置可以抽象为一棵树。
下面用一个 3 * 3 的棋盘将搜索过程抽象为一棵树如图
从图中可以看出二维矩阵中矩阵的高就是这棵树的高度矩阵的宽就是树形结构中每一个节点的宽度。
那么我们用皇后们的约束条件来回溯搜索这棵树只要搜索到了树的叶子节点说明就找到了皇后们的合理位置了。
回溯三部曲
递归函数参数
依然是定义全局变量二维数组result来记录最终结果。
参数n是棋盘的大小然后用row来记录当前遍历到棋盘的第几层了。
代码如下
vectorvectorstring result;
void backtracking(int n, int row, vectorstring chessboard) {递归终止条件
可以看出当递归到棋盘最底层也就是叶子节点的时候就可以收集结果并返回了。
代码如下
if (row n) {result.push_back(chessboard);return;
}单层搜索的逻辑
递归深度就是row控制棋盘的行每一层里for循环的col控制棋盘的列一行一列确定了放置皇后的位置。
每次都是要从新的一行的起始位置开始搜所以都是从0开始。
代码如下
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] .; // 回溯撤销皇后}
}验证棋盘是否合法 按照如下标准去重
不能同行不能同列不能同斜线 45度和135度角 代码如下
bool isValid(int row, int col, vectorstring 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;
}为什么没有在同行进行检查呢
因为在单层搜索的过程中每一层递归只会选for循环也就是同一行里的一个元素所以不用去重了。
代码实现
class Solution {
private:
vectorvectorstring result;
// n 为输入的棋盘大小
// row 是当前递归到棋盘的第几行了
void backtracking(int n, int row, vectorstring 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, vectorstring 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:vectorvectorstring solveNQueens(int n) {result.clear();std::vectorstd::string chessboard(n, std::string(n, .));backtracking(n, 0, chessboard);return result;}
};详细解析 思路视频 代码实现文章 37 解数独hard
编写一个程序通过填充空格来解决数独问题。
数独的解法需 遵循如下规则
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图 数独部分空格内已填入了数字空白格用 ‘.’ 表示。
思路回溯法二维递归
棋盘搜索问题可以使用回溯法暴力搜索只不过这次我们要做的是二维递归。
怎么做二维递归呢
N皇后问题是因为每一行每一列只放一个皇后只需要一层for循环遍历一行递归来遍历列然后一行一列确定皇后的唯一位置。
本题就不一样了本题中棋盘的每一个位置都要放一个数字而N皇后是一行只放一个皇后并检查数字是否合法解数独的树形结构要比N皇后更宽更深。
因为这个树形结构太大了抽取一部分如图所示 回溯三部曲
递归函数以及参数
递归函数的返回值需要是bool类型为什么呢因为解数独找到一个符合的条件就在树的叶子节点上立刻就返回相当于找从根节点到叶子节点一条唯一路径所以需要使用bool返回值。
代码如下
bool backtracking(vectorvectorchar board)递归终止条件
本题递归不用终止条件解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。
不用终止条件会不会死循环
递归的下一层的棋盘一定比上一层的棋盘多一个数等数填满了棋盘自然就终止填满当然好了说明找到结果了所以不需要终止条件
递归单层搜索逻辑
在树形图中可以看出我们需要的是一个二维的递归也就是两个for循环嵌套着递归
一个for循环遍历棋盘的行一个for循环遍历棋盘的列一行一列确定下来之后递归遍历这个位置放9个数字的可能性
代码如下详细看注释
bool backtracking(vectorvectorchar board) {for (int i 0; 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) { // (i, j) 这个位置放k是否合适if (isValid(i, j, k, board)) {board[i][j] k; // 放置kif (backtracking(board)) return true; // 如果找到合适一组立刻返回board[i][j] .; // 回溯撤销k}}return false; // 9个数都试完了都不行那么就返回false}}return true; // 遍历完没有返回false说明找到了合适棋盘位置了
}注意这里return false的地方这里放return false 是有讲究的。
因为如果一行一列确定下来了这里尝试了9个数都不行说明这个棋盘找不到解决数独问题的解
那么会直接返回 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去
判断棋盘是否合法
判断棋盘是否合法有如下三个维度
同行是否重复同列是否重复9宫格里是否重复 代码如下
bool isValid(int row, int col, char val, vectorvectorchar board) {for (int i 0; i 9; i) { // 判断行里是否重复if (board[row][i] val) {return false;}}for (int j 0; j 9; j) { // 判断列里是否重复if (board[j][col] val) {return false;}}int startRow (row / 3) * 3;int startCol (col / 3) * 3;for (int i startRow; i startRow 3; i) { // 判断9方格里是否重复for (int j startCol; j startCol 3; j) {if (board[i][j] val ) {return false;}}}return true;
}代码实现
class Solution {
private:
bool backtracking(vectorvectorchar board) {for (int i 0; i board.size(); i) { // 遍历行for (int j 0; j board[0].size(); j) { // 遍历列if (board[i][j] .) {for (char k 1; k 9; k) { // (i, j) 这个位置放k是否合适if (isValid(i, j, k, board)) {board[i][j] k; // 放置kif (backtracking(board)) return true; // 如果找到合适一组立刻返回board[i][j] .; // 回溯撤销k}}return false; // 9个数都试完了都不行那么就返回false}}}return true; // 遍历完没有返回false说明找到了合适棋盘位置了
}
bool isValid(int row, int col, char val, vectorvectorchar board) {for (int i 0; i 9; i) { // 判断行里是否重复if (board[row][i] val) {return false;}}for (int j 0; j 9; j) { // 判断列里是否重复if (board[j][col] val) {return false;}}int startRow (row / 3) * 3;int startCol (col / 3) * 3;for (int i startRow; i startRow 3; i) { // 判断9方格里是否重复for (int j startCol; j startCol 3; j) {if (board[i][j] val ) {return false;}}}return true;
}
public:void solveSudoku(vectorvectorchar board) {backtracking(board);}
};详细解析 思路视频 代码实现文章
