没有合适的资源?快使用搜索试试~ 我知道了~
DP、二分-LeetCode300. 最长上升子序列(Python)
3 下载量 117 浏览量
2020-12-21
12:50:37
上传
评论
收藏 126KB PDF 举报
温馨提示
试读
1页
1、题目描述 给定一个无序的整数数组,找到其中最长上升子序列的长度。 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 说明:可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。 2、代码详解 法一:DP,O(N^2) class Solution(object): def lengthOfLIS(self, nums): """ :type nums: List[int] :rtype: int """
资源推荐
资源详情
资源评论
DP、二分、二分-LeetCode300. 最长上升子序列(最长上升子序列(Python))
1、题目描述、题目描述
给定一个无序的整数数组,找到其中最长上升子序列的长度。
输入: [10,9,2,5,3,7,101,18] 输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
说明:可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
2、代码详解、代码详解
法一:法一:DP,,O(N^2))
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int] :rtype: int
"""
if not nums: 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)
return max(dp)
nums = [10, 9, 2, 5, 3, 7, 101, 18] s = Solution()
print(s.lengthOfLIS(nums))
法二:二分查找,法二:二分查找,O(NlogN)
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int] :rtype: int
"""
tails = [0] * len(nums)
size = 0
for x in nums:
i, j = 0, size
while i != j:
m = (i + j) / 2
if tails[m] < x:
i = m + 1
else:
j = m
tails[i] = x
size = max(i + 1, size)
return size
作者:NLP_victor
资源评论
weixin_38709379
- 粉丝: 2
- 资源: 954
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功