[数据结构与算法]最长连续序列 python

最长连续序列 python

2022.09.19

1.128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

解法1 暴力求解：去重+排序

nums = [0,3,7,2,5,8,4,6,0,1]
t = 1
ans = 0
nums = sorted(set(nums))# 先去重再排序
if not nums: # 列表为空返回0
	print(0)
for i in range(len(nums)-1):
    if nums[i+1]-nums[i] == 1:# 列表为空返回0
        t+=1
    else:
        ans = max(ans,t)# 最长连续递增序列，后一个元素比前一个元素大1。
        t = 1
print(max(ans,t)) # 有可能去重排序后整个都是连续的，所以要输出ans,t中较大的一个

解法2 动态规划+哈希表

题目要求$O(n)$复杂度，但是哈希表比暴力求解更慢。
借鉴【动态规划】Python 题解及讨论区

class Solution(object):
    def longestConsecutive(self, nums):
        hash_dict = dict() # 用哈希表存储每个端点值对应连续区间的长度
        max_length = 0
        for num in nums:
            if num not in hash_dict: # 若是新数加入;若数已在哈希表中,跳过不做处理
                left = hash_dict.get(num - 1, 0) # 取出其左右相邻数已有的连续区间长度 left 和 right
                right = hash_dict.get(num + 1, 0)
                cur_length = 1 + left + right # 计算当前数的区间长度为：cur_length = left + right + 1
                if cur_length > max_length: # 根据 cur_length 更新最大长度 max_length 的值
                    max_length = cur_length
                hash_dict[num] = cur_length # 更新区间两端点的长度值
                hash_dict[num - left] = cur_length
                hash_dict[num + right] = cur_length
        return max_length

2.300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1

参考链接：动态规划 + 二分查找，清晰图解

解法1 动态规划

执行用时3080ms

class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums: # 列表为空返回0
            return 0
        dp = [1] * len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[j] < nums[i]: # 如果要求非严格递增，将此行 '<' 改为 '<=' 即可。
                    dp[i] = max(dp[i], dp[j] + 1) #  dp[i]的值代表以nums[i]结尾的最长子序列长度
        return max(dp)

解法2 动态规划+二分查找

采用了二分查找后，执行用时只有24ms。

class Solution(object):
    def lengthOfLIS(self, nums):
        tails, res = [0] * len(nums), 0 # 新建数组tails，用于保存最长上升子序列。
        for num in nums: # 对原序列进行遍历，将每位元素二分插入tails中。
            i, j = 0, res
            while i < j:
                m = (i + j) // 2
                if tails[m] < num: # 如果要求非严格递增，将此行 '<' 改为 '<=' 即可。
                    i = m + 1 
                else: 
                    j = m
            tails[i] = num
            if j == res: 
                res += 1
        return res

3.354. 俄罗斯套娃信封问题

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

示例 1：
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例 2：
输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

Python中bisect的使用方法

Python 二分查找与 bisect 模块
8.6. bisect — 数组二分查找算法

import bisect
#使用bisect函数前需要对列表进行排序，否则虽然可以输出数值，但没有意义
a = [1, 5, 6, 10, 9]
a.sort()
print("最初的列表：", a)
-----------------------
输出>>>
最初的列表： [1, 5, 6, 9, 10]

1.bisect.bisect 返回某个数在列表中可以插入的位置，但不会插入该数。

#如果这个数与列表中的元素相同，则返回元素后面的位置
print("6在列表中可以插入的位置：", bisect.bisect(a, 6))
-----------------------
输出>>>
6在列表中可以插入的位置： 3

2.bisect.insort 将某个数插入列表

bisect.insort(a, 8)
print("在列表中插入8：", a)
-----------------------
输出>>>
在列表中插入8： [1, 5, 6, 8, 9, 10]

3.处理插入数值与列表元素相同的情况，插入该数

#bisect.insort_left 插入元素左侧位置；bisect.insort_right 插入元素右侧位置
bisect.insort_left(a, 5)
print("在列表中插入5：", a)
bisect.insort_right(a, 10)
print("在列表中插入10：", a)
-----------------------
输出>>>
在列表中插入5： [1, 5, 5, 6, 8, 9, 10]
在列表中插入10： [1, 5, 5, 6, 8, 9, 10, 10]

