当前位置: 首页 > news >正文

算法【最长递增子序列问题与扩展】

本文讲解最长递增子序列以及最长不下降子序列的最优解,以及一些扩展题目。本文中讲述的是最优解,时间复杂度是O(n*logn),空间复杂度O(n),好实现、理解难度不大。这个问题也可以用线段树来求解,时间和空间复杂度和本节讲的最优解没有区别。

下面通过一些题目来加深理解。

题目一

测试链接:https://leetcode.cn/problems/longest-increasing-subsequence/

分析:这道题的基本做法是非常简单和常见的,所以下面给出基本做法以及优化时间复杂度的做法。基本做法的时间复杂度是O(n²)。代码如下。

class Solution {
public:int dp[2500];int lengthOfLIS(vector<int>& nums) {int length = nums.size();int ans = 1;dp[0] = 1;for(int i = 1;i < length;++i){dp[i] = 1;for(int j = 0;j < i;++j){if(nums[i] > nums[j]){dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;}}ans = ans > dp[i] ? ans : dp[i];}return ans;}
};

优化时间复杂度之后,能做到O(n*logn)。通过一个end数组,end[i]表示长度为i+1的严格递增子序列的最小结尾,故可以知道end数组是有序的,对于有序数组的查找可以采用二分查找法,这也是优化时间复杂度所在。最后end数组的长度就是最长严格递增子序列的长度。代码如下。

class Solution {
public:int end[2500];int get_index(int len, int num){int ans = -1;int l = 0, r = len - 1, m;while (l <= r){m = l + (r - l) / 2;if(end[m] >= num){ans = m;r = m - 1;}else{l = m + 1;}}return ans;}int lengthOfLIS(vector<int>& nums) {int length = nums.size();int len = 1, find;end[0] = nums[0];for(int i = 1;i < length;++i){find = get_index(len, nums[i]);if(find == -1){end[len++] = nums[i];}else{end[find] = nums[i];}}return len;}
};

题目二

测试链接:https://leetcode.cn/problems/russian-doll-envelopes/

分析:这道题的思路较为难想,其实只需要对于每个信封宽度从小到大排序,相同宽度的,对于高度从大到小排序,然后仅对高度求一个最长递增子序列即可。代码如下。

class Solution {
public:int end[100000];int get_index(int len, int num){int ans = -1;int l = 0, r = len - 1, m;while (l <= r){m = l + (r - l) / 2;if(end[m] >= num){ans = m;r = m - 1;}else{l = m + 1;}}return ans;}int maxEnvelopes(vector<vector<int>>& envelopes) {auto cmp = [](vector <int> v1, vector<int> v2){return v1[0] < v2[0] || (v1[0] == v2[0] && v1[1] > v2[1]);};sort(envelopes.begin(), envelopes.end(), cmp);int length = envelopes.size();int len = 1, find;end[0] = envelopes[0][1];for(int i = 1;i < length;++i){find = get_index(len, envelopes[i][1]);if(find == -1){end[len++] = envelopes[i][1];}else{end[find] = envelopes[i][1];}}return len;}
};

题目三

测试链接:https://leetcode.cn/problems/minimum-operations-to-make-the-array-k-increasing/

分析:这道题其实是将一个数组分为了k个子数组,然后只需要对每个子数组求一个最长不下降子序列,然后用子数组长度减去这个最长不下降子序列的长度就是需要操作的次数,将每一个子数组的操作次数求和即可得到答案。代码如下。

class Solution {
public:int nums[100000];int end[100000];int kIncreasing(vector<int>& arr, int k) {int length = arr.size();int ans = 0;int size;for(int i = 0;i < k;++i){size = 0;for(int j = i;j < length;j += k){nums[size++] = arr[j];}ans += (size - get_num(size));}return ans;}int get_num(int size){end[0] = nums[0];int len = 1;for(int i = 1, find;i < size;++i){find = get_index(nums[i], len);if(find == -1){end[len++] = nums[i];}else{end[find] = nums[i];}}return len;}int get_index(int num, int len){int ans = -1;int m;int l = 0;int r = len - 1;while (l <= r){m = (l + r) / 2;if(end[m] > num){ans = m;r = m - 1;}else{l = m + 1;}}return ans;}
};

