332.重新安排行程
题目描述
给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
示例 1：
输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] 输出：["JFK","MUC","LHR","SFO","SJC"]
示例 2：
输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] 输出：["JFK","ATL","JFK","SFO","ATL","SFO"] 解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。
思路分析
这道题目的几个难点：
- 一个行程中，如果航班处理不好容易变成一个圈，成为死循环
- 有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？
- 使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？
- 搜索的过程中，如何遍历一个机场所对应的所有机场。
1、如何理解死循环
从例子可以看出 ,出发机场和到达机场也会重复的，如果在解题的过程中没有对集合元素处理好，就会死循环
2、该记录映射关系
有多种解法，字母序靠前排在前面，如何该记录映射关系呢 ？
一个机场映射多个机场，机场之间要靠字母序排列。一个机场映射多个机场，可以使用std::unordered_map，如果让多个机场之间再有顺序的话，就是用std::map或者std::multimap 或者 std::multiset。
这样存放映射关系可以定义为 unordered_map<string, multiset<string>> targets 或者 unordered_map<string, map<string, int>> targets。
含义如下：
unordered_map<string, multiset> targets：unordered_map<出发机场, 到达机场的集合> targets
unordered_map<string, map<string, int>> targets：unordered_map<出发机场, map<到达机场, 航班次数>> targets
这两个结构，我选择了后者，因为如果使用unordered_map<string, multiset<string>> targets 遍历multiset的时候，不能删除元素，一旦删除元素，迭代器就失效了。
再说一下为什么一定要增删元素呢，正如前面图中所示，出发机场和到达机场是会重复的，搜索的过程没及时删除目的机场就会死循环。
所以搜索的过程中就是要不断的删multiset里的元素，那么推荐使用unordered_map<string, map<string, int>> targets。
在遍历 unordered_map<出发机场, map<到达机场, 航班次数>> targets的过程中，可以使用"航班次数"这个字段的数字做相应的增减，来标记到达机场是否使用过了。
如果“航班次数”大于零，说明目的地还可以飞，如果如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。
相当于说我不删，我就做一个标记！
算法设计
以 [[“JFK”, “KUL”], [“JFK”, “NRT”], [“NRT”, “JFK”]为例，抽象为树形结构如下：
回溯三部曲
- 递归参数和返回值
递归参数:航班的映射关系 unordered_map<string, multiset<string>> targets我们定义成全局变量(控制参数的个数), 还需要ticketNum表示一共有多少个航班(用于结束条件),还需要一个vector<string> 记录结果.
返回值:我们需要找到一个航程,就是在树形结构中找一条通往叶子节点的路线.所以我们只需要找到就直接返回就可以了,也不用继续往下寻找了.
**备注:**本回溯函数中的参数都可作为全局变量.
- 递归结束条件
根据观察得知,如果最终的行程里的机场个数要比航线列表中的航班数量+1.我们就找到了一个形成,就把所有的航班串到一起了,递归结束.
if (result.size() == ticketNum + 1) { return true; }
- 单层递归逻辑
遍历所有以当前出发点开始的航线,先判断当前的航线是否还有多余的了,如果有则加入结果集.然后开始以新的出发点继续飞. 如果没有,继续寻找下一条.
for (pair<const 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_map<出发机场,map<到达机场,航班次数>> //unordered_map<出发机场,map<到达机场,航班次数>> unordered_map<string,map<string,int>> targets; bool backtracking(int ticketNum,vector<string>& result){ if(result.size() == ticketNum+1){ return true; } for(pair<const string,int>& target: targets[result[result.size()-1]]){ if(target.second>0){//>0说明还有可以起飞的飞机 result.push_back(target.first); target.second--; if(backtracking(ticketNum,result)){//如果最后找到了,则返回true. return true; } //如果没找到,则进行回溯,尝试其他方案 result.pop_back(); target.second++; } } return false;//遍历完所有的航班记录还没找到就返回false } vector<string> findItinerary(vector<vector<string>>& tickets) { targets.clear(); vector<string> result; for(const vector<string>&vec : tickets){ targets[vec[0]][vec[1]]++;//记录航班映射关系 } result.push_back("JFK") ; backtracking(tickets.size(),result); return result; }
51. N皇后
题目描述
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1 输出：[["Q"]]
思路分析
皇后们的约束条件：
- 不能同行
- 不能同列
- 不能同斜线
确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。
下面用一个 3 * 3 的棋盘，将搜索过程抽象为一棵树，如图：
可以看出，二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。
那么我们用皇后们的约束条件，来回溯搜索这棵树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。
回溯三部曲
- 确定参数和返回值
参数:当前进行到棋盘的行数row,棋盘规模n,以及整个棋盘vector<string> &chessboard
返回值:当我们把所有的棋子摆完,也就是把棋盘遍历一遍,则就结束,把棋盘加入结果集即可.因为结果有多个,所以并不需要返回值.
- 确定递归结束条件
当进行的row和棋盘的规模相等,则递归结束
- 确定单层递归逻辑
判断当前位置是否可以放置,如果可以则放棋子.然后递归进入下一行.递归回来进行回溯尝试其他情况.
参考代码
#include<bits/stdc++.h> using namespace std; vector<vector<string>> result;//最终结果集 void backtracking(int row,int n,vector<string> &chessboard){//row:进行到第row行 n:棋盘大小 if(row==n) { result.push_back(chessboard); return; } for(int col = 0;col < n; col++){ if(!isValid(row,col,n,chessboard)){ continue; } chessboard[row][col] = 'Q'; backtracking(row+1,n,chessboard); chessboard[row][col] = '.'; } } bool isValid(int row,int col,int n,vector<string> &chessboard){//row:行 col:列 n:棋盘大小 //45°是否重复 int i,j; i = row-1; j = col - 1; while(i>=0&&j>=0){ if(chessboard[i][j]=='Q'){ return false; } i--; j--; } //同一列是否重复 i = row-1; while(i>=0){ if(chessboard[i][col]=='Q'){ return false; } i--; } //135°是否重复 i = row - 1; j = col +1; while(i>=0 && j <=n){ if(chessboard[i][j]=='Q'){ return false; } i--; j++; } return true;//没有重复 } //chessboard因为每次要进行初始化,所以建议作为函数参数 ,引用传入. vector<vector<string>> solveNQueens(int n) { result.clear(); vector<string> chessboard(n,string(n,'.')); //单一棋盘 初始化 backtracking(0,n,chessboard); return result; }
37. 解数独
题目描述
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例：
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] 输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
思路分析
N皇后问题 是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来来遍历列，然后一行一列确定皇后的唯一位置。
本题就不一样了，本题中棋盘的每一个位置都要放一个数字，并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。
因为这个树形结构太大了，我抽取一部分，如图所示：
回溯三部曲
- 确定参数和返回值
参数:由于数独的行列已知,所以参数只需要传入九宫格vector<vector<char>>& board即可.
返回值:由于答案只有一种,找到了就直接返回,没找到就尝试下一种情况,所以返回值是bool类型.
- 确定递归结束条件
递归的话只要把数字填满就返回true,然后递归逐渐跳出并结束.
- 确定单层递归逻辑
由于每一行需要填充多个数,也需要填充多个列,所以需要双层循环.如果当前位置需要填充,就先判断要填充的数是否合法(同行,同列,九宫格都不重复),如果合法就尝试下一个位置,不合法就尝试下一个数字.
参考代码
#include<bits/stdc++.h> using namespace std; bool backtracking(vector<vector<char>>& 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++) { if(isValid(i,j,k,board)) { board[i][j] = k; if(backtracking(board)) { //如果找到合适的,直接进行返回 return true; } board[i][j] = '.'; //回溯 } } return false;//如果'1'-'9'试过了还没找到,则返回false. } } return true;//遍历完没有返回false,说明找到了合适棋盘,继续向上返回. } bool isValid(int row,int col,char val,vector<vector<char>>& board) { //因为是9*9的所有并不需要规模参数: n //是否行重复 for(int i = 0; i <9; i++) { if(board[row][i]==val) { return false; } } //是否列重复 for(int i = 0; i < 9; i++) { if(board[i][col]==val) { return false; } } //是否九宫格重复 int startX = (row / 3) * 3;//九宫格起始下标 int startY = (col / 3) * 3; for(int i = startX; i < startX+3; i++) { for(int j = startY; j < startY+3; j++) { if(board[i][j]==val) { return false; } } } return true;//不重复 } void solveSudoku(vector<vector<char>>& board) { backtracking(board); }