4.处理插入数值与列表元素相同的情况，返回位置，但不会插入该数

#bisect.bisect_left 插入元素左侧位置；bisect.bisect_right 插入元素右侧位置
print("5在列表中可以插入的位置：", bisect.bisect_left(a, 5))
print("5在列表中可以插入的位置：", bisect.bisect_right(a, 5))
-----------------------
输出>>>
5在列表中可以插入的位置： 1
5在列表中可以插入的位置： 3

5. bisect() 还可以用于数字表查询

Python导入模块的方法有两种：import module 和 from module import，区别是前者所有导入的东西使用时需加上模块名的限定，而后者不要。

# import bisect # 报错，TypeError: 'module' object is not callable
from bisect import * 
def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
    i = bisect(breakpoints, score)
    return grades[i]
[grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
-----------------------
输出>>>
['F', 'A', 'C', 'C', 'B', 'A', 'A']

解法1 动态规划

超出时间限制

[[2, 3], [5, 4], [6, 5], [6, 7]]

用第一个维度递增，第二个维度递减的顺序排序，会得到下面的结果：

[[2, 3], [5, 4], [6, 7], [6, 5]]

这个时候，只看第二个维度
[3, 4, 7, 5]，就会得到最长递增子序列的长度是 3 的正确结果

class Solution(object):
    def maxEnvelopes(self, envelopes):
		if not envelopes: # 列表为空返回0
            return 0
        N = len(envelopes)
        envelopes.sort(key=lambda x: (x[0], -x[1])) # 按第一维升序，第二位降序对信封进行快排
        res = 0
        dp = [1] * N
        for i in range(N):
            for j in range(i):
                if envelopes[j][1] < envelopes[i][1]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

解法2 动态规划+二分查找

class Solution(object):
    def maxEnvelopes(self, envelopes):
        envelopes.sort(key=lambda x: [x[0], -x[1]]) # 按第一维升序，第二位降序对信封进行快排
        dp = []
        for i, env in enumerate(envelopes):
            i = bisect.bisect_left(dp, env[1]) # bisect.bisect_left 插入元素左侧位置
            if i < len(dp):
                dp[i] = env[1]
            else:
                dp.append(env[1])
        return len(dp)

4.329. 矩阵中的最长递增路径

给定一个 $m$ x $n$整数矩阵 matrix ，找出其中最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1：
输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4 
解释：最长递增路径为 [1, 2, 6, 9]。

示例 2：
输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4 
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

示例 3：
输入：matrix = [[1]]
输出：1

解法1 记忆化搜索+DFS

functools.lru_cache装饰器详解
在functools这个模块中，有lru_cache这个一个神奇的装饰器存在。functools.lru_cache的作用主要是用来做缓存，他能把相对耗时的函数结果进行保存，避免传入相同的参数重复计算。同时，缓存并不会无限增长，不用的缓存会被释放。

# import functools
class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        @lru_cache(None)
        def dfs(x, y):
            res = 1
            for a, b in [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]:
                if 0 <= a < m and 0 <= b < n and matrix[a][b] > matrix[x][y] and dfs(a, b) + 1 > res:
                    res = dfs(a, b) + 1
            return res
        m, n = len(matrix), len(matrix[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                if dfs(i, j) > ans:
                    ans = dfs(i, j)
        return ans

5.334. 递增的三元子序列

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

示例 1：
输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意

示例 2：
输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组

示例 3：
输入：nums = [2,1,5,0,4,6]
输出：true
解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6

解题思路

用两个变量 r1, r2 分别记录第一小和第二小的数。然后遍历 nums。只要碰到比 r1 小的数我们就替换掉 r1，碰到比 r1 大但比 r2 小的数就替换 r2。
只要碰到比 r2 大的数就已经满足题意了。

class Solution:
    def increasingTriplet(self, nums):
        r1, r2 = sys.maxsize, sys.maxsize
        for n in nums :
            if n <= r1 : r1 = n
            elif n <= r2 : r2 = n
            else : return True
        return False

参考内容

最长递增子序列问题五连击