leetcode 491递增子序列

简介: leetcode 491递增子序列

递增子序列


78fd2fb43187497caadf23c537f6d5b7.png8f05db3485bd4d5cb9484ba8c6681a88.png

回溯去重

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums , int indnx )
    {
      //小于2的不加入结果,至少两个
        if(path.size()>=2) result.push_back(path);
        if(indnx >= nums.size()) return;
    //用set统计每一层相同值元素的使用
        unordered_set<int> uset;
        for(int i =indnx ; i<nums.size(); i++)
        {
          //如果当前值小于上一个,或者这个值在该层用过了,跳过
            if(path.empty() == 0 && nums[i] < path.back() 
                || uset.find(nums[i]) != uset.end()) 
            continue;
            //将该使用过的存入set,标记使用过
            uset.insert(nums[i]);
            path.push_back(nums[i]);
            backtracking(nums,i+1 );
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums,0);
        return result;
    }
};

二刷

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void track_back(vector<int>& nums , int indnx)
    {
        if(indnx > nums.size()) return;
        if(path.size() >= 2 )
        {
             result.push_back(path);
        } 
        set<int> my_set;
        for(int i=indnx ; i<nums.size() ; i++)
        {
            if((path.empty()==0&&nums[i]<path.back()) || 
                my_set.find(nums[i])!=my_set.end()) continue;
            my_set.insert(nums[i]);
            path.push_back(nums[i]);
            track_back(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        if(nums.size() == 0) return result;
        track_back(nums,0);
        return result;
    }
};
相关文章
|
8月前
|
Java
leetcode-46:全排列
leetcode-46:全排列
51 1
|
8月前
|
Java
leetcode-491:递增子序列
leetcode-491:递增子序列
55 0
|
3月前
|
算法
Leetcode第46题(全排列)
这篇文章介绍了LeetCode第46题“全排列”的解题方法,使用深度优先搜索(DFS)和回溯算法来生成给定数组的所有可能排列。
53 0
Leetcode第46题(全排列)
|
3月前
Leetcode第47题(全排列II)
LeetCode第47题要求返回一个包含重复数字序列的所有不重复全排列,通过深度优先搜索和去重策略来解决。
38 0
|
5月前
|
算法
LeetCode第46题全排列
LeetCode第46题"全排列"的解题方法,利用回溯法避免重复并确保元素的有序性,生成所有可能的排列组合。
LeetCode第46题全排列
|
5月前
|
算法
LeetCode第5题最长回文子串
该文章介绍了 LeetCode 第 5 题最长回文子串的解法,通过分析回文子串的特点,使用动态规划的思想,用二维数组记录字符串是否为回文串,从后往前遍历找子串,减少重复判断,最终找到最长回文子串,并总结了解题时通过举例推导找规律的思路。
LeetCode第5题最长回文子串
|
5月前
|
算法
LeetCode第47题全排列II
LeetCode第47题"全排列II"的解题方法,通过排序和添加去重逻辑,使用回溯法避免生成重复的排列组合。
|
8月前
leetcode-5:最长回文子串
leetcode-5:最长回文子串
58 0
|
6月前
|
索引
821.字符的最短距离-力扣(LeetCode)
821.字符的最短距离-力扣(LeetCode)
51 0
|
8月前
|
存储 算法 Go
LeetCode第五题: 最长回文子串
给定一个字符串 `s`​,找到 `s`​ 中最长的回文子串。你可以假设 `s`​ 的最大长度为 1000。
LeetCode第五题: 最长回文子串