最长递增子序列两种算法实现(动态规划,二分查找)
恭喜你刷到博主 DP 经典题目详解部分第一期,想学好 DP 请关注订阅,会持续更新!!!!!
建议先阅读DP算法入门
00001 最长递增子序列(Longest Increasing Subsequence,简写 LIS)
提要:本文介绍两种算法实现
一种是动态规划(算法复杂度 O(n ^ 2)):
通过本题了解设计动态规划的通用技巧 ————> 数学归纳思想
一种是二分查找(算法复杂度 O(n log n)):
由 patience game 的纸牌游戏(甚至有一种排序方法就叫做 patience sorting(耐心排序))的思想衍生的算法
01 动态规划
假设这个结论在 k < n 时成立,然后想办法证明 k = n 的时候此结论也成立。如果能够证明出来,那么就说明这个结论对于 k 等于任何数都成立类似的,我们设计动态规划算法,不是需要一个 dp 数组吗?我们可以假设 dp[0...i - 1] 都已经被算出来了,怎么通过这些结果算出 dp[i]?
首先要定义清楚 dp 数组的含义,即 dp[i] 的值到底代表着什么?
我们的定义是这样的:dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
重申一遍 DP 框架
明确状态 -> 定义 dp 数组/函数的含义 -> 明确选择-> 明确 base case
int lengthOfLIS(vector<int> &nums)
{if (nums.empty())return 0;int n = nums.size();//dp 数组应该全部初始化为 1,因为子序列最少也要包含自己,所以长度最小为 1vector<int> dp(n, 1); // 填充 dp 数组for (int i = 1; i < n; ++i){//找到前面那些结尾比 i 小的子序列,然后把 i 接到最后,就可以形成一个新的递增子序列,而且这个新的子序列长度加 1for (int j = 0; j < i; ++j){if (nums[i] > nums[j]){dp[i] = max(dp[i], dp[j] + 1);}}}// 寻找 dp 数组中的最大值即找最长递增子序列int res = 0;for (int i = 0; i < n; ++i){res = max(res, dp[i]);}return res;
}
10 二分查找
首先我们玩下叫 patience game 的纸牌游戏
规则:他的实现原理就是首先使用数组中的第一个数字创建一个纸牌堆,然后逐个读取数组中的剩余数字,如果当前数字比所有纸牌堆中最上面的数字都大,就新建一个纸牌堆,把当前数字放到该堆中。否则找到一个最上面数字不小于当前数字的纸牌堆,把当前数字放到该纸牌堆中