题目四

测试链接:https://leetcode.cn/problems/maximum-length-of-pair-chain/

分析:因为结果中后一个数对的第一个数一定会比前一个数对的第一个数大,所以我们先对第一个数从小到大排序。然后对于去end数组查找的数选用数对的第一个数,但对end数组进行赋值的时候我们选用数对的第二个数,这是因为题目要求后一个数对的第一个数必须比前一个数对的第二个数大。代码如下。

class Solution {
public:int end[1000];int findLongestChain(vector<vector<int>>& pairs) {sort(pairs.begin(), pairs.end(), [](vector<int> v1, vector<int> v2)->bool{return v1[0] < v2[0];});int length = pairs.size();end[0] = pairs[0][1];int len = 1;for(int i = 0, find;i < length;++i){find = get_index(len, pairs[i][0]);if(find == -1){end[len++] = pairs[i][1];}else{end[find] = end[find] > pairs[i][1] ? pairs[i][1] : end[find];}}return len;}int get_index(int len, int num){int ans = -1;int m, l = 0, r = len - 1;while (l <= r){m = (l + r) / 2;if(end[m] >= num){ans = m;r = m - 1;}else{l = m + 1;}}return ans;}
};

这道题的最优解法是贪心。对于数对的第二个数从小到大排序,然后从一个开始寻找符合条件数对,遍历完即可得到答案。代码如下。

class Solution {
public:int findLongestChain(vector<vector<int>>& pairs) {sort(pairs.begin(), pairs.end(), [](vector<int> v1, vector<int> v2)->bool{return v1[1] < v2[1];});int pre = -2000;int ans = 0;int length = pairs.size();for(int i = 0;i < length;++i){if(pairs[i][0] > pre){pre = pairs[i][1];++ans;}}return ans;}
};

题目五

测试链接:https://www.luogu.com.cn/problem/P8776

分析:这道题需要理解,被修改的数和被修改为的数紧靠在一起求得的答案和原题目没有区别。这样被修改的数和被修改为的数就组成了一个子数组。对子数组的左边,求得以子数组左边下标为结尾的最长不下降子序列的长度且这个最长不下降子序列的最大值不能超过这个被修改为的数;对于这个子数组的右边,求得以子数组右边为开头的最长不下降子序列的长度。将两个最长不下降子序列的长度相加再加上k就是这个子数组求得的答案,遍历数组即可得到最大值。代码如下。

#include <iostream>
using namespace std;
int N, K;
int arr[100000];
int Right[100000];
int End[100000];
int get_index1(int num, int len){int ans = -1;int m, l = 0, r = len - 1;while (l <= r){m = (l + r) / 2;if(End[m] < num){ans = m;r = m - 1;}else{l = m + 1;}}return ans;
}
void get_right(){End[0] = arr[N-1];int len = 1;Right[N-1] = 1;for(int i = N-2, find;i >= K;--i){find = get_index1(arr[i], len);if(find == -1){End[len++] = arr[i];Right[i] = len;}else{End[find] = arr[i];Right[i] = find+1;}}
}
int get_index2(int num, int len){int ans = -1;int m, l = 0, r = len - 1;while (l <= r){m = (l + r) / 2;if(End[m] > num){ans = m;r = m - 1;}else{l = m + 1;}}return ans;
}
int main(void){scanf("%d%d", &N, &K);for(int i = 0;i < N;++i){scanf("%d", &arr[i]);}get_right();int ans = K + Right[K];End[0] = arr[0];int len = 1;for(int i = K+1, find;i < N;++i){find = get_index2(arr[i], len);find = find == -1 ? len : find;ans = ans > (find + K + Right[i]) ? ans : (find + K + Right[i]);find = get_index2(arr[i-K], len);if(find == -1){End[len++] = arr[i-K];}else{End[find] = arr[i-K];}}printf("%d", ans);
}

相关文章:

算法【最长递增子序列问题与扩展】

