您现在的位置是:首页 >技术教程 >【代码随想录】刷题Day29网站首页技术教程
【代码随想录】刷题Day29
简介【代码随想录】刷题Day29
1.递增子序列
本题需要注意的有三点:
1.插入到ret的数组大小至少等于2,所以需要在插入前判断是否大于1
2.符合的数组为,一个数要大于或者等于前一个数或者整个数组是空的
3.由于每层都有可能出现同样的元素,那么前一次出现的元素结果一定包含了后续相同数的结果,不同于子集II那一题,我们不能进行排序,因为题目条件就已经限制了。那么我们需要在每层设置一个哈希表,使得我们在一层中,遍历不同的数碰到已经存在的数时,我们可以直接跳过本次的回溯
class Solution {
public:
void _findSubsequencesR(vector<vector<int>>& ret,vector<int>& tmp,vector<int>& nums,int statr)
{
if(tmp.size()>=2)
ret.push_back(tmp);
unordered_set<int> uset; // 使用set对本层元素进行去重
for(int i=statr;i<nums.size();i++)
{
if ((!tmp.empty() && nums[i] < tmp.back()) || uset.find(nums[i]) != uset.end())
continue;
uset.insert(nums[i]); // 记录这个元素在本层用过了,本层后面不能再用了
tmp.push_back(nums[i]);
_findSubsequencesR(ret,tmp,nums,i+1);
tmp.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<vector<int>> ret;
vector<int> tmp;
_findSubsequencesR(ret,tmp,nums,0);
return ret;
}
};
2.全排列
1.区别于组合,全排列传入的参数不是start而是一个数组,用于查看某一位置的元素是否已经被push到tmp中。
2.由于全排列是将所有情况都录用,那么循环的条件就是从0开始,使得nums的所有元素都要在每一层中遍历一次
class Solution {
public:
void _permuteR(vector<vector<int>>& ret,vector<int>& tmp,vector<int>& nums,vector<int>& map)
{
if(tmp.size()==nums.size())
{
ret.push_back(tmp);
return;
}
for(int i=0;i<nums.size();i++)
{
if(map[i]==1)
continue;
tmp.push_back(nums[i]);
map[i]=1;
_permuteR(ret,tmp,nums,map);
tmp.pop_back();
map[i]=0;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ret;
vector<int> tmp;
vector<int> map;
map.resize(nums.size(),0);
_permuteR(ret,tmp,nums,map);
return ret;
}
};
3.全排列 II
只需要将一层中,相同元素的结果剔除即可,那么使用哈希表就能实现查重功能。
class Solution {
public:
void _permuteUniqueR(vector<vector<int>>& ret,vector<int>& tmp,vector<int>& nums,vector<int>& map)
{
if(tmp.size()==nums.size())
{
ret.push_back(tmp);
return;
}
unordered_set<int> uset; // 使用set对本层元素进行去重
for(int i=0;i<nums.size();i++)
{
if(map[i]==1||uset.find(nums[i]) != uset.end())
continue;
uset.insert(nums[i]);
tmp.push_back(nums[i]);
map[i]=1;
_permuteUniqueR(ret,tmp,nums,map);
tmp.pop_back();
map[i]=0;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ret;
vector<int> tmp;
vector<int> map;
map.resize(nums.size(),0);
_permuteUniqueR(ret,tmp,nums,map);
return ret;
}
};
排序再进行查重空间消耗少。
注意的地方是:
1.map[i]==1,说明数已经插入
2.i>0说明是第二个以后的数,nums[i]==nums[i-1]说明两数相同,map[i-1]==0说明不是上一层的数,而是这一层重复的数,需要减枝。map[i-1]==1,说明是上层的数与下层的数相同,不需要减枝,因为这也是一种结果。
class Solution {
public:
void _permuteUniqueR(vector<vector<int>>& ret,vector<int>& tmp,vector<int>& nums,vector<int>& map)
{
if(tmp.size()==nums.size())
{
ret.push_back(tmp);
return;
}
for(int i=0;i<nums.size();i++)
{
if(map[i]==1||(i>0&&nums[i]==nums[i-1]&&map[i-1]==0))
continue;
tmp.push_back(nums[i]);
map[i]=1;
_permuteUniqueR(ret,tmp,nums,map);
tmp.pop_back();
map[i]=0;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ret;
vector<int> tmp;
vector<int> map;
sort(nums.begin(),nums.end());
map.resize(nums.size(),0);
_permuteUniqueR(ret,tmp,nums,map);
return ret;
}
};
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。