代码随想录训练营Day21 | 491.递增子序列 - 46.全排列 - 47.全排列 II - 332.重新安排行程 - 51.N皇后 - 37.解数独

491.递增子序列

• 题目链接：491.递增子序列
• 思路：和子集那道题思路很像，每次在数组中选择一个数，选过的数不能选择，这里要求集合数量必须大于2个才能符合，仍然需要去重，但这里选额的是子序列，数组不能进行排序，故去重使用集合，记录当前回溯函数选择过的数，遇到选择过的数不需要再重新选择
• 代码：

class Solution {
public:vector<vector<int>> findSubsequences(vector<int>& nums) {vector<vector<int>> ans;vector<int> tmp;int n = nums.size();auto dfs = [&](auto&& dfs, int i) {if(i > n) // 终止条件return;if(tmp.size() >= 2) // 符合题目条件加入答案中ans.push_back(tmp);set<int> cnt; // 集合去重，每次回溯函数，同一个数只选择一次for(int j = i; j < n; ++j) {if(!tmp.empty() && nums[j] < tmp.back()) // 每次选择的数必须是递增的continue;if(!cnt.count(nums[j])) {tmp.push_back(nums[j]);dfs(dfs, j + 1);tmp.pop_back();cnt.insert(nums[j]);}}};dfs(dfs, 0);return ans;}
};

46.全排列

• 题目链接：46.全排列
• 思路：全排列思路仍然是每次从数组中选择一个数，选过的数不能再选，因为全排列的特殊性，排列长度和数组长度一样，故不需要额外创建数组来记录每次选择结果，每次将选择的数和当前应该选择的位置上的数交换即可
• 代码：

class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> ans;int n = nums.size();vector<int> tmp;auto dfs = [&](auto&& dfs, int i) {if(i == n) {ans.push_back(nums);  // 选择成功加入到ans中return;}for(int j = i; j < n; ++j) {swap(nums[i], nums[j]); // 选择 nums[j]，将它和nums[i] 交换dfs(dfs, i + 1);swap(nums[i], nums[j]); // 再交换回来}};dfs(dfs, 0); // 从0开始选择return ans;}
};

47.全排列 II

• 题目链接：47.全排列 II
• 思路：思路和上一题一致，这里需要去重，即相同的数，只能选择一次，去重方法和子序列那题类似，使用集合去重
• 代码：

class Solution {
public:vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> ans;int n = nums.size();vector<int> tmp;auto dfs = [&](auto&& dfs, int i) {if(i == n) {ans.push_back(nums);return;}set<int> cnt; // 集合去重for(int j = i; j < n; j++) {if(cnt.count(nums[j]) != 0) // 去重continue;swap(nums[i], nums[j]); // 交换dfs(dfs, i + 1);swap(nums[i], nums[j]); // 交换cnt.insert(nums[j]); // 选择的数加入到集合中}};dfs(dfs, 0); // 从0开始return ans;}
};

332.重新安排行程

• 题目链接：332.重新安排行程
• 思路：本题没有完整的思路，一刷感觉思路不完善，这里使用的是卡哥的代码，二刷的时候仔细思考，卡哥讲解
• 代码：

class Solution {
private:
// unordered_map<出发城市, map<到达城市, 航班次数>> targets
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 ) { // 使用int字段来记录到达城市是否使用过了result.push_back(target.first);target.second--;if (backtracking(ticketNum, result)) return true;result.pop_back();target.second++;}}return false;
}
public:vector<string> findItinerary(vector<vector<string>>& tickets) {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皇后

• 题目链接：51.N皇后
• 思路：
  1. N皇后经典题目，使用回溯算法，每次选择一个位置放入皇后，当不符合的时候回溯选择其他位置；
  2. 使用数组arr，记录每行选择的皇后的列的位置，从第0行开始回溯，每次回溯代表着选择某一行选择某一列放置皇后；
  3. 使用judge函数判断当前位置是否可以放置皇后；
  4. GetRow函数获取每行的字符串形式；
• 代码：

class Solution {
public:vector<vector<string>> solveNQueens(int n) {vector<vector<string>> ans;vector<string> row;vector<int> arr(n, 0); // 存储每一行放的皇后的列数auto judge = [&](int t) ->bool {for(int i = 0; i < t; ++i) {// 判断是否有皇后在同一列，判断皇后是否在斜线上，即横坐标距离，于纵坐标之间的距离是否相等if(arr[i] == arr[t] || abs(t - i) == abs(arr[t] - arr[i]))return false;}return true;};auto GetRow = [&](int k) -> string {  // 将某一行转换为字符串stringstream ss;for(int i = 0; i < n; ++i) {if(i == k)ss << 'Q';elsess << '.';}return ss.str();};auto dfs = [&](auto&& dfs, int i) {if(i == n) {ans.push_back(row); // 符合放入答案中return;}for(int j = 0; j < n; ++j) { // 每行选择某一列放置皇后arr[i] = j; // 第i行选择将皇后放到第 j 列， 即[i, j]的位置if(judge(i)) { // 判断皇后位置是否合法row.push_back(GetRow(j));dfs(dfs, i + 1);row.pop_back();}}};dfs(dfs, 0); // 从第0行开始，从行开始回溯，默认每次放置的皇后都不再同一行return ans;}
};

37.解数独

• 题目链接：37.解数独
• 思路：
  1. 回溯数独每一个位置，每个位置需要填写时，从1-9选择一个数；
  2. 每个数的填充需要进行判断是否符合数独的条件。
• 代码：

class Solution {
public:void solveSudoku(vector<vector<char>>& board) {int n = board.size();// 判断当前位置是否符合数独条件auto isTrue = [&] (int row, int col, char val) {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;};auto dfs = [&](auto&& dfs) -> bool {// 遍历数独	for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {if(board[i][j] != '.') continue;// 需要填充时，从1到9选择for(int k = 1; k <= 9; k++) { if(isTrue(i, j, k + '0')) { // 判断当前位置放入 k ,是否符合数独条件board[i][j] = k + '0';if(dfs(dfs))return true;board[i][j] = '.';}}return false;}}return true;};dfs(dfs);}
};