[LeetCode] 491. Increasing Subsequences

[grandyang]

 

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:

Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

 

Note:

1. The length of the given array will not exceed 15.
2. The range of integer in the given array is [-100,100].
3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

 

这道题让我们找出所有的递增子序列，应该不难想到，这题肯定是要先找出所有的子序列，从中找出递增的。找出所有的子序列的题之前也接触过 Subsets 和 Subsets II，那两题不同之处在于数组中有没有重复项。而这道题明显是有重复项的，所以需要用到 Subsets II 中的解法。首先来看一种迭代的解法，对于重复项的处理，最偷懒的方法是使用 TreeSet，利用其自动去处重复项的机制，然后最后返回时再转回 vector 即可。由于是找递增序列，所以需要对递归函数做一些修改，首先题目中说明了递增序列数字至少两个，所以只有子序列个数大于等于2时，才加入结果。然后就是要递增，如果之前的数字大于当前的数字，那么跳过这种情况，继续循环，参见代码如下：

 

解法一：

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        set<vector<int>> res;
        vector<int> out;
        helper(nums, 0, out, res);
        return vector<vector<int>>(res.begin(), res.end());
    }
    void helper(vector<int>& nums, int start, vector<int>& out, set<vector<int>>& res) {
        if (out.size() >= 2) res.insert(out);
        for (int i = start; i < nums.size(); ++i) {
            if (!out.empty() && out.back() > nums[i]) continue;
            out.push_back(nums[i]);
            helper(nums, i + 1, out, res);
            out.pop_back();
        }
    }
};

 

我们也可以在递归中进行去重复处理，方法是用一个 HashSet 保存中间过程的数字，如果当前的数字在之前出现过了，就直接跳过这种情况即可，参见代码如下：

 

解法二：

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> out;
        helper(nums, 0, out, res);
        return res;
    }
    void helper(vector<int>& nums, int start, vector<int>& out, vector<vector<int>>& res) {
        if (out.size() >= 2) res.push_back(out);
        unordered_set<int> st;
        for (int i = start; i < nums.size(); ++i) {
            if ((!out.empty() && out.back() > nums[i]) || st.count(nums[i])) continue;
            out.push_back(nums[i]);
            st.insert(nums[i]);
            helper(nums, i + 1, out, res);
            out.pop_back();
        }
    }
};

 

下面我们来看迭代的解法，还是老套路，先看偷懒的方法，用 TreeSet 来去处重复。对于递归的处理方法跟之前相同，参见代码如下：

 

解法三：

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        set<vector<int>> res;
        vector<vector<int>> cur(1);
        for (int i = 0; i < nums.size(); ++i) {
            int n = cur.size();
            for (int j = 0; j < n; ++j) {
                if (!cur[j].empty() && cur[j].back() > nums[i]) continue;
                cur.push_back(cur[j]);
                cur.back().push_back(nums[i]);
                if (cur.back().size() >= 2) res.insert(cur.back());
            }
        }
        return vector<vector<int>>(res.begin(), res.end());
    }
};

 

我们来看不用 TreeSet 的方法，使用一个 HashMap 来建立每个数字对应的遍历起始位置，默认都是0，然后在遍历的时候先取出原有值当作遍历起始点，然后更新为当前位置，如果某个数字之前出现过，那么取出的原有值就不是0，而是之前那个数的出现位置，这样就不会产生重复了，如果不太好理解的话就带个简单的实例去试试吧，参见代码如下：

 

解法四：

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> res, cur(1);
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); ++i) {
            int n = cur.size(), start = m[nums[i]];
            m[nums[i]] = n;
            for (int j = start; j < n; ++j) {
                if (!cur[j].empty() && cur[j].back() > nums[i]) continue;
                cur.push_back(cur[j]);
                cur.back().push_back(nums[i]);
                if (cur.back().size() >= 2) res.push_back(cur.back());
            }
        }
        return res;
    }
};

 

Github 同步地址：

#491

 

类似题目：

Subsets

Subsets II

Maximum Length of Pair Chain

 

参考资料：

https://leetcode.com/problems/increasing-subsequences/

https://leetcode.com/problems/increasing-subsequences/discuss/97124/c-dfs-solution-using-unordered_set

https://leetcode.com/problems/increasing-subsequences/discuss/97134/evolve-from-intuitive-solution-to-optimal

 

LeetCode All in One 题目讲解汇总(持续更新中...)