Python Leetcode会求最长递增子序列长度还不够？

本文主要是介绍Python Leetcode会求最长递增子序列长度还不够？，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

最近做某公司的笔试，遇到了一道求最长递增子序列！最长递增子序列！最长递增子序列！注意不是求长度，而是求序列-_-.(如果存在多个解，则输出字典序最小的那个子序列)当时人都傻了，一直做的是求长度，这次还上升了一个档次，当时时间紧没想出来（一个小时10道选择题，3道编程题，我想知道这时间安排合理么）

今天想了一下，才发现也很简单，我们先看求最长递增子序列长度的代码：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return n
        dp = [1 for _ in range(n)]
        result = 1
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
                if dp[i] > result: result = dp[i]
        return result

另外一种二分+贪心的代码：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        d = []  # d[i]:长度为 i + 1 的最长上升子序列的末尾元素的最小值
        for num in nums:
            if not d or num > d[-1]:
                d.append(num)
            else:
                l, r = 0, len(d) - 1
                while l <= r:
                    mid = (l + r) >> 1
                    if d[mid] >= num:
                        r = mid - 1
                    else:
                        l = mid + 1
                d[l] = num
        return len(d)

这里求最长递增子序列，不能用二分+贪心的方法（或许可以，只是我还没想出来？）
代码逻辑也很简单，只是在dp方法dp[i] = max(dp[i], dp[j] + 1)处进行序列列表的更新，代码如下：

class Solution:
    def lengthOfLIS(self, nums):
        n = len(nums)
        if n <= 1:
            return n
        dp = [1 for _ in range(n)]
        path = [[nums[i]] for i in range(len(nums))]
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    # dp[i] = max(dp[i], dp[j] + 1)
                    # 下面将这行代码分开判断，利于path[i]的更新
                    if dp[i] <= dp[j] + 1:
                        dp[i] = dp[j] + 1
                        path[i] = min(path[j] + [nums[i]], path[i]) # 取最小表示的是：如以7结尾的有两种：2-5-7和2-3-7，应该选择最小的2-3-7
                    # 下面写出来便于你的理解
                    else:
                        dp[i] = dp[i]
                        path[i] = path[i]
        return dp, path
nums = [10,9,2,5,3,1,7,101,18]
f = Solution()
dp, path = f.lengthOfLIS(nums)
print(dp)
print(path)
res = []
for i in range(len(path)):
    if len(path[i]) == max(dp):
        res.append(path[i]) # 将长度为max(dp)的序列加入res中
print(min(res))  # 得到字典序最小的序列

其实发现，我们在leetcode上做的很多求最长/最短值这种题，到了公司的机试就变成了求其最长/最短路径，平时不注意，到机试时，一时还真想不出方法。

这篇关于Python Leetcode会求最长递增子序列长度还不够？的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！