本文讲解最长递增子序列以及最长不下降子序列的最优解&#xff0c;以及一些扩展题目。本文中讲述的是最优解&#xff0c;时间复杂度是O(n*logn)&#xff0c;空间复杂度O(n)&#xff0c;好实现、理解难度不大。这个问题也可以用线段树来求解&#xff0c;时间和空间复杂度和本节讲…...

k8s篇之flannel网络模型详解

在 Kubernetes (K8s) 中,Flannel 是一种常用的网络插件,用于实现容器之间的网络通信。Flannel 提供了一种覆盖网络(Overlay Network)模型,使得容器可以跨多个主机进行通信。 以下是 Flannel 在 Kubernetes 中的详细工作原理和覆盖网络模型的详解: 1.Flannel 简介 Flann…...

windows 和 linux检查操作系统基本信息

windows检查操作系统基本信息 systeminfolinux检查操作系统基本信息 获取系统位数 getconf LONG_BIT查询操作系统release信息 lsb_release -a查询系统信息 cat /etc/issue查询系统名称 uname -a...

Oracle OCP认证考试考点详解082系列22

题记&#xff1a; 本系列主要讲解Oracle OCP认证考试考点&#xff08;题目&#xff09;&#xff0c;适用于19C/21C,跟着学OCP考试必过。 105. 第105题&#xff1a; 题目 解析及答案&#xff1a; 题目翻译&#xff1a; 关于Oracle数据库中的事务请选择两个正确的陈述&#xf…...

线性回归 - 最小二乘法

线性回归 一 简单的线性回归应用 webrtc中的音视频同步。Sender Report数据包 NTP Timestamp&#xff08;网络时间协议时间戳&#xff09;&#xff1a;这是一个64位的时间戳&#xff0c;记录着发送SR的NTP时间戳&#xff0c;用于同步不同源之间的时间。RTP Timestamp&#xff1…...

Linux - 线程基础

文章目录 1.什么是线程2.线程vs进程3.线程调度4.线程控制4.1 POSIX线程库4.2创建线程4.3线程终止4.4线程等待4.5线程分离 5、线程封装 1.什么是线程 在Linux操作系统中&#xff0c;线程是进程内部的一个执行流。在Linux操作系统下&#xff0c;执行流统称为轻量级进程&#xff0…...

网络爬虫——分布式爬虫架构

分布式爬虫在现代大数据采集中是不可或缺的一部分。随着互联网信息量的爆炸性增长&#xff0c;单机爬虫在性能、效率和稳定性上都面临巨大的挑战。分布式爬虫通过任务分发、多节点协作以及结果整合&#xff0c;成为解决大规模数据抓取任务的核心手段。 本节将从 Scrapy 框架的…...

RT_Thread内核源码分析(三)——线程

目录 1. 线程结构 2. 线程创建 2.1 静态线程创建 2.2 动态线程创建 2.3 源码分析 2.4 线程内存结构 3. 线程状态 3.1 线程状态分类 3.2 就绪状态和运行态 3.3 阻塞/挂起状态 3.3.1 阻塞工况 3.4 关闭状态 3.4.1 线程关闭接口 3.4.2 静态线程关闭 3.4.3 动态线程关…...

正排索引和倒排索引

一、简介 正排索引&#xff1a;一个未经处理的数据库中&#xff0c;一般是以文档ID作为索引&#xff0c;以文档内容作为记录。 倒排索引&#xff1a;Inverted index&#xff0c;指的是将单词或记录作为索引&#xff0c;将文档ID作为记录&#xff0c;这样便可以方便地通过单词或…...

丹摩 | 重返丹摩(上)

目录 一.登录平台 二. 数据管理与预处理 1.数据清洗 2.数据格式转换 3.特征工程 二.数据可视化 1.快速可视化 2.数据洞察 3.自定义视图 三.技术支持与帮助 1.技术支持 (1). 帮助文档 (2). 用户社区 2.客服支持 (1). 在线客服 (2). 反馈与建议 总结 一.登录平台…...

Frontend - 防止多次请求,避免重复请求

