个人网站设计教程,网站推广方式措施,丹阳市房产信息网,世界杯竞猜491.递增子序列
题目链接#xff1a;491.递增子序列思路#xff1a;和子集那道题思路很像#xff0c;每次在数组中选择一个数#xff0c;选过的数不能选择#xff0c;这里要求集合数量必须大于2个才能符合#xff0c;仍然需要去重#xff0c;但这里选额的是子序列…491.递增子序列
题目链接491.递增子序列思路和子集那道题思路很像每次在数组中选择一个数选过的数不能选择这里要求集合数量必须大于2个才能符合仍然需要去重但这里选额的是子序列数组不能进行排序故去重使用集合记录当前回溯函数选择过的数遇到选择过的数不需要再重新选择代码
class Solution {
public:vectorvectorint findSubsequences(vectorint nums) {vectorvectorint ans;vectorint tmp;int n nums.size();auto dfs [](auto dfs, int i) {if(i n) // 终止条件return;if(tmp.size() 2) // 符合题目条件加入答案中ans.push_back(tmp);setint 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:vectorvectorint permute(vectorint nums) {vectorvectorint ans;int n nums.size();vectorint 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:vectorvectorint permuteUnique(vectorint nums) {vectorvectorint ans;int n nums.size();vectorint tmp;auto dfs [](auto dfs, int i) {if(i n) {ans.push_back(nums);return;}setint 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_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 ) { // 使用int字段来记录到达城市是否使用过了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) {vectorstring result;for (const vectorstring vec : tickets) {targets[vec[0]][vec[1]]; // 记录映射关系}result.push_back(JFK);backtracking(tickets.size(), result);return result;}
};51.N皇后
题目链接51.N皇后思路 N皇后经典题目使用回溯算法每次选择一个位置放入皇后当不符合的时候回溯选择其他位置使用数组arr记录每行选择的皇后的列的位置从第0行开始回溯每次回溯代表着选择某一行选择某一列放置皇后使用judge函数判断当前位置是否可以放置皇后GetRow函数获取每行的字符串形式 代码
class Solution {
public:vectorvectorstring solveNQueens(int n) {vectorvectorstring ans;vectorstring row;vectorint 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-9选择一个数每个数的填充需要进行判断是否符合数独的条件。 代码
class Solution {
public:void solveSudoku(vectorvectorchar 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);}
};
