代码随想录算法训练营Day29|491.递增子序列、46.全排列、47.全排列 II

目录

491.递增子序列

前言

算法实现

优化

46.全排列

前言

算法实现

47.全排列 II

?前言

算法实现

总结

---

491.递增子序列

题目链接

文章链接

前言

? ? ? ? ?本题初看与上一题子集II类似，但实际上只是表面相像，在子集II中我们是通过排序，再加一个标记数组来达到去重的目的。而本题求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了。所以不能使用之前的去重逻辑！

算法实现

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex){
        // 递增子序列长度至少为2
        if (path.size() >= 2){
            result.push_back(path);
        }
        if (startIndex >= nums.size()){
            return;
        }
        unordered_set<int> uset;
        for (int i = startIndex; i < nums.size(); i++){
            if ((!path.empty() && nums[i] < path.back()) || uset.find(nums[i]) != uset.end()){
                continue;
            }
            path.push_back(nums[i]);
            uset.insert(nums[i]); //记录这个元素在本层使用过了，本层后面不能再使用了
            backtracking(nums, i + 1);
            path.pop_back();
    }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
    
};

? ? ? ? 该算法在for循环中，递归函数上面有uset.insert(nums[i]);，下面却没有与之对应的pop操作，是因为定义的unordered_set<int> uset;是记录本层元素是否使用，新的一层uset都会重新定义，所以uset只负责本层。

优化

? ? ? ? 通过将定义unordered_set<int>来记录本层元素是否使用，改为用数组做哈希，能极大提高运行效率。

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex){
        if (path.size() >= 2){
            result.push_back(path);
        }
        if (startIndex >= nums.size()){
            return;
        }
        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;
            }
            path.push_back(nums[i]);
            used[nums[i] + 100] = 1;
            backtracking(nums, i + 1);
            path.pop_back();
    }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
    
};

? ? ? ? 如果数值范围小的话能用数组尽量用数组。

46.全排列

题目链接

文章链接

前言

? ? ? ? ?排列问题与组合问题的区别是排列是有序的，在处理排列问题的时候不再使用startIndex，但是需要一个used数组标记已经选择的元素。

算法实现

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, vector<bool> used){
        if (path.size() == nums.size()){
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++){
            if (used[i] == true) continue;
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, used);
            used[i] = false;
            path.pop_back();
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

47.全排列 II

题目链接

文章链接

?前言

? ? ? ? 本题与上一题的区别在于给定一个可包含重复数字的序列，要返回所有不重复的全排列。因此又涉及到了去重问题。关于去重问题，可以参考组合总和II以及子集II，我们分别详细讲解了组合问题和子集问题如何去重。

? ? ? ? 对于排列问题，去重也是一样的思路，不过还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。

算法实现

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, vector<bool> used){
        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] == true){
                continue;
            }
                path.push_back(nums[i]);
                used[i] = true;
                backtracking(nums, used);
                used[i] = false;
                path.pop_back();            
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end()); // 利用used数组去重要记得排序
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

总结

? ? ? ? 今天接触了排列问题，本质上与组合问题类似，只是每一次遍历要从头开始并且利用used数组不再取当前遍历的值。