目录 一、避免重复执行的多种情况 &#xff08;一&#xff09;根据用途 &#xff08;二&#xff09;根据用户操作 二、具体实现 &#xff08;一&#xff09;“Ajax ”结合disabled (防止多次请求)&#xff0c;避免多次点击重复请求 1. 适用场景 2. 解决办法 3. 示例 &…...

RHCE的学习(22)

第四章 流程控制之条件判断 条件判断语句是一种最简单的流程控制语句。该语句使得程序根据不同的条件来执行不同的程序分支。本节将介绍Shell程序设计中的简单的条件判断语句。 if语句语法 单分支结构 # 语法1&#xff1a; if <条件表达式> then指令 fi #语法2&#x…...

【前端知识】简单讲讲什么是微前端

微前端介绍 一、定义二、背景三、核心思想四、基本要素五、核心价值六、实现方式七、应用场景八、挑战与解决方案 什么是single-spa一、核心特点二、核心原理三、应用加载流程四、最佳实践五、优缺点六、应用场景 什么是 qiankun一、概述二、特点与优势三、核心功能四、使用场景…...

AWS IAM

一、介绍 1、简介 AWS Identity and Access Management (IAM) 是 Amazon Web Services 提供的一项服务,用于管理 AWS 资源的访问权限。通过 IAM,可以安全地控制用户、组和角色对 AWS 服务和资源的访问权限。IAM 是 AWS 安全模型的核心组成部分,确保只有经过授权的用户和应…...

丹摩|丹摩助力selenium实现大麦网抢票

丹摩&#xff5c;丹摩助力selenium实现大麦网抢票 声明&#xff1a;非广告&#xff0c;为用户体验 1.引言 在人工智能飞速发展的今天&#xff0c;丹摩智算平台&#xff08;DAMODEL&#xff09;以其卓越的AI算力服务脱颖而出&#xff0c;为开发者提供了一个简化AI开发流程的强…...

基于Qt/C++/Opencv实现的一个视频中二维码解析软件

本文详细讲解了如何利用 Qt 和 OpenCV 实现一个可从视频和图片中检测二维码的软件。代码实现了视频解码、多线程处理和界面更新等功能&#xff0c;是一个典型的跨线程图像处理项目。以下分模块对代码进行解析。 一、项目的整体结构 项目分为以下几部分&#xff1a; 主窗口 (M…...

智慧理财项目测试文档

目录 幕布思维导图链接&#xff1a;https://www.mubu.com/doc/6xk3c7DzgFs学习链接&#xff1a;https://www.bilibili.com/video/BV15J4m147vZ/?spm_id_from333.999.0.0&vd_source078d5d025b9cb472d70d8fda1a7dc5a6智慧理财项目测试文档项目介绍项目基本信息项目业务特性系…...

R | 统一栅格数据的坐标系、分辨率和行列号

各位同学&#xff0c;在做相关性等分析时&#xff0c;经常会遇到各栅格数据间的行列号不统一等问题&#xff0c;下面的代码能直接解决这类麻烦。以某个栅格数据的坐标系、分辨率和行列号为准&#xff0c;统一文件夹内所有栅格并输出到新的文件夹。 代码只需要更改输入输出和ti…...

C++学习——编译的过程

编译的过程——预处理 引言预处理包含头文件宏定义指令条件编译 编译、链接 引言 C程序编译的过程&#xff1a;预处理 -> 编译&#xff08;优化、汇编&#xff09;-> 链接 编译和链接的内容可以查阅这篇文章&#xff08;点击查看&#xff09; 预处理 编译预处理是指&a…...

当你要改文件 但是原来的文件内容又不能丢失的时候,拷贝一份(备注原来的),然后添加后缀:.bak

当你要改文件 但是原来的文件内容又不能丢失的时候&#xff0c;拷贝一份&#xff08;备注原来的&#xff09;&#xff0c;然后添加后缀&#xff1a;.bak &#xff01;&#xff01;&#xff01;文件不要直接删除&#xff0c;若你以后要还原的话会找不到...

MATLAB神经网络(五)——R-CNN视觉检测

