[数据结构与算法]LeetCode刷题day47

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. 有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？
3. 使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？
4. 搜索的过程中，如何遍历一个机场所对应的所有机场。

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"]]

思路分析

皇后们的约束条件：

1. 不能同行
2. 不能同列
3. 不能同斜线

确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。

下面用一个 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. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 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);
}

如果有收获！！！ 希望老铁们来个三连，点赞、收藏、转发。
创作不易，别忘点个赞，可以让更多的人看到这篇文章，顺便鼓励我写出更好的博客