代码随想录算法训练营第十三天|n皇后&数独老经典了-创新互联
链接：https://leetcode.cn/problems/subsets-ii/
那么这道题和上一道题有什么区别呢？
没什么区别，就是仅仅多了重复元素而已，那怎么搞？
实际上[1,4,4]和[4,1,4]是同一个子集，所以就还要去重
不急，在递归的下面加上这句话
while(i+1< nums.size() && vec[vec.size()-1] == nums[i+1]在pop元素之前，如果我们发现要pop的元素和下一个push进来的元素一毛一样，那么我们就让i++
class Solution {public:
vector>ans;
vectorvec;
void recursion(vector& nums,int k,int step)
{// 元素收集满了，记录当前vec然后return
if(vec.size() == k)
{ans.push_back(vec);
return;
}
for(int i = step;ivec.push_back(nums[i]);
recursion(nums,k,i + 1); // 是取搜下一个元素了
while(i+1< nums.size() && vec[vec.size()-1] == nums[i+1]) i++; // 那么就跳过重复的数据呗
vec.pop_back();
}
}
vector>subsetsWithDup(vector& nums)
{sort(nums.begin(),nums.end());
for(int i = 1; i< nums.size() ;i++)
{vec.clear();
recursion(nums,i,0);
}
//vector>res (ans.begin(),ans.end());
ans.push_back({});
ans.push_back(nums);
return ans;
}
}; 链接：https://leetcode.cn/problems/increasing-subsequences/description/
注意，这个题目比较特别
因为要求输出递增序列，因此是不可以排序的，而我们之前推崇的办法
while(i + 1< nums.size() && nums[i+1] == vec[vec.size()-1]) i++;也仅仅在排好序的数组上管用
所以我们需要重新思考去重的方式——set
同时因为题目要求递增，所以需要在push之前判断当前元素是不是比vector中的最后一个元素大
class Solution {public:
set>ans;
vectorvec;
void recursion(vector& nums,int k,int step)
{if(vec.size() == k)
{ans.insert(vec);
return;
}
for(int i=step;iif(!vec.empty() && nums[i] >= vec[vec.size()-1] || vec.empty()) // 如果满足递增，再把元素给push进来
{vec.push_back(nums[i]);
recursion(nums,k,i + 1);
//while(i + 1< nums.size() && nums[i+1] == vec[vec.size()-1]) i++; // 不能排序这个办法基本上就死了，所以需要set
vec.pop_back();
}
}
}
vector>findSubsequences(vector& nums) {//sort(nums.begin(),nums.end()); // 注意这个题目是不允许排序的
for(int i=2;i<=nums.size();i++)
{vec.clear();
recursion(nums,i,0);
}
vector>res(ans.begin(),ans.end());
return res;
}
}; 链接：https://leetcode.cn/problems/permutations/
确实是需要used数组了，记录当前哪些元素用过哪些元素没有用过
值得注意的一点是：used中的索引值需要是当前元素在nums中的索引而不能是当前元素的值，因为当前元素可能是负值···
class Solution {public:
// 想返回全排列最好的办法就是用数组记重了
vector>res;
vectorvec;
int used[100];
void recurison(vector& nums)
{if(vec.size() == nums.size())
{res.push_back(vec);
return;
}
for(int i = 0;iif(!used[i]) // 最好是记录索引而不是值，因为值有可能是负的
{vec.push_back(nums[i]);
used[i] = 1;
recurison(nums);
used[i] = 0;
vec.pop_back();
}
}
}
vector>permute(vector& nums) {recurison(nums);
return res;
}
}; 链接：https://leetcode.cn/problems/permutations-ii/
加个set去重咯，没有新意~
class Solution {public:
set>ans;
vectorvec;
int used[100];
void recurison(vector& nums)
{if(vec.size() == nums.size())
{ans.insert(vec);
return;
}
for(int i = 0;iif(!used[i]) // 最好是记录索引而不是值，因为值有可能是负的
{vec.push_back(nums[i]);
used[i] = 1;
recurison(nums);
used[i] = 0;
vec.pop_back();
}
}
}
vector>permuteUnique(vector& nums) {recurison(nums);
vector>res(ans.begin(),ans.end());
return res;
}
}; 链接：https://leetcode.cn/problems/reconstruct-itinerary/
孙哥讲的真很好，很细
class Solution {unordered_map>targets;
bool backtracking(int ticketNum, vector& result) {if (result.size() == ticketNum + 1) {return true;
}
for (pair& 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:
vectorfindItinerary(vector>& tickets)
{targets.clear();
vectorresult;
for (const vector& vec : tickets)
{targets[vec[0]][vec[1]]++; // 记录映射关系
}
result.push_back("JFK"); // 起始机场
backtracking(tickets.size(), result);
return result;
}
}; 链接：https://leetcode.cn/problems/n-queens/
经典练手题
// 区区n皇后是困难？？？
class Solution {public:
vector>res;
// 首先我们枚举行，从左到右，看行上的哪个元素可以放置Q
bool check(int n,int row,int column,vector&test)
{// [row,column]
// 若是在row这行有元素，我们就直接return false
for(int i=0;iif(test[i][column] == 'Q') return false;
if(row - i >= 0 && column + iif(test[row - i][column + i] == 'Q') return false;}
if(row - i >= 0 && column - i >=0) {if(test[row - i][column - i] == 'Q') return false;}
}
return true;c
}
void recursion(int n,int step,vector&test) // 直接修改test数组
{// 如果当前枚举的行数已经超过了n，那么我们直接就记录当前答案然后return
if(step >n-1)
{res.push_back(test);
return;
}
for(int i=0;iif(check(n,step,i,test)) // 如果当前位置是合法的
{test[step][i] = 'Q';
recursion(n,step + 1,test);
test[step][i] = '.';
}
}
}
vector>solveNQueens(int n) // 此处的n给的是棋盘的大小
{// 首先需要初始化数组，答案是用三维数组装填的
vectortest(n , string(n,'.')); // 刚开始我们将数组全部都用'.'装填之
recursion(n,0,test);
return res;
}
}; 经典练手题2，主要看细不细
首先我们考虑如何递归的问题：按理说是9*9的方格逐个位置搜索，那用for循环枚举位置不是有点多余？因为移动挺有规律的，所以我们这里就没有用两层for循环去枚举位置（加上枚举数字就有三层循环了），我们只要枚举当前位置需要填入的值就OK了
至于行数和列数，一般都是递归到当前行的下一列，只有当前行所有列全都遍历完毕才会去下一行，根据这个规律就能得到下一次递归的位置在哪
还有一个需要注意的点：数独数组本来就是有值的，并且我们在填充数独的过程中是不可以改变原来数独中的值的，因此我们在递归的过程中发现当前位置若是有值，就直接递归到下一层。并且，从此处回溯是不合理的，所以在递归操作的后面直接加上return避免此处回溯进入到后面的for循环，同时也提高了效率
除此之外，我设计了一个check函数，用来判断在当前位置填入num是否合法——还是为了提高效率，开始的时候我们就得到了不完全的数独数组，为了避免重复值出现在“同一行”，“同一列”，“同一个3 * 3矩阵”中，我们还要定义三个数组用来记录“当前行”，“当前列”，“当前的3 * 3矩阵中哪些数字被使用过
最后还有一个需要注意的点：数独填充完毕后是要return的，但是真的return回来所有被填充的数字又会变成’.'，所以在填充完毕后，我们定义标志位flag为1，并且在回溯的时候加上判断——只有在标志位不为1的时候才回溯，这样我们return回来的数组就是完整的
class Solution {public:
int rows[10][10];
int cols[10][10];
int cell[10][10][10];
int flag = 0;
// 首先先遍历一遍数独，将其中都是1的位置全都置为1，表示这个元素已经被使用过了
bool check(int row, int col, vector>& board, int num)
{// 若是行中列中包括cell中都没有出现过这个元素，那么return true
if (rows[row][num]) return false;
if (cols[col][num]) return false;
if (cell[row/3][col/3][num]) return false;
return true;
}
void recursion(vector>& board, int row, int col)
{if (flag) return;
if (col == 9) {col = 0; row += 1; }
if (row == 9 && col == 0) // 已经将数组填充完毕
{flag = 1;
return;
}
if (board[row][col]!='.') {recursion(board, row, col + 1); return; } // 如果当前有元素，直接跳过，并且不允许回溯，直接return
// 你觉得需要用for循环枚举位置吗，是不是所有顺序都是固定的
for (int num = 1; num<= 9; num++) // num是当前准备填充的元素
{if (check(row, col, board, num))
{ board[row][col] = num + '0';
rows[row][num] = 1; // 第row行的num已经用过了
cols[col][num] = 1; // 第col列的num已经用过了
cell[row/3][col/3][num] = 1;
recursion(board, row, col + 1);
if (flag) return;
board[row][col] = '.';
rows[row][num] = 0; // 第row行的num没用过
cols[col][num] = 0; // 第col列的num没用过
cell[row/3][col/3][num] = 0;
}
}
}
void solveSudoku(vector>& board)
{memset(rows, 0, sizeof(rows));
memset(cols, 0, sizeof(cols));
memset(cell, 0, sizeof(cell));
for (int i = 0; i<9; i++)
for (int j = 0; j<9; j++)
{ if (board[i][j] != '.')
{ int num = board[i][j] - '0';
rows[i][num] = 1; // 第i行的num已经用过了
cols[j][num] = 1; // 第j列的num已经用过了;
cell[i/3][j/3][num] = 1;
}
}
recursion(board, 0, 0);
}
}; 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网站标题：代码随想录算法训练营第十三天|n皇后&数独老经典了-创新互联
文章转载：http://6mz.cn/article/jjede.html