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

【动态规划-最长递增子序列(LIS)】力扣2826. 将三个组排序

给你一个整数数组 nums 。nums 的每个元素是 1,2 或 3。在每次操作中,你可以删除 nums 中的一个元素。返回使 nums 成为 非递减 顺序所需操作数的 最小值。

示例 1:
输入:nums = [2,1,3,2,1]
输出:3
解释:
其中一个最优方案是删除 nums[0],nums[2] 和 nums[3]。

示例 2:
输入:nums = [1,3,2,1,3,3]
输出:2
解释:
其中一个最优方案是删除 nums[1] 和 nums[2]。

示例 3:
输入:nums = [2,2,2,2,3,3]
输出:0
解释:
nums 已是非递减顺序的。

提示:
1 <= nums.length <= 100
1 <= nums[i] <= 3

动态规划

class Solution {
public:int minimumOperations(vector<int>& nums) {int n = nums.size();vector<int> g;for(int x : nums){auto it = ranges::upper_bound(g, x);if(it == g.end()) g.push_back(x);else *it = x;}return nums.size() - g.size();}
};

时间复杂度:O(nlogn),其中 n 为 nums 的长度。
空间复杂度:O(n)。

这个采用了c++的内置函数upper_bound,对于每个nums元素x,使用二分查找动态数组g来查找比x大且最接近x的位置,然后用迭代器it指向这个位置。

如果迭代器it指向了g.end(),那么就说明g中没有比x大的元素,那么x就可以push到g里面来构成一个更长的虚拟递增子序列。为什么是虚拟,下面我会谈到。如果it指向g中的某个位置,那么就用x替换掉那个元素,因为对于被替换的元素的前一个元素,肯定比x要小,且被替换的元素大于x,所以说x与被替换元素的上一个元素的值会更加接近,在构造最长递增子序列过程中,我们希望在长度相同的情况下,尽可能让这个虚拟序列更加接近。

为什么说g里面是个虚拟的递增子序列,不是真正的子序列。因为我们在用x替换g里面的元素的时候,由于x在nums中的位置肯定都要比g中所有元素都要大,所以替换过去后,并不会马上构成一个最长递增子序列。什么时候会构成真正的递增子序列?那就是在被替换的元素是g里面最后一个元素的时候,这时候虚拟的递增子序列才会变成真正的子序列。

举个例子:nums = [1,2,4,5,3,7,4,6]
一开始我们得到g=[1,2,4,5],然后遇到x=3,替换后g=[1,2,3,5],这时候g就是虚拟的递增子序列,因为很明显nums中没有这么一个递增子序列。接着遇到x=7,推入g,g=[1,2,3,5,7]。接着遇到x=4,替换掉g中的5,g=[1,2,3,4,7]。最后遇到x=6,替换掉了g中的最后一个元素7,g=[1,2,3,4,6],这时候我们的最长子序列才真正变成了[1,2,3,4,6]。

知道了最长递增子序列的长度后,我们用nums的大小减去g的大小,就是我们需要删除操作的次数。

这道题可以用状态机DP来进行优化时间复杂度为O(n)

相关文章:

【动态规划-最长递增子序列(LIS)】力扣2826. 将三个组排序

给你一个整数数组 nums 。nums 的每个元素是 1&#xff0c;2 或 3。在每次操作中&#xff0c;你可以删除 nums 中的一个元素。返回使 nums 成为 非递减 顺序所需操作数的 最小值。 示例 1&#xff1a; 输入&#xff1a;nums [2,1,3,2,1] 输出&#xff1a;3 解释&#xff1a; …...

Elastic Stack--16--ES三种分页策略

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 方式一&#xff1a;from size实现原理使用方式优缺点 方式二&#xff1a;scroll实现原理使用方式优缺点 方式三&#xff1a;search_after实现原理使用方式优缺点 三…...

[LeetCode] 315. 计算右侧小于当前元素的个数

题目描述&#xff1a; 给你一个整数数组 nums &#xff0c;按要求返回一个新数组 counts 。数组 counts 有该性质&#xff1a; counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。 题目链接&#xff1a; . - 力扣&#xff08;LeetCode&#xff09; 题目主要思路&a…...

【hot100-java】二叉树展开为链表

二叉树篇。 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* …...

如何在在 YOLOv3模型中添加Attention机制

在YOLOv3模型中添加Attention机制需要以下几个步骤&#xff1a; 1. 规定格式 当添加新的模块&#xff08;如Attention机制模块&#xff09;时&#xff0c;需要像定义[convolutional]、[maxpool]等层在cfg文件中的格式一样&#xff0c;对新模块进行格式规定。例如对于SE模块&a…...

单点登录Apereo CAS 7.1安装配置教程

笔者目前正在做一个单点登录的课题,历时较长总算摸到一些门路,其中的辛酸不易按下不表。截至本文发布,CAS的最新版本为7.1。由于涉及到课题内容,而且内容比较新,整理试验不容易,暂时只对VIP开放,后续课题完成后会完全开放,敬请谅解。 CAS项目区别 在CAS的项目选择上,…...

windows C++-移除界面工作线程(一)

本文档演示了如何使用并发运行时将 Microsoft 基础类 (MFC) 应用程序中由用户界面 (UI) 线程执行的工作移动到工作线程。 本文档还演示了如何提高冗长绘制操作的性能。 通过将阻塞性操作&#xff08;例如&#xff0c;绘制&#xff09;卸载到工作线程来从 UI 线程中移除工作&am…...

