LeetCode 300——最长上升子序列
2024-09-05 18:13:29
1. 题目
2. 解答
2.1. 动态规划
我们定义状态 state[i] 表示以 nums[i] 为结尾元素的最长上升子序列的长度,那么状态转移方程为:
\[state[i] = max(state[j] + 1) \space 如果 \space nums[i] > nums[j], 0 \leqslant j < i
\]
\]
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> state(n, 1);
for (int i = 1; i < n; i++)
{
for (int j = i-1; j >= 0; j--)
{
if (nums[i] > nums[j])
state[i] = max(state[i], state[j]+1);
}
}
int ret = 0;
for (int i = 0; i < n; i++)
ret = max(ret, state[i]);
return ret;
}
};
易知上面代码的时间复杂度为 \(O(n^2)\)。
2.2. 贪心思想
我们用一个列表 result 来放置我们的最长上升子序列,然后向后遍历数组,如果 nums[i] > result[-1],说明当前元素应该被放进列表中去,因为这样就能组成一个更长的上升子序列;如果 nums[i] < result[-1],说明目前的上升子序列里面有大于当前元素的数据,贪心思想是说让我们用当前元素去替换掉上升子序列里面第一个大于等于当前元素的数,这样我们就可以有更大的操作空间去向 result 里面放更多的元素,从而形成更长的上升子序列。
比如 nums=[10,9,2,5,3,7,101,18],算法过程如下所示:
\[result = [10] \\
result = [9] \gets 9 < 10 \\
result = [2] \gets 2 < 9 \\
result = [2, 5] \gets 5 > 2 \\
result = [2, 3] \gets 3 < 5 \\
result = [2, 3, 7] \gets 7 > 3 \\
result = [2, 3, 7, 101] \gets 101 > 7 \\
result = [2, 3, 7, 18] \gets 18 < 101 \\
\]
result = [9] \gets 9 < 10 \\
result = [2] \gets 2 < 9 \\
result = [2, 5] \gets 5 > 2 \\
result = [2, 3] \gets 3 < 5 \\
result = [2, 3, 7] \gets 7 > 3 \\
result = [2, 3, 7, 101] \gets 101 > 7 \\
result = [2, 3, 7, 18] \gets 18 < 101 \\
\]
class Solution:
def binary_search(self, result, data):
n = len(result)
i, j = 0, n-1
while i <= j:
mid = i + (j - i) // 2
if result[mid] >= data:
if mid == 0 or result[mid-1] < data:
return mid
else:
j = mid - 1
else:
i = mid + 1
return -1
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
if n == 0: return 0
result = [nums[0]]
for i in range(1, n):
if nums[i] > result[-1]:
result.append(nums[i])
elif nums[i] < result[-1]:
#在result中找到第一个大于等于nums[i]的元素位置
pos = self.binary_search(result, nums[i])
result[pos] = nums[i]
return len(result)
循环需要 \(n\) 次,二分查找复杂度为 \(O(logn)\),所以总体代码的时间复杂度为 \(O(nlogn)\)。
获取更多精彩,请关注「seniusen」!
最新文章
- C#搜索指定文件夹内的符合要求的文件
- alfresco install in linux, and integrated with tesseract ocr
- ORACLE关于索引是否需要定期重建争论的整理
- SVD++:推荐系统的基于矩阵分解的协同过滤算法的提高
- Django的是如何工作的
- 学习iOS笔记第一天的C语言学习记录
- PostgreSQL连接Python
- script加defer=";defer"; 的意义
- Python学习之四【变量】
- Thinkphp 连接数据库、查询、添加
- 字符相等(E - 暴力求解、DFS)
- HTML CSS基础(三)
- strtok函数 分类: c++ 2014-11-02 15:24 214人阅读 评论(0) 收藏
- 一个简单的基于BIO的RPC框架
- Docker 系列七(Dubbo 微服务部署实践).
- ACM-ICPC 2018 沈阳赛区网络预赛 I. Lattice&#39;s basics in digital electronics 阅读题加模拟题
- windows7时间同步设置
- 持续更新 | 想不到的key
- 【LOJ】#2306. 「NOI2017」蔬菜
- 快速排序——PowerShell版
热门文章
- JavaSE基础:泛型
- js变量的作用域与函数作用域
- 10分钟,让你彻底明白Promise原理
- k8s+docker+proget 镜像制作
- git上传文件夹报错: ! [rejected] master ->; master (fetch first) error: failed to push some refs to &#39;https://github.com/taminachen/rjxm.git&#39; hint: Updates were rejected because the remote contains work
- urllib urllib2学习笔记
- Ubuntu 16.04 编译ORB_SLAM2_modified
- python中字符串格式化的两种方法
- Java基本的程序结构设计 字符类型
- 第三篇:解析库之re、beautifulsoup、pyquery