首页 > 其他分享 >DAY30||491.非递减子序列 |46.全排列 |47.全排列Ⅱ

DAY30||491.非递减子序列 |46.全排列 |47.全排列Ⅱ

时间:2024-10-13 15:46:15浏览次数:19  
标签:排列 nums 46 47 used vector result path

491.非递减子序列

题目:491. 非递减子序列 - 力扣(LeetCode)

给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。

示例:

  • 输入: [4, 6, 7, 7]
  • 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

说明:

  • 给定数组的长度不会超过15。
  • 数组中的整数范围是 [-100,100]。
  • 给定数组中可能包含重复数字,相等的数字应该被视为递增的一种情况。

去重逻辑是1.本层重复元素不使用,纵向的树枝可以使用重复元素,但和path末尾相比要去掉非递增的元素。(这些在单层搜索逻辑里去重,终止条件只要取所有节点即可)

 本题可以用set去重,(只记录本层重复使用的元素)。x写个上题(使用used去重)不一样的写法先。。优化可以用数组做哈希表。

 代码

class Solution {
    private:
    vector<vector<int>>result;
    vector<int>path;
    void backtraking(vector<int>&nums,int startindex)
    {
        if(path.size()>1)result.push_back(path);
        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())//1.去掉树枝里不递增的元素2.去掉本层使用过的元素
            continue;

            path.push_back(nums[i]);
            uset.insert(nums[i]);//记录本层使用过的元素
            backtraking(nums,i+1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtraking(nums,0);
        return result;
    }
};

46.全排列

题目:46. 全排列 - 力扣(LeetCode)

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

示例:

  • 输入: [1,2,3]
  • 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

 集合有多长树就有多深,和组合问题的区别就是startindex的使用,这个的使用保证了求出的是组合。本题不需要,递归里,取完一个数,就取剩下的两个数,使用used数组记录使用过的元素。

终止条件是到达和数组同样长度即找到了一个全排列。。

代码 

class Solution {
public:
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();//回溯
        }

    }
    vector<vector<int>> permute(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool>used(nums.size(),false);
        backtracking(nums,used);
        return result;

    }
};

47.全排列Ⅱ

题目:47. 全排列 II - 力扣(LeetCode)

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

示例 1:

  • 输入:nums = [1,1,2]
  • 输出: [[1,1,2], [1,2,1], [2,1,1]]

示例 2:

  • 输入:nums = [1,2,3]
  • 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示:

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

思路:本题结合了全排列Ⅰ和组合总和Ⅱ里面的去重逻辑(使用used,且这个去重一定要先对数组进行排列)。

 代码

class Solution {
public:
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++)
        {
            // used[i - 1] == true,说明同一树枝nums[i - 1]使用过
            // used[i - 1] == false,说明同一树层nums[i - 1]使用过
            // 如果同一树层nums[i - 1]使用过则直接跳过
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false)continue;//这里是组合去重

            if(used[i]==false)//只有纵向递归里,没使用过的元素才取(这里是排列去重)
            {
                 path.push_back(nums[i]);
            used[i]=true;
            backtracking(nums,used);
            used[i]=false;
            path.pop_back();//回溯

            }
           
        }

    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(),nums.end());//树层去重需要对数组排序
        vector<bool>used(nums.size(),false);
        backtracking(nums,used);
        return result;

    }
};

可以感受出排列问题的不同:

  • 每层都是从0开始搜索而不是startIndex
  • 需要used数组记录path里都放了哪些元素了

 一般说道回溯算法的复杂度,都说是指数级别的时间复杂度。

 切记两个去重逻辑的不同。。。

还要三道比较难的题目,这里一刷没有什么时间就先跳过了,只看了解题思路

332. 重新安排行程 - 力扣(LeetCode)

51. N 皇后 - 力扣(LeetCode)

37. 解数独 - 力扣(LeetCode)

标签:排列,nums,46,47,used,vector,result,path
From: https://blog.csdn.net/2301_79865280/article/details/142867735

相关文章

  • [Python学习日记-46] Python 中第三方开源模块的安装、使用与上传自己写的模块
    [Python学习日记-46]Python中第三方开源模块的安装、使用与上传自己写的模块简介下载与安装如何使用安装好的第三方开源模块如何上传自己写的模块到PyPi简介    在前面的模块介绍和导入当中主要介绍的都是Python内置的一些模块,我们把它称为标准库,而这个库......
  • B. 全排列问题
    时间限制:1s 空间限制:256MB输出自然数1到n所有不重复的排列,即n的全排列,要求所产生的任一数字序列中不允许出现重复的数字。(注意输出格式)输入n(1<=n<=9)输出由1~n组成的所有不重复的数字序列,每一行一个序列,每个数字前4个空格。样例样例输入13样例输出11......