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;
    }
};
相关文章
|
6天前
|
Java
leetcode-491:递增子序列
leetcode-491:递增子序列
25 0
|
6天前
leetcode-5:最长回文子串
leetcode-5:最长回文子串
24 0
|
6天前
|
存储 算法 Go
LeetCode第五题: 最长回文子串
给定一个字符串 `s`​,找到 `s`​ 中最长的回文子串。你可以假设 `s`​ 的最大长度为 1000。
LeetCode第五题: 最长回文子串
|
6天前
leetcode-647:回文子串
leetcode-647:回文子串
14 0
|
6天前
|
Java
leetcode-53:最大子序和
leetcode-53:最大子序和
22 0
|
6天前
leetcode-516:最长回文子序列
leetcode-516:最长回文子序列
21 0
|
8月前
|
算法
LeetCode5-最长回文子串
LeetCode5-最长回文子串
|
9月前
|
算法
LeetCode-5 最长回文子串
LeetCode-5 最长回文子串
|
9月前
|
存储 人工智能 算法
|
11月前
|
测试技术
力扣5-最长回文子串
力扣5-最长回文子串
48 0