题目:491.递增子序列、46.全排列、47.全排列 II
参考链接:代码随想录
491.递增子序列
思路:一开始按照基本回溯的模板来写。当路径长度大于2时加入ans,结束条件为开始位置到达末尾。for循环部分遍历第一个加入path中的数,如果目前的数小于path末尾,则直接考虑下一个数。写完后运行发现没有去重处理,但本题的去重和上题集合2不同,不能排序,不是相邻也可能重复,比如[4,4,5,4],会产生3个[4,4],去重方法我一开始没想到。
一开始的错误代码:
class Solution {
public:
vectorvectorint>> ans;
vectorint> path;
void backtracking(vectorint>& nums,int begin){//begin为开始取的位置
if(path.size()>=2){
ans.push_back(path);
}
if(begin==nums.size()){
return;
}
for(int i=begin;inums.size()-1;i++){
if(path.size()>0&&nums[i]path.back()){//如果目前遍历的数小于path末尾,则不满足递增情况,直接考虑下一个数
continue;
}
path.push_back(nums[i]);
backtracking(nums,i+1);
path.pop_back();
}
}
vectorvectorint>> findSubsequences(vectorint>& nums) {
backtracking(nums,0);
return ans;
}
};
看了解析需要对每一层进行去重,由于重复元素不相邻,只能用集合来判断重复。不能再简单的用used数组了。时间复杂度O(n*2^n)。
标答:
class Solution {
public:
vectorvectorint>> ans;
vectorint> path;
void backtracking(vectorint>& nums,int begin){//begin为开始取的位置
if(path.size()>=2){
ans.push_back(path);
}
if(begin==nums.size()){
return;
}
unordered_setint> set;//对本层去重
for(int i=begin;inums.size()-1;i++){
if(path.size()>0&&nums[i]path.back()||set.find(nums[i])!=set.end()){
//如果目前遍历的数小于path末尾,则不满足递增情况,直接考虑下一个数。或者在同一层出现重复。
continue;
}
path.push_back(nums[i]);
set.insert(nums[i]);
backtracking(nums,i+1);
path.pop_back();//这里不需要set中移出nums[i],因为是对整层的去重
}
}
vectorvectorint>> findSubsequences(vectorint>& nums) {
backtracking(nums,0);
return ans;
}
};
注意使用set在回溯的时候不用移出元素,因为是对整层去重。set也是每一层for循环之前定义一个。
看了标答,发现由于题目说了数值范围[-100,100],因此可以使用数组做哈希表:
class Solution {
private:
vectorvectorint>> result;
vectorint> path;
void backtracking(vectorint>& nums, int startIndex) {
if (path.size() > 1) {
result.push_back(path);
}
int used[201] = {0}; // 这里使用数组来进行去重操作,题目说数值范围[-100, 100]
for (int i = startIndex; i nums.size(); i++) {
if ((!path.empty() && nums[i] path.back())
|| used[nums[i] + 100] == 1) {
continue;
}
used[nums[i] + 100] = 1; // 记录这个元素在本层用过了,本层后面不能再用了
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vectorvectorint>> findSubsequences(vectorint>& nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
};
46.全排列
思路:排列的组合的最大区别就是有顺序的考虑。比如第一个元素选的2,那么后面1和3还需要考虑,而组合就只需要考虑3了。所以在回溯模板的区别中,首先是for循环必须每次都是从0到结束,那么如何判断那些元素可以选呢?我们继续采用used数组,当for遍历的元素已经用过,则直接continue,否则加入路径。当路径长度为数组长度时将路径添加到ans。时间复杂度O(n*n!),注意这个时间复杂度就是所有排列方式的数量A(n,n)乘以生成每一个答案需要的n次push_back。
class Solution {
public:
vectorvectorint>> ans;
vectorint> path;
void backtracking(vectorint>& nums,vectorint>& used){
if(path.size()==nums.size()){
ans.push_back(path);
return;
}
for(int i=0;inums.size();i++){//每次都要全部遍历
if(used[i]==1){
continue;
}
path.push_back(nums[i]);
used[i]=1;
backtracking(nums服务器托管网,used);
path.pop_back();
used[i]=0;
}
}
vectorvectorint>> permute(vectorint>& nums) {
vectorint> used(nums.size(),0);
backtracking(nums,used);
return ans;
}
};
47.全排列 II
思路:一开始想的就是在上题基础上加一个每层去重,由于排列每次for都要遍历所有元素,不是相邻情况,故每层使用了一个set去重。
class Solution {
public:
vectorvectorint>> ans;
vectorint> path;
void backtracking(vectorint>& nums,vectorint>& used){
if(path.size()==nums.size()){
ans.push_back(path);
}
unordered_setint> set;
for(int i=0;inums.size();i++){//每一层去重,这里不是相邻重复情况使用set
if(used[i]==1||set.find(nums[i])!=set.end()){
continue;
}
path.push_back(nums[i]);
used[i]=1;
set.insert(nums[i]);
backtracking(nums,used);
path.pop_back();
used[i]=0;
}
}
vectorvectorint>> permuteUnique(vectorint>& nums) {
vectorint> used(nums.size(),0);
backtracking(nums,used);
return ans;
}
};
看完标答,发现可以先排序,然后只用一个used就可以完成所有功能。判断相邻方法和之前的组合一样。时间复杂度O(n*n!)。
class Solution {
public:
vectorvectorint>> ans;
vectorint> path;
void backtracking(vectorint>& nums,vectorint>& used){
if(path.size()==nums.size()){
ans.push_back(path);
}
for(int i=0;inums.size();i++){
if(used[i]==1||i>0&&nums[i]==nums[i-1]&&used[i-1]==0){
continue;
}
path.push_back(nums[i]);
used[i]=1;
backtracking(nums,used);
path.pop_back();
used[i]=0;
}
}
vectorvectorint>> permuteUnique(vectorint>& nums) {
sort(nums.begin(),nums.end());
vectorint> used(nums.size(),0);
backtracking(nums,used);
return ans;
}
};
对于回溯算法的时间复杂度,可以直接看这里。
服务器托管,北京服务器托服务器托管网管,服务器租用 http://www.fwqtg.net
相关推荐: 结合Next项目实际认识webpack.splitChunks
本文的目的在于简单的介绍webpack的优化功能配置:splitChunks。 webpack5出于“开箱即用”的目的,将大部分曾经要使用插件的功能集成到了config配置中,因此用户只需要了解如何配置,即可达到优化目的,其中最常使用接触的配置是:webpac…