[LeetCode] 491. Increasing Subsequences 递增子序列
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.
这道题让我们找出所有的递增子序列，应该不难想到，这题肯定是要先找出所有的子序列，从中找出递增的。找出所有的子序列的题之前也接触过 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, , 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() >= ) 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 + , 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, , out, res);
return res;
}
void helper(vector<int>& nums, int start, vector<int>& out, vector<vector<int>>& res) {
if (out.size() >= ) 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 + , out, res);
out.pop_back();
}
}
};
下面我们来看迭代的解法，还是老套路，先看偷懒的方法，用 TreeSet 来去处重复。对于递归的处理方法跟之前相同，参见代码如下：
解法三：
class Solution {
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
set<vector<int>> res;
vector<vector<int>> cur();
for (int i = ; i < nums.size(); ++i) {
int n = cur.size();
for (int j = ; 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() >= ) 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();
unordered_map<int, int> m;
for (int i = ; 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() >= ) res.push_back(cur.back());
}
}
return res;
}
};
Github 同步地址：
https://github.com/grandyang/leetcode/issues/491
类似题目：
参考资料：
最新文章
- 调试台自动多出现一个'&#65279;' ，我 用uploadify上传图片时，在给页面写入一个返回值为图片名称的变量的值的时候值的前面始终多出现一个'&#65279;'
- python查找空格和中文
- 【转载】经典SQL语句大全
- 编辑器sublime text3 破解码
- C#中通过Selenium IWebDriver实现人人网相册备份工具
- python练习程序（显示图像）
- poj 2886 Who Gets the Most Candies?（线段树和反素数）
- Java中NaN和-0.0f的比较问题
- jQuery知识点整合
- JDBC （二）
- springboot~jpa个性化数据操作接口
- 从知乎首页用户操作入口学习到的CSS技巧 - 合理利用伪元素实现一些装饰样式
- linux虚拟机桥接网络配置
- MySQL 5.7.14安装说明，解决服务无法启动
- MaidSafe区块链项目白皮书解读
- Python学习笔记之逻辑回归
- java 浮点运算
- JSONObject遍历获取键值方法合并两个JSONObject
- （资源）Git优秀学习资源
- nginx-----惹不起的端口修改