LeetCode 491. Increasing Subsequences
原题链接在这里：https://leetcode.com/problems/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.
题解：
The DFS needs the state, current start index, current item.
When item size is already >= 2, then add a copy to res.
Otherwise, iterate from start, if nums[i] >= last number in item, then add it to item.
When backtracking, remove the last added number.
Time Complexity: exponential.
Space: O(n). n = nums.length.
AC Java:
class Solution {
public List<List<Integer>> findSubsequences(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums == null || nums.length < 2){
return res;
}
HashSet<List<Integer>> hs = new HashSet<>();
dfs(nums, 0, new ArrayList<Integer>(), hs);
return new ArrayList<List<Integer>>(hs);
}
private void dfs(int [] nums, int start, List<Integer> item, Set<List<Integer>> hs){
if(item.size() > 1){
hs.add(new ArrayList<Integer>(item));
}
for(int i = start; i<nums.length; i++){
if(item.size() == 0 || item.get(item.size()-1) <= nums[i]){
item.add(nums[i]);
dfs(nums, i+1, item, hs);
item.remove(item.size()-1);
}
}
}
}
Another way to avoid the duplicate is to record visited item on each level of DFS.
For the same level, if we see a previous visited number.
e.g. 4,6,7,7. when item = 4,6. First time visited 7, 7 is added to set. set = [6, 7]. item = 4,6,7. set is on this level of DFS.
Later it is removed from item, but it is still in the set. Thus when encountering the 2nd 7, it would skip.
But item = 4,6,7,7 still is added to res. That is because the second 7 is added to set on next level of DFS.
Time Complexity: exponential.
Space: O(n). n = nums.length.
AC Java:
class Solution {
public List<List<Integer>> findSubsequences(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums == null || nums.length < 2){
return res;
}
dfs(nums, 0, new ArrayList<Integer>(), res);
return res;
}
private void dfs(int [] nums, int start, List<Integer> item, List<List<Integer>> res){
if(item.size() > 1){
res.add(new ArrayList<Integer>(item));
}
HashSet<Integer> visited = new HashSet<Integer>();
for(int i = start; i<nums.length; i++){
if(visited.contains(nums[i])){
continue;
}
if(item.size() == 0 || item.get(item.size()-1) <= nums[i]){
visited.add(nums[i]);
item.add(nums[i]);
dfs(nums, i+1, item, res);
item.remove(item.size()-1);
}
}
}
}
最新文章
- jdbc 日期时间相关的类型
- 创建Java类并实例化的基本过程
- POJ 3243 Clever Y （求解高次同余方程A^x=B(mod C) Baby Step Giant Step算法）
- java设计模式—Adapter模式
- WebDriver: Getting it to play nicely with Xvfb
- CentOS Linux修改系统时区
- springmvc 基础
- PHP 7: PHP 变量和常量的定义
- Spring+SpringMVC+MyBatis+easyUI整合优化篇（四）单元测试实例
- grub2详解(翻译和整理官方手册)
- [2014-11-11]使用Owin中间件搭建OAuth2.0认证授权服务器
- JAVA课程设计--简易计算器（201521123022 黄俊麟）
- MYSQL可调用执行自定义SQL的代码
- .NET内存泄漏（之 静态事件）
- 关于itext生成pdf的新的demo(包含简单的提取txt文件的内容 和xml内容转化为pdf)
- busybox tar 命令支持 tar.gz
- 在 arc里面打印 引用计数的方法
- SHOW CREATE语句
- Excel批量删除换行符_clean函数
- SVN入门教程总结