【LeetCode】300. 最长递增子序列

news/2024/10/30 19:32:00/

300. 最长递增子序列(中等)

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

方法一:动态规划

  1. 思路

    • 通常来说,子序列不要求连续,而子数组子字符串必须连续;
    • 对于子序列问题,第一种动态规划方法是,定义 dp 数组,其中 dp[i] 表示以 i 结尾的子序列的性质。在处理好每个位置后,统计一遍各个位置的结果即可得到题目要求的结果。
    • 在本题中, dp[i] 可以表示为以 i 结尾的、最长子序列长度。对于每个位置 i ,如果其之前的某个位置 j 所对应的数字小于位置 i 所对应的数字 ,则我们可以获得一个以 i 结尾、长度为 dp[j] + 1 的子序列。为了遍历所有情况,我们需要对 i 和 j 进行两层循环,其时间复杂度为 O(n2)。
  2. 代码

    class Solution {
    public:int lengthOfLIS(vector<int>& nums) {int ans = 0;vector<int> dp(nums.size(), 1);for(int i=0; i<nums.size(); ++i){for(int j=0; j<i; ++j){if(nums[i] > nums[j]){dp[i] = max(dp[i], dp[j] + 1);}}ans = max(ans, dp[i]);}return ans;}
    };
    
  3. 收获

    • 我一开始的想法是将 dp[i] 表示为前 i 位最长递增子序列的长度,但是发现并不好算。

方法二:二分查找

  1. 思路

    • 本题还可以使用二分查找将时间复杂度降为 O(n logn)。
    • 定义 dp数组,其中 dp[k] 表示存储长度为 k+1 的最长递增子序列的最后一个数字
    • 遍历每一个位置 i ,如果对应的数字大于 dp 数组中所有数字的值,那么就把他放在 dp 数组的尾部,表示最长递增子序列长度+1;如果这个数字介于当前dp数组最小值和最大值之间,那么将最大值更新为当前数组,使得之后构成递增序列的可能性加大。
    • 根据这个方法维护 dp 数组永远是递增的,因此可以用二分查找加速搜索。
    • 然而,使用这个方法需要注意, dp数组的最终形式不一定是合法的排列形式,但最优解一定出现在遍历的过程中。
  2. 代码

    class Solution {
    public:int lengthOfLIS(vector<int>& nums) {int ans = 0;vector<int> dp;dp.push_back(nums[0]);for(int i=1; i<nums.size(); ++i){if(dp.back() < nums[i]){dp.push_back(nums[i]);}else{// 通过二分查找,返回第一次出现大于等于 nums[i] 的地址auto itr = lower_bound(dp.begin(), dp.end(), nums[i]);*itr = nums[i];}}return dp.size();}
    };
    
  3. 收获

    • 这个思路还挺新奇的,学习了 lower_bound 函数的用法 lower_bound。

http://www.ppmy.cn/news/61401.html

相关文章

人工智能实践: 基于T-S 模型的模糊推理

模糊推理是一种基于行为的仿生推理方法, 主要用来解决带有模糊现象的复杂推理问题。由于模糊现象的普遍存在, 模糊推理系统被广泛的应用。模糊推理系统主要由模糊化、模糊规则库、模糊推理方法以及去模糊化组成, 其基本流程如图1所示。 ■ 图1 模糊推理流程图 传统的模糊推理是…

【C++】vector的介绍及使用

目录 一、vector的介绍二、vector的常用接口2.1 vector的定义2.2 vector iterator的使用2.3 vector 空间增长问题2.4 vector 增删查改2.4.1.尾插和尾删2.4.2.任意位置插入和删除以及查找2.4.3.vector 的交换与遍历 2.5 vector 迭代器失效问题 一、vector的介绍 vector是表示可…

RocketMQ不同的类型消息

目录 普通消息 可靠同步发送 可靠异步发送 单向发送 三种发送方式的对比 顺序消息 事物消息 两个概念 事务消息发送步骤 事务消息回查步骤 消息消费要注意的细节 RocketMQ支持两种消息模式: 普通消息 RocketMQ提供三种方式来发送普通消息&#xff1a;可靠同步发送、…

Android基于JNA集成调用第三方C/C++的so库

Android基于JNA集成调用第三方C/C的so库 &#xff08;1&#xff09;引入JNA。 基于JNA开源项目&#xff0c;JNA对Android NDK的封装&#xff0c;简化Android层JNI集成调用C/C的so库。 GitHub - java-native-access/jna: Java Native AccessJava Native Access. Contribute to…

简单总结:使用 gunicorn 进行 Python Web 应用部署

简单总结&#xff1a;使用 gunicorn 进行 Python Web 应用部署 Gunicorn (Green Unicorn) 是一个 Python Web 应用服务器&#xff0c;可以帮助我们轻松地部署 Python Web 应用程序。它是一个预先创建的 WSGI (Web Server Gateway Interface) 服务器&#xff0c;可以通过简单的…

代码随想录算法训练营第五十三天| 1143.最长公共子序列 、1035.不相交的线、53. 最大子序和 动态规划

文章目录 1143.最长公共子序列:star:1035.不相交的线53. 最大子序和 动态规划 1143.最长公共子序列⭐️ 题目链接&#xff1a;代码随想录 解题思路&#xff1a; 1.dp数组&#xff1a;长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp(i)[j]…

2023年的深度学习入门指南(12) - PEFT与LoRA

2023年的深度学习入门指南(12) - PEFT与LoRA 大家都知道&#xff0c;大模型的训练需要海量的算力。其实&#xff0c;即使是只对大模型做微调训练&#xff0c;也是需要大量的计算资源的。 有没有用更少的计算资源来进行微调的方法呢&#xff1f;研究者研发出了几种被Hugging F…

武忠祥老师每日一题||定积分基础训练(三)

常用的基本不等式&#xff1a; sin ⁡ x < x < t a n x , x ∈ ( 0 , π 2 ) \sin x<x<\ tan x,x\in(0,\frac{\pi}{2}) sinx<x< tanx,x∈(0,2π​) e x ≥ 1 x , x ∈ ( − ∞ , ∞ ) e^x\ge1x,x\in(-\infty,\infty) ex≥1x,x∈(−∞,∞) x 1 x ≤ ln …