10-31 LeetCode 491. Increasing Subsequences

Increasing Subsequences

Description

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:

1. The length of the given array will not exceed 15.

2. The range of integer in the given array is [-100,100].

3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

提供一个整数数组，你的任务是找到所有不同的升序子序列，升序子序列的大小至少为2.

注意：

1. 数组长度不会超过15

2. 数组元素的值在-100到100之间

3. 数组中可能有重复的值，并且两个相等的整数也应该算作一个特殊的升序序列

Solution 1:

这题我用的递归去解决。现在我自己写递归有点困惑，一个模模糊糊的想法告诉我就是那样写，但是不能够很清晰的理解为什么是这么写。可能是跟我的算法不明确有关系吧，也可能是表达能力不够。

递归时传给递归函数一个index值，记录需要去遍历的数组的首地址，然后比较这个值与升序子序列的最后一个值得大小关系，大于则加入，进入下一个递归调用，否则index加一后重复上述过程。

这题第一次提交时有个错误，是我对Python语法不熟悉造成的，升序子序列不能重复，很自然而然的就想到了用set这个内置的数据结构，但是set里的元素不能是list,于是网上搜索了一下如何二维数组去重，代码里很清晰的展示了这一步骤。

代码：

    class Solution(object):
        def findSubsequences(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            result = []
            self.find(result, nums, [], 0)
            result = list(set(tuple(t) for t in result))
            return [lists for lists in result]
    
        def find(self, result_set, nums, lists, index):
            if len(lists) >= 2:
                result_set.append(lists)
            for i in range(index, len(nums)):
                if not lists:
                    self.find(result_set, nums, [nums[i]], i+1)
                else:
                    if nums[i] >= lists[-1]:
                        self.find(result_set, nums, lists+[nums[i]], i+1)

Solution2:

提交之后，我又花了点时间看了一下别人的算法，有不少人用递归，但是还有用动态规划的。动态规划的念头在我脑海中出现过，但是第一时间想不到状态转移方程，没有去深思。看了下别人的代码，发觉还是挺简单的。代码我就不贴出来了，因为没有自己去实现。我介绍下大概的思路。

首先考虑一个元素的子序列，那毫无疑问全是升序，将这些子序列添加到result数组中，然后在一个元素的序列的基础上考虑两个元素的升序子序列，也添加到result数组中，从而考虑三个的，四个的………………

最后返回结果时去除result中长度小于2的元素,以及去重操作。

for num in nums:
    for array in result:
        if num >= array[-1]:
            result.append(array+[num])
    result.append(num)

感想

今天是10月的最后一天了，时间过得真快啊。但是我这个月也没有刷多少题，在网上查找其他解题思路时，发现有很多人都分享自己的刷题过程。跟他们相比，我就是个渣渣= = 。