您现在的位置是:首页 >技术教程 >【代码随想录】刷题Day29网站首页技术教程

【代码随想录】刷题Day29

哈里沃克 2024-06-17 10:43:20
简介【代码随想录】刷题Day29

1.递增子序列

491. 递增子序列

本题需要注意的有三点:

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.全排列

46. 全排列

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

47. 全排列 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;
    }
};

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。