491. Increasing Subsequences 递增子序列

题目地址：https://leetcode.com/problems/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、 Thelengthofthegivenarraywillnotexceed15.；
2、 Therangeofintegerinthegivenarrayis[-100,100].；
3、 Thegivenarraymaycontainduplicates,andtwoequalintegersshouldalsobeconsideredasaspecialcaseofincreasingsequence.；

题目大意

找出一个数组中所有的递增的序列。

解题方法

我先写了dfs的做法，数组规模不超过15，那么O(N!)的时间复杂度能接受的。

dfs做法：

class Solution(object):
    def findSubsequences(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = set()
        self.dfs(nums, 0, res, [])
        return map(list, res)
    
    def dfs(self, nums, index, res, path):
        if len(path) >= 2:
            res.add(tuple(path))
        for i in range(index, len(nums)):
            if not path or nums[i] >= path[-1]:
                self.dfs(nums, i + 1, res, path + [nums[i]])

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

下面是动态规划的代码，使用了一个set来保证不会有重复，然后由于set之中只能放不可变的对象，所以放进去的是元组对象。当我们遍历到nums的每个数字的时候，对set中的所有的元素进行遍历，看每个tuple元素的最后一个数字是否是小于等于当前的num的，如果是的话就把当前的元素添加到原来的tuple的后面。这样的循环虽说稍显复杂，但是竟然也能通过了。。

代码：

class Solution(object):
    def findSubsequences(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        dp = set()
        for n in nums:
            for y in list(dp):
                if n >= y[-1]:
                    dp.add(y + (n,))
            dp.add((n,))
        return list(e for e in dp if len(e) > 1)

1 2 3 4 5 6 7 8 9 10 11 12 13

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发