详细布置
491.递增子序列
本题和大家刚做过的 90.子集II 非常像,但又很不一样,很容易掉坑里。
https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html
视频讲解:https://www.bilibili.com/video/BV1EG4y1h78v
Tips:有以下几点要注意:
1. 递增的元素可以不相邻。
2. 为了去重,要在一层内限制相等的元素被使用多次,因此定义一个unordered_set来记录使用过哪些元素。
我的题解:
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int pos){
if(pos == nums.size()){
return;
}
// 用这个set来记录用过哪些元素
unordered_set<int> uset;
for(int i = pos; i<nums.size();i++){
if( (path.size() == 0 || nums[i] >= path[path.size() - 1]) && uset.find(nums[i])==uset.end()){
path.push_back(nums[i]);
uset.insert(nums[i]);
if(path.size()>=2){
result.push_back(path);
}
backtracking(nums,i+1);
path.pop_back();
}
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums, 0);
return result;
}
};
46.全排列
本题重点感受一下,排列问题 与 组合问题,组合总和,子集问题的区别。 为什么排列问题不用 startIndex
https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html
视频讲解:https://www.bilibili.com/video/BV19v4y1S79W
Tips:这道题就是定义一个used数组,来标记在当前树的纵向方向上有哪些元素已被使用过。同时每层都是从0开始搜索而不是startIndex。
如果数组a不能在声明的时候初始化,可以先定义再初始化:
vector<int> a;
a=vector<int>(nums.begin(), nums.end());
我的题解:
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
vector<bool> used;
void backtracking(vector<int>& nums){
if(path.size() == nums.size()){
result.push_back(path);
return;
}
for(int i = 0; i< nums.size(); i++){
if(used[i]){
continue;
}
used[i] = true;
path.push_back(nums[i]);
backtracking(nums);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
used = vector<bool>(nums.size(),false);
backtracking(nums);
return result;
}
};
47.全排列 II
本题 就是我们讲过的 40.组合总和II 去重逻辑 和 46.全排列 的结合,可以先自己做一下,然后重点看一下 文章中 我讲的拓展内容。 used[i - 1] == true 也行,used[i - 1] == false 也行
https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html
视频讲解:https://www.bilibili.com/video/BV1R84y1i7Tm
Tips:
解法1就是需要在上一道题的基础上进行同层的去重,因此使用了一个set来记录哪些元素已经被使用过。
解法2更加精炼一些,没有使用到set
我的题解:
解法1:
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
vector<bool> used;
void backtracking(vector<int>& nums){
if(path.size()==nums.size()){
result.push_back(path);
return;
}
// vector<bool> layerUsed = vector<bool>(nums.size(),false);
unordered_set<int> uset;
for(int i = 0; i<nums.size(); i++){
if(uset.find(nums[i])!=uset.end()||used[i]){
continue;
}
used[i] = true;
uset.insert(nums[i]);
path.push_back(nums[i]);
backtracking(nums);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
used = vector<bool>(nums.size(), false);
// sort(nums.begin(),nums.end());
backtracking(nums);
return result;
}
};
解法2:
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
vector<bool> used;
void backtracking(vector<int>& nums){
if(path.size()==nums.size()){
result.push_back(path);
return;
}
for(int i = 0; i<nums.size(); i++){
if(i > 0 && nums[i] == nums[i-1] && used[i - 1] == false){
continue;
}
if(used[i] == false){
used[i] = true;
path.push_back(nums[i]);
backtracking(nums);
path.pop_back();
used[i] = false;
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
used = vector<bool>(nums.size(), false);
sort(nums.begin(),nums.end());
backtracking(nums);
return result;
}
};
标签:排列,nums,46,47,used,vector,result,path,size
From: https://www.cnblogs.com/GavinGYM/p/17090422.html