5.1 目标分类、检测与分割 在计算机视觉领域&#xff0c;目标分类、检测与分割是常用计数。三者的联系与区分又在哪呢&#xff1f;目标分类是解决图像中的物体是什么的问题&#xff1b;目标检测是解决图像中的物体是什么&#xff0c;在哪里的问题&#xff1b;目标分割时将目标和…...

mock.js:定义、应用场景、安装、配置、使用

前言&#xff1a;什么是mock.js&#xff1f; 作为一个前端程序员&#xff0c;没有mockjs你不感觉很被动吗&#xff1f;你不感觉你的命脉被后端那个男人掌握了吗&#xff1f;所以&#xff0c;我命由我不由天&#xff01;学学mock.js吧&#xff01; mock.js 是一个用于生成随机…...

【GAT】 代码详解 (1) 运行方法【pytorch】可运行版本

GRAPH ATTENTION NETWORKS 代码详解 前言0.引言1. 环境配置2. 代码的运行2.1 报错处理2.2 运行结果展示 3.总结 前言 在前文中&#xff0c;我们已经深入探讨了图卷积神经网络和图注意力网络的理论基础。还没看的同学点这里补习下。接下来&#xff0c;将开启一个新的阶段&#…...

Transformer中的Self-Attention机制如何自然地适应于目标检测任务

Transformer中的Self-Attention机制如何自然地适应于目标检测任务&#xff1a; 特征图的降维与重塑 首先&#xff0c;Backbone&#xff08;如ResNet、VGG等&#xff09;会输出一个特征图&#xff0c;这个特征图通常具有较高的通道数、高度和宽度&#xff08;例如CHW&#xff…...

2411rust,1.75.0

原文 Rust团队很高兴地声明推出Rust的新版本1.75.0. 如果你rustup安装了以前版本的Rust,你可如下取1.75.0: $ rustup update stable1.75.0稳定版中的功能 async fn和特征中的返回位置impl Trait. 指针字节偏移API 原始指针(*const T和*mutT)过去主要支持,T为单位的操作.如…...

远程办公新宠:分享8款知识共享软件

远程办公模式下&#xff0c;知识共享软件成为了团队协作和沟通的重要工具。以下是8款备受推崇的知识共享软件&#xff1a; 1、HelpLook AI知识库 简介&#xff1a;HelpLook是一款快速搭建AI知识库的系统&#xff0c;具备强大功能&#xff0c;如快速精准的知识检索、灵活定制的…...

3.9MayBeSomeAssembly

就是先从数组里&#xff0c;乘4得到正确地址 32&#xff08;&s3),s3是基址&#xff0c;32是偏移量&#xff0c;就是先从数组里取出数到临时寄存器&#xff0c;然后再在临时寄存器上加上变量&#xff0c;最后再把临时寄存器上的变量存到数组里&#xff0c;偏移量&#xff0…...

i春秋-签到题

练习平台地址 竞赛中心 题目描述 题目内容 点击GUESS后会有辨识细菌的选择题 全部完成后会有弹窗提示 输入nickname后提示获得flag F12检查 元素中没有发现信息 检查后发现flag在控制台中 flag flag{663a5c95-3050-4c3a-bb6e-bc4f2fb6c32e} 注意事项 flag不一定要在元素中找&a…...

TypeScript 中扩展现有模块的用法

declare module 是 TypeScript 中用于扩展现有模块的特性。它允许开发者在已有模块的基础上&#xff0c;添加新的功能&#xff08;比如扩展接口、添加类型声明等&#xff09;。通过 declare module&#xff0c;可以将额外的声明合并到原模块中。以下是用法详解&#xff1a; 用…...

【报错记录】解决Termux中pulseaudio启动报错,报:E: [pulseaudio] main.c: Daemon startup failed.

前言 在尝试使用Termux-X11启动Minecraft过程中&#xff0c;不知道怎么回事原本好好的pulseaudio居然无法启动了&#xff0c;一直在报&#xff1a; E: [pulseaudio] main.c: Daemon startup failed. 重装了好几次也没用解决方案如下。 排除重复启动 如果pulseaudio之前已经…...