我们只要把处理扑克牌的过程编程写出来即可。每次处理一张扑克牌不是要找一个合适的牌堆顶来放吗?牌堆顶的牌不是有序吗?
———> 用到二分查找了:搜索当前牌应放置的位置
int LIS(vector<int> &nums)
{if (nums.empty())return 0;vector<int> top; // 用于存储牌堆的顶端元素for (int poker : nums){// 二分查找,找到比 poker 大的最小位置auto it = lower_bound(top.begin(), top.end(), poker);// 如果没有找到合适的位置,说明 poker 应该作为新的牌堆加入if (it == top.end()){top.push_back(poker);}else{// 否则,更新找到的位置*it = poker;}}// 牌堆数即为 LIS 长度return top.size();
}
这里的二分查找直接用了 STL 算法库中的 lower_bound (因为lower_bound 底层实现使用二分查找)
想要了解二分查找的实现的参考
template <typename ForwardIterator, typename T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val) {while (first < last) {ForwardIterator mid = first + (last - first) / 2; // 计算中点if (*mid < val) {first = mid + 1; // 如果 mid 小于 val,则搜索右半部分} else {last = mid; // 如果 mid 大于或等于 val,则搜索左半部分}}return first; // 返回第一个不小于 val 的元素
}
相关文章:
最长递增子序列两种算法实现(动态规划,二分查找)
恭喜你刷到博主 DP 经典题目详解部分第一期,想学好 DP 请关注订阅,会持续更新!!!!! 建议先阅读DP算法入门 00001 最长递增子序列(Longest Increasing Subsequence,简写…...
Deepmotion技术浅析(三):特征提取
DeepMotion 的特征提取模块是整个动作捕捉和 3D 追踪流程的基础,负责从输入的视频帧中提取出具有代表性的视觉特征。这些特征将被用于人体姿态估计、动作识别、3D 重建等后续任务。 包括: 1.图像特征提取 卷积神经网络(CNN) 卷…...
国内CentOS使用yum安装docker和docker-compose
安装docker 安装需要的软件包, yum-util 提供yum-config-manager功能,另两个是devicemapper驱动依赖 yum install -y yum-utils device-mapper-persistent-data lvm2下载yum源采用阿里云的镜像源 wget -O /etc/yum.repos.d/docker-ce.repo https://mi…...
python学opencv|读取图像(十三)BGR图像和HSV图像互相转换深入
【1】引言 前序学习过程中,我们偶然发现:如果原始图像是png格式,将其从BGR转向HSV,再从HSV转回BGR后,图像的效果要好于JPG格式。 文章链接为: python学opencv|读取图像(十二)BGR图…...
【鸿蒙实战开发】数据的下拉刷新与上拉加载
本章介绍 本章主要介绍 ArkUI 开发中最常用的场景下拉刷新, 上拉加载,在本章中介绍的内容在实际开发过程当中会高频的使用,所以同学们要牢记本章的内容。下面就让我们开始今天的讲解吧! List 组件 在 ArkUI 中List容器组件也可以实现数据滚动的效果&a…...
面向对象设计规则和各类设计模式
面向对象设计(Object-Oriented Design, OOD)是一种软件设计方法论,它使用对象、类、继承、封装、多态等概念来组织代码。面向对象设计的核心目标是提高软件的可维护性、可扩展性和复用性。在面向对象设计中,遵循一定的设计原则和模…...
《拉依达的嵌入式\驱动面试宝典》—C/CPP基础篇(六)
《拉依达的嵌入式\驱动面试宝典》—C/CPP基础篇(六) 你好,我是拉依达。 感谢所有阅读关注我的同学支持,目前博客累计阅读 27w,关注1.5w人。其中博客《最全Linux驱动开发全流程详细解析(持续更新)-CSDN博客》已经是 Linux驱动 相关内容搜索的推荐首位,感谢大家支持。 《拉…...
利用Docker分层构建优化镜像大小
合适docker镜像文件大小不仅影响容器启动效率,也影响资源占用效率。本文介绍如何利用分层方式构建docker镜像,采用多种方式避免镜像文件太大而影响性能。 Docker 镜像大小优化的重要性 资源利用效率 较小的镜像文件在存储和传输过程中占用更少的空间和带…...
Spring 魔法探秘:从 Bean 线程安全到事务魔法全解析
1.Spring 框架中的单例 Bean 是线程安全的么? Spring 框架中的单例 Bean 本身并不保证线程安全性。单例模式意味着在整个应用程序的生命周期中,只会创建该 Bean 的一个实例,并且所有对该 Bean 的请求都将共享这个实例。 线程安全与否取决于…...
[Maven]IDEA父工程创建子工程后父工程不可运行
IDEA在使用maven构建项目时,如果你在当前工程下创建一个子工程,那么原有的工程(变为父工程的工程)原有的代码通常会变得不可运行。 这是因为,使用maven创建父子工程关系后,IDEA会自动变更项目的模块相关配置。 比如这是我maven工程…...
【系统移植】在开发板上加载内核和根文件系统的三种方法
实现环境:ubuntu24.04和FS4412实验平台。 要在开发板上运行linux操作系统,首先要将linux内核镜像(uImage)、设备树(dexynos4412-fs4412.dtb)和根文件系统镜像(ramdisk.img)加载到开发板内存。有以下几种方式加载: 一、通过tftp加载内核和根文件系统 二、通过EMMC加…...
#渗透测试#漏洞挖掘#红蓝攻防#护网#sql注入介绍02-基于错误消息的SQL注入(Error-Based SQL Injection)
免责声明 本教程仅为合法的教学目的而准备,严禁用于任何形式的违法犯罪活动及其他商业行为,在使用本教程前,您应确保该行为符合当地的法律法规,继续阅读即表示您需自行承担所有操作的后果,如有异议,请立即停…...
数据结构-排序(来自于王道)
排序的基本概念 插入排序 在这个算法中,除了输入的数组本身,没有使用额外的数据结构来存储数据,所有的操作都是在原数组上进行的。因此,无论输入数组的大小 n 是多少,算法执行过程中所占用的额外空间是固定的ÿ…...
【蓝桥杯选拔赛真题93】Scratch青蛙过河 第十五届蓝桥杯scratch图形化编程 少儿编程创意编程选拔赛真题解析
目录 Scratch青蛙过河 一、题目要求 编程实现 二、案例分析 1、角色分析 2、背景分析 3、前期准备 三、解题思路 1、思路分析 2、详细过程 四、程序编写 五、考点分析 六、推荐资料 1、入门基础 2、蓝桥杯比赛 3、考级资料 4、视频课程 5、python资料 Scr…...
ReactPress最佳实践—搭建导航网站实战
Github项目地址:https://github.com/fecommunity/easy-blog 欢迎Star。 近期,阮一峰在科技爱好者周刊第 325 期中推荐了一款开源工具——ReactPress,ReactPress一个基于 Next.js 的博客和 CMS 系统,可查看 demo站点。(…...
Hive-4.0.1数据库搭建(可选配置用户名密码远程连接)
1.官网下载tar包上传到服务器并解压(我这里解压到了hive目录): 2.进入到conf目录,并复制模板配置文件进行修改: cd /apache-hive-4.0.1-bin/conf cp hive-default.xml.template hive-site.xml3.编写内容如下: <property>&…...
P8772 求和 P8716 回文日期
文章目录 [蓝桥杯 2022 省 A] 求和[蓝桥杯 2020 省 AB2] 回文日期 [蓝桥杯 2022 省 A] 求和 题目描述 给定 n n n 个整数 a 1 , a 2 , ⋯ , a n a_{1}, a_{2}, \cdots, a_{n} a1,a2,⋯,an, 求它们两两相乘再相加的和,即 S a 1 ⋅ a 2 a 1 ⋅ a 3 ⋯ a…...
MySQL迁移SQLite
将 MySQL 的表结构和数据迁移到 SQLite,可以通过以下步骤实现。这个过程主要包括导出 MySQL 数据库到 SQL 文件,然后将其导入到 SQLite 数据库中。 步骤 1: 导出 MySQL 数据库 首先,需要将 MySQL 数据库导出为一个 SQL 文件。可以使用 mysq…...
RocketMQ中的顺序消息和乱序消息详解
内容编辑中… 1.背景 顺序消息是消息队列 RocketMQ 提供的一种高级消息类型。 对于一个指定的Topic,消息严格按照先进先出(FIFO)的原则进行消息发布和消费。 即先发送的消息先消费,后发送的消息后消费。 顺序消息在发送、存储和投递的处理过程中,强调多条消息间的先后…...
Unity UGUI图片循环列表插件
效果展示: 下载链接:https://gf.bilibili.com/item/detail/1111843026 概述: LoopListView2 是一个与 UGUI ScrollRect 相同的游戏对象的组件。它可以帮助 UGUI ScrollRect 以高效率和节省内存的方式支持任意数量的项目。 对于具有10,000个…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
