Leetcode 491 Increasing Subsequences

发表于 |

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

示例:
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

说明:

  1. 给定数组的长度不会超过15。
  2. 数组中的整数范围是 [-100,100]。
  3. 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。

分析：

  1. 如果你看出来这道题和最长上升子序列是一模一样的话那么答案做出来也就不难了，这也是为什么我把这道题归入dp类的原因
  2. 我们可以先思考一下LIS问题是怎么处理的，我们使用dp[i]表示前i个数字组成的序列中以nums[i]结尾的最长上升子序列的长度，dp[i] = max([dp[j]+1 for j in range(i) if nums[j] < nums[i]])
  3. 根据这个思路我们可以想到这道题其实也可以用一样的方法，我们使用一个字典d，d[i]表示以nums[i]结尾的上升子序列，初始化所有的d[i] = [[nums[i]]]
  4. 则可获得递推式 d[i].append(l+nums[i]) for j in range(i) if nums[j] <= nums[i] for l in d[j]
  5. 当然严格来说上式不能算是递推式，我们直接用给出的具体实例来看一下是怎么运作的，初始化d = {0:[[4]],1:[[6]],2:[[7]],3:[[7]]}，我们从1开始分析，nums[1] > nums[0]，所以d[1] = [[6],[4,6]]，依次类推d[2] = [[4,7],[6,7],[4,6,7]]，d[3] = …

思路：

  1. 递推式如分析中所示，但考虑到4,6,7,7,7这种情况，计算第三个7的时候会出现重复情况，所以用一个集合来确保答案中没有重复元素，然后又因为list本身不可hash，所以转化成元祖来进行hash即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
    def findSubsequences(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # 初始化字典
        d = {i:[[nums[i]]] for i in range(len(nums))}
        for i in range(1,len(nums)):
            for j in range(i):
                if nums[i] >= nums[j]:
                    for l in d[j]:
                        d[i].append(l+[nums[i]])
        
        s = set()
        res = []
        for i in range(len(nums)):
            for l in d[i]:
            	# 因为字典中本身存在长度为1的list，需要我们排除
                if len(l) < 2: continue
                if tuple(l) in s: continue
                s.add(tuple(l))
                res.append(l)
        return res

57 / 57 test cases passed.
difficulty: medium
Runtime: 984 ms