Qt小bug — LINK : fatal error LNK1158: 无法运行“rc.exe“

Qt小bug —— LINK &#xff1a;fatal error LNK1158&#xff1a;无法运行"rc.exe" 环境 Qt 5.14.2 MSVC 2015 x64 现象 解决 在电脑上找到rc.exe 和rcdll.dll &#xff08;一般在C:\Program Files(x86)\Windows Kits*\bin\x64下面&#xff09;拷贝到 C:\Qt\Qt5…...

c++小游戏

目录 狼人杀 走迷宫 炸弹人 贪吃蛇 飞翔的小鸟 跑酷 吃豆人 飞机大战 人生模拟器 坦克大战 修仙模拟器 搜集了一些小游戏&#xff0c;名字下是个人是个人喜欢度&#xff0c;可供参考~ 狼人杀 ❤❤❤❤ #include<bits/stdc.h> #include<cstdio> #incl…...

k8s为什么用Calico

‌Calico是一种开源的网络和安全解决方案&#xff0c;主要用于容器、虚拟机、宿主机之间的网络连接。‌ 它支持Kubernetes、OpenShift、Docker EE、OpenStack等PaaS或IaaS平台&#xff0c;提供高效的网络通信和安全控制功能‌12。 Calico的核心组件包括Felix、etcd、BIRD等。F…...

HashMap 和 Hashtable 有什么区别?

HashMap和Hashtable都是Java中常用的存储键值对的集合类&#xff0c;它们都实现了Map接口&#xff0c;但二者之间存在一些显著的区别。以下是对HashMap和Hashtable区别的详细归纳&#xff1a; 一、线程安全性 HashMap&#xff1a;是非线程安全的&#xff0c;即多个线程可以同…...

【机器学习】深度学习、强化学习和深度强化学习?

深度学习、强化学习和深度强化学习是机器学习的三个重要子领域。它们有着各自独特的应用场景和研究目标&#xff0c;虽然都属于机器学习的范畴&#xff0c;但各自的实现方式和侧重点有所不同。 1. 深度学习&#xff08;Deep Learning&#xff09; 深度学习是一种基于神经网络的…...

fastadmin 多商户模式下侧边栏跳转路径BUG

记录&#xff1a;仅作自己项目记录&#xff0c;在一个域名下部署多套项目时&#xff0c;若不是多商户模式项目会出现跳转路径问题。 修改 \manystore\library\Auth.php 文件的 getSidebar 方法 // 1 改为&#xff1a; $v[url] isset($v[url]) && $v[url] ? $v[url]…...

java内置的四种函数式接口

供给型&#xff1a;Supplier 无入参&#xff0c;有返回值。 FunctionalInterface public interface Supplier<T> {T get();}消费型&#xff1a;Consumer 有入参&#xff0c;无返回值。 FunctionalInterface public interface Consumer<T> {void accept(T t);de…...

如何获取 uni-app 应用发布所需的证书、私钥与配置文件

引言 在开发和发布iOS应用时&#xff0c;开发者常常会面临一系列复杂的证书、私钥密码以及配置文件的管理问题。这些配置不仅影响到应用的开发调试&#xff0c;还决定了应用是否能够顺利通过审核并发布到App Store。对于使用uni-app进行开发的开发者来说&#xff0c;自动生成的…...

TCP网络通信——多线程

前面分别用多进程和多路复用完成了TCP网络通信&#xff0c;本文就来讲讲多线程的TCP通信。首先来了解一下线程的概念&#xff1a; 1、线程是进程的执行路线&#xff0c;它是进程内部的控制序列&#xff0c;或者说线程是进程的一部分(进程是一个资源单位&#xff0c;线程是执行单…...

【exp报错注入】

整数范围 最大整数 exp 函数介绍 报错盲注注入 payload分析 709C-ASCII 值就等于我们下面的 7091-1 &#xff0c;C就是我们要猜的值&#xff0c;当我们猜测的值和ASCII码相等时&#xff0c;那么exp就不会出现报错&#xff0c;因为1-1还是等于709&#xff1a; 练习 id1 an…...

基于SpringBoot问卷调查系统小程序【附源码】

基于SpringBoot问卷调查系统小程序 效果如下&#xff1a; 管理员登录界面 管理员功能界面 调查人管理界面 问卷调查管理界面 问卷题目管理界面 用户登录界面 APP首页界面 公告信息界面 研究背景 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&…...

LLM - 配置 GraphRAG + Ollama 服务 构建 中文知识图谱

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/142795151 免责声明&#xff1a;本文来源于个人知识与公开资料&#xff0c;仅用于学术交流&#xff0c;欢迎讨论&#xff0c;不支持转载。 GraphR…...

简单认识redis - 6 redis 存储速度快的原因

1基于内存存储 缓存&#xff08;内存&#xff09;读写速度很快&#xff0c;相比于磁盘存储的Mysql 省去了磁盘I/O的次数。 2.高效的数据结构 SDS动态字符串&#xff1a; 1.字符串长度处理&#xff1a;Redis获取字符串长度&#xff0c;时间复杂度为O(1)&#xff0c;而C语言中&am…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...