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:
- The length of the given array will not exceed 15.
- The range of integer in the given array is [-100,100].
- The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.
这道题让我们找出所有的递增子序列,那么我们应该不难想到,这题肯定是要先找出所有的子序列,从中找出递增的。找出所有的子序列的题我们之前也接触过和,那两题不同之处在于数组中有没有重复项。而这道题明显是有重复项的,所以需要用到中的解法。我们首先来看一种迭代的解法,对于重复项的处理,最偷懒的方法是使用set,利用其自动去处重复项的机制,然后最后返回时再转回vector即可。由于是找递增序列,所以我们需要对递归函数做一些修改,首先题目中说明了递归序列数字至少两个,所以只有当当前子序列个数大于等于2时,才加入结果。然后就是要递增,如果之前的数字大于当前的数字,那么跳过这种情况,继续循环,参见代码如下:
解法一:
class Solution {public: vector> findSubsequences(vector & nums) { set > res; vector out; helper(nums, 0, out, res); return vector >(res.begin(), res.end()); } void helper(vector & nums, int start, vector & out, set >& 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(); } }};
我们也可以在递归中进行去重复处理,方法是用一个set保存中间过程的数字,如果当前的数字在之前出现过了,就直接跳过这种情况即可,参见代码如下:
解法二:
class Solution {public: vector> findSubsequences(vector & nums) { vector > res; vector out; helper(nums, 0, out, res); return res; } void helper(vector & nums, int start, vector & out, vector >& res) { if (out.size() >= 2) res.push_back(out); unordered_set 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(); } }};
下面我们来看迭代的解法,还是老套路,先看偷懒的方法,用set来去处重复。对于递归的处理方法跟之前相同,参见代码如下:
解法三:
class Solution {public: vector> findSubsequences(vector & nums) { set > res; vector > 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 >(res.begin(), res.end()); }};
我们来看不用set的方法,使用一个哈希表来建立每个数字对应的遍历起始位置,默认都是0,然后在遍历的时候先取出原有值当作遍历起始点,然后更新为当前位置,如果某个数字之前出现过,那么取出的原有值就不是0,而是之前那个数的出现位置,这样就就不会产生重复了,如果不太好理解的话就带个简单的实例去试试吧,参见代码如下:
解法四:
class Solution {public: vector> findSubsequences(vector & nums) { vector > res, cur(1); unordered_map m; for (int i = 0; i < nums.size(); ++i) { int n = cur.size(); int 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; }};
本文转自博客园Grandyang的博客,原文链接:,如需转载请自行联系原博主。