十月常见算法考题、最长递增子序列，Leetcode第300题最长上升子序列的变种，我没见过乔丹，今天詹姆斯就是我的神！
@Author：Runsen
@Date：2020/10/12
十月过得很平缓。在这个“收获的季节”，我成了为数不多不必收获的人。每天睡到中午，即使闹钟设在早上也很难把自己弄醒。
十月没有重要的待办事项、非做不可的作业，也没有实习，人好像被社会排除在外，只有日期的变化和昼夜的流动，变成这个月很重要的刻度，甚至盼头：朝盼暮，暮盼朝，明日永复，往昔不溯洄。
十五号又要补考化工原理，本不想写博客了，好好看看化工原理，刷题，谁想不到今天詹姆斯FMVP，我本不是湖人的粉，而是詹姆斯的粉丝，于是又花点时间写下博客了。
牛客：最长递增子序列常考算法问题
如果我只写日记，不写代码IT之类的都不好意思发CSDN博客了，那顺便把前几天我搞不懂了最长递增子序列算法写一下吧。
牛客题目：https://www.nowcoder.com/practice/9cf027bf54714ad889d4f30ff0ae5481
题目是这样的，有一个整数序列，例如 1, 6, 8, 2, 4, 5, 9，在这个数列中找到一个长度最长的递增子数列。（不是长度）
输入
[2,1,5,3,6,4,8,9,7]
输出
[1,3,4,8,9]
输入
[1,2,8,6,4]
输出
[1,2,4]
说明
其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
此题，之前还有类似的，类似的牛客题目
Leetcode300 最长上升子序列
其实这道题，我马上就想到了Leetcode300 最长上升子序列的两次动态规划做法。
def getMaxSubList(nums): # 如果定义dp dp[i] 最长上升子序列 那么 dp[i] = max(dp[i], dp[k] + 1) 0<k<i-1 m = len(nums) if m <= 1: return m dp = [ 1 for _ in range(m)] for i in range(1,m): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j]+ 1 ) print(dp) return max(dp)
print(getMaxSubList([1,3,6,7,9,4,10,5,6]))
[1, 2, 3, 4, 5, 3, 6, 4, 5]
6
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
在这里的dp指的是第i个最长上升子序列的长度，而牛客的是要求出对应的上升子序列。于是乎就转成了，通过dp和arr两个数组来求出 最长上升子序列。
首先遍历找到dp数组中的最大值maxlen以及下标index，其中maxlen就是最长递增子序列的长度，arr[index]就是最长递增子序列的最后一个数字，然后从index向前遍历数组arr，找到比arr[index]小的数arr[j]并且dp[j] + 1 = dp[index]。这个值就是子序列的倒数第二个数，依次向前遍历即可得到最长递增子序列。
'''
@Author： Runsen
@WeChat：RunsenLiu
@微信公众号： Python之王
@CSDN： https://blog.csdn.net/weixin_44510615
@Github： https://github.com/MaoliRUNsen
@Date： 2020/10/12
'''
def getMaxSubList(nums): # 如果定义dp dp[i] 最长上升子序列 那么 dp[i] = max(dp[i], dp[k] + 1) 0<k<i-1 m = len(nums) if m <= 1: return m dp = [ 1 for _ in range(m)] for i in range(1,m): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j]+ 1 ) print(dp) return dp
def generateLIS(arr, dp): # 因为要找到最小的字典序，max的方法是找到第一个，而不是最后一个 maxlen = max(dp) index = dp.index(max(dp)) # maxlen = index = 0 # for i in range(len(dp)): # if dp[i] >= maxlen: # maxlen = dp[i] # index = i # maxlen是dp中最大值，index只是对应的index # lis lis = [None for _ in range(maxlen)] # lis最后一个一定是最大值 lis[maxlen-1] = arr[index] # maxlen需要减一 maxlen = maxlen - 1 # 倒序 for i in range(index, -1, -1): # 寻找倒数的数 if arr[i] < arr[index] and dp[i]+1 == dp[index]: lis[maxlen-1] = arr[i] maxlen = maxlen - 1 index = i return lis
print(generateLIS([1,3,6,7,9,4,10,5,6],getMaxSubList([1,3,6,7,9,4,10,5,6])))
print(generateLIS([1,2,8,4],getMaxSubList([1,2,8,4])))
[1, 2, 3, 4, 5, 3, 6, 4, 5]
[1, 3, 6, 7, 9, 10]
[1, 2, 3, 3]
[1, 2, 8]
- 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
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
但是由于最后的结果是最小的字典序，max的方法是找到第一个，而不是最后一个，需要修改max的写法。
# 最长递增子序列
def getMaxSubList(arr): def getdp(arr): m = len(arr) if m <= 1: return m dp = [1 for _ in range(m)] for i in range(1, m): for j in range(i): if arr[i] > arr[j]: dp[i] = max(dp[i], dp[j] + 1) print(dp) return dp def generateLIS(arr, dp): maxlen = index = 0 for i in range(len(dp)): if dp[i] >= maxlen: # >= 如果是max就是> maxlen = dp[i] index = i lis = [None for _ in range(maxlen)] # lis最后一个一定是最大值 lis[maxlen - 1] = arr[index] # maxlen需要减一 maxlen = maxlen - 1 # 倒序 for i in range(index, -1, -1): # 寻找倒数的数 if arr[i] < arr[index] and dp[i] + 1 == dp[index]: lis[maxlen - 1] = arr[i] maxlen = maxlen - 1 index = i return lis if arr == None or len(arr) == 0: return None dp = getdp(arr) return generateLIS(arr, dp) print(getMaxSubList([2, 1, 5, 3, 6, 4, 8, 9, 7]))
print(getMaxSubList([1, 2, 8, 4]))
[1, 2, 3, 4, 5, 3, 6, 4, 5]
[1, 3, 6, 7, 9, 10]
[1, 2, 3, 3]
[1, 2, 4]
- 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
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
上面的代码运行超时。
贪心+二分的巧妙解决Leetcode300
Leetcode300题最长上升子序列可以用 贪心+二分，具体的代码查看Leetcode。
如果插入的i比如前面的最后一个小，就寻找第一个大于等于的值，替换，典型的二分查找变种。
arr = [2, 1, 5, 3, 6, 4, 8, 9, 7]
d = []
for n in arr: if not d or n > d[-1]: d.append(n) else: l, r = 0, len(d) - 1 loc = r while l <= r: mid = (l + r) // 2 if d[mid] >= n: loc = mid r = mid - 1 else: l = mid + 1 d[loc] = n
print(d)
print(len(d))
[1, 3, 4, 7, 9]
5
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
一开始我以为就是这样，但是如果arr是[100,101,102,103,1,2,3]，得到的d不是[100,101,102,103]。
arr = [100,101,102,103,1,2,3]
d = []
for n in arr: if not d or n > d[-1]: d.append(n) else: l, r = 0, len(d) - 1 loc = r while l <= r: mid = (l + r) // 2 if d[mid] >= n: loc = mid r = mid - 1 else: l = mid + 1 d[loc] = n
print(d)
print(len(d))
[1, 2, 3, 103]
4
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
可以说这种的二分其实并不能求出最长递增子序列，因此唯一的方法就是求出dp，然后根据dp和arr求出最长递增子序列。
柳暗花明又一村
在我怀疑人生的时候，竟然看到了一个通过辅助数组ends来缩短时间复杂度到O(nlogn)。本质上还是二分。
具体博客参考：https://blog.csdn.net/qq_34342154/article/details/77132137
下面是最终通过的代码。
class Solution: def LIS(self, arr): def getdp(arr): # 求dp dp = [0 for _ in range(len(arr))] ends = [0 for _ in range(len(arr))] right = 0 dp[0] = 1 ends[0] = arr[0] # 二分法进行 for i in range(1, len(arr)): l = 0 r = right while l <= r: m = (l + r) // 2 if arr[i] > ends[m]: l = m + 1 else: r = m - 1 right = max(right, l) dp[i] = l + 1 ends[l] = arr[i] return dp def generateLIS(arr, dp): maxlen = index = 0 for i in range(len(dp)): if dp[i] >= maxlen: # >= 如果是max就是> maxlen = dp[i] index = i lis = [None for _ in range(maxlen)] # lis最后一个一定是最大值 lis[maxlen - 1] = arr[index] # maxlen需要减一 maxlen = maxlen - 1 # 倒序 for i in range(index, -1, -1): # 寻找倒数的数 if arr[i] < arr[index] and dp[i] + 1 == dp[index]: lis[maxlen - 1] = arr[i] maxlen = maxlen - 1 index = i return lis if arr == None or len(arr) == 0: return None dp = getdp(arr) return generateLIS(arr, dp)
- 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
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
后来看了别人的题解，我看废了。
后言（日记）
今天湖人总冠军，詹姆斯FMVP！
如果这个世界上真有超级英雄，他的名字一定叫勒布朗-詹姆斯。
已是十七生涯，犹能横刀立马。
三队四冠不足夸，再看风吹浪打。
终结十年无冠，奖杯聊显光华。
鏖战竞透紫金甲，今夜致敬曼巴。
每个年代都有各自的英雄！
我没见过乔丹，詹姆斯就是我的神！
文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。
原文链接：maoli.blog.csdn.net/article/details/109033289
- 点赞
- 收藏
- 关注作者
评论（0）