LeetCode 491 - Increasing Subsequences

作者 QIFAN 日期 2017-02-24
LeetCode 491 - Increasing Subsequences

原题链接: 491. Increasing Subsequences


题干

给定一个数组,返回所有可能的非严格增序子集,子集至少有两个元素。数组中有重复元素。

举例:
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]]

思路

动态规划解法。遍历数组 nums 。用一个 map 来存储 已经出现过的值及其上次出现的位置。

nums[i] 的结果集等于之前所有结果集 res[i - 1] 加上 res[i - 1] 中所有 List 加上 nums[i] (如果 nums[i] 大于最后的数)再加上:

  • 若 nums[i] 第一次出现,nums[i] 与 map 中所有 key 的对子。
  • 若 map 中已存在 nums[i] ,遍历上次位置 last 到这次位置 curr,若某个值 nums[j] 首次出现的位置 i 比 last 小,说明这个值在上次 nums[i] 以后才有,应该将 (nums[j], nums[i]) 加入集合 res 。
    最后将 (nums[i], i) 存入 map

本来是用一个 List<List<List<Integer>>> 作为 dp 来做,写完之后发现只要记录一下上一次加的最后一个就好了。

用 List 超时了,应该是中间判断的时间花了太久,干脆先用 set 存,最后转到 List 里,过了。以为考的就是重复时候的条件,辣鸡。

代码:

public List<List<Integer>> findSubsequences(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length <= 1) {
return res;
}
int length = nums.length;
Set<List<Integer>> tempRes = new HashSet<>();
Set<Integer> numSet = new HashSet<>();
for (int i = 0; i < length; i++) {
// for list whose last num is smaller than nums[i], add nums[i] to get a new list.
for (List<Integer> subset: tempRes) {
if (subset.get(subset.size() - 1) <= nums[i]) {
List<Integer> newSet = new ArrayList<>(subset);
newSet.add(nums[i]);
res.add(newSet);
}
}
tempRes.addAll(res);
res.clear();
// for single num, combine num[i] to get a new list
for (Integer num: numSet) {
if (nums[i] >= num) {
List<Integer> newSet = new ArrayList<>();
newSet.add(num);
newSet.add(nums[i]);
tempRes.add(newSet);
}
}
numSet.add(nums[i]);
}
res.addAll(tempRes);
return res;
}

后来又想到一个思路。这道题其实就是找到最长的递增,然后返回所有子集就可以了。