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

LC1713. 得到子序列的最少操作次数(java - 动态规划)

LC1713. 得到子序列的最少操作次数

  • 题目描述
    • LIS 动态规划 + 二分法
    • 代码演示

题目描述

难度 - 困难
LC1713.得到子序列的最少操作次数

给你一个数组 target ,包含若干 互不相同 的整数,以及另一个整数数组 arr ,arr 可能 包含重复元素。
每一次操作中,你可以在 arr 的任意位置插入任一整数。比方说,如果 arr = [1,4,1,2] ,那么你可以在中间添加 3 得到 [1,4,3,1,2] 。你可以在数组最开始或最后面添加整数。
请你返回 最少 操作次数,使得 target 成为 arr 的一个子序列。
一个数组的 子序列 指的是删除原数组的某些元素(可能一个元素都不删除),同时不改变其余元素的相对顺序得到的数组。比方说,[2,7,4] 是 [4,2,3,7,2,1,4] 的子序列(加粗元素),但 [2,4,2] 不是子序列。

示例 1:
输入:target = [5,1,3], arr = [9,4,2,3,4]
输出:2
解释:你可以添加 5 和 1 ,使得 arr 变为 [5,9,4,1,2,3,4] ,target 为 arr 的子序列。

示例 2:
输入:target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
输出:3

提示:
1 <= target.length, arr.length <= 10^5
1 <= target[i], arr[i] <= 10^9
target 不包含任何重复元素。
在这里插入图片描述

LIS 动态规划 + 二分法

为了方便,我们令 target 长度为 n,arr 长度为 m,target 和 arr 的最长公共子序列长度为 max,不难发现最终答案为 n−max。
因此从题面来说,这是一道最长公共子序列问题(LCS)。
但朴素求解 LCS 问题复杂度为 O(n∗m),使用状态定义「f[i][j] 为考虑 a 数组的前 i 个元素和 b 数组的前 j 个元素的最长公共子序列长度为多少」进行求解。
而本题的数据范围为 10^5,使用朴素求解 LCS 的做法必然超时。
一个很显眼的切入点是 target 数组元素各不相同,当 LCS 问题增加某些条件限制之后,会存在一些很有趣的性质。
其中一个经典的性质就是:当其中一个数组元素各不相同时,最长公共子序列问题(LCS)可以转换为最长上升子序列问题(LIS)进行求解。同时最长上升子序列问题(LIS)存在使用「维护单调序列 + 二分」的贪心解法,复杂度为 O(nlog⁡n)。
因此本题可以通过「抽象成 LCS 问题」->「利用 target数组元素各不相同,转换为 LIS 问题」->「使用 LIS 的贪心解法」,做到 O(nlog⁡n) 的复杂度。

朴素的 LIS 问题求解,我们需要定义一个 f[i] 数组代表以 nums[i] 为结尾的最长上升子序列的长度为多少。
对于某个 f[i] 而言,我们需要往回检查 [0,i−1] 区间内,所有可以将 nums[i] 接到后面的位置 jjj,在所有的 f[j]+1中取最大值更新 f[i]。因此朴素的 LIS 问题复杂度是 O(n^2) 的。
LIS 的贪心解法则是维护一个额外 ggg 数组,g[len]=x 代表上升子序列长度为 lenlenlen 的上升子序列的「最小结尾元素」为 x。
整理一下,我们总共有两个数组:

  1. f 动规数组:与朴素 LIS 解法的动规数组含义一致。f[i]f[i]f[i] 代表以 nums[i] 为结尾的上升子序列的最大长度;
  2. g 贪心数组:g[len]=x代表上升子序列长度为 len 的上升子序列的「最小结尾元素」为 x。

由于我们计算 f[i] 时,需要找到满足 nums[j]<nums[i],同时取得最大 f[j] 的位置 j。

我们期望通过 g 数组代替线性遍历。
显然,如果 g 数组具有「单调递增」特性的话,我们可以通过「二分」找到符合 g[idx]<nums[i] 分割点 idxi(下标最大),即利用 O(log⁡n) 复杂度找到最佳转移位置。

代码演示

class Solution {public int minOperations(int[] target , int[] arr) {Map<Integer, Integer> map = new HashMap();int Tlen = target.length, Alen = arr.length;//1:target的元素和对应下标 装入mapfor(int i = 0; i < Tlen; i++) map.put(target[i], i);//2:在arr中寻找相等的值的下标装入下标数组int[] index = new int[Alen];int p = 0;for(int i = 0; i < Alen; i++){if(map.containsKey(arr[i])) index[p++] = map.get(arr[i]);}//3:直接调用处理最长递增公共子串代码(之前做过,这里赋值过来,偷懒)int uplen = lengthOfLIS(index,p);return Tlen - uplen;}public int lengthOfLIS(int[] nums,int n){if(n == 0) return 0;int res = 1;int[] dp = new int[n];dp[0] = nums[0];for(int num:nums){int i = 0,j = res;while(i < j){int mid = (i + j)>>1;if(dp[mid] >= num) j = mid;else i = mid + 1;}dp[i] = num;if(j == res) res++;}return res;}}

相关文章:

LC1713. 得到子序列的最少操作次数(java - 动态规划)

LC1713. 得到子序列的最少操作次数 题目描述LIS 动态规划 二分法代码演示 题目描述 难度 - 困难 LC1713.得到子序列的最少操作次数 给你一个数组 target &#xff0c;包含若干 互不相同 的整数&#xff0c;以及另一个整数数组 arr &#xff0c;arr 可能 包含重复元素。 每一次…...

vr飞机驾驶舱模拟流程3D仿真演示加大航飞安全法码

众所周知&#xff0c;航空航天飞行是一项耗资大、变量参数很多、非常复杂的系统工程&#xff0c;因此可利用虚拟仿真技术经济、安全及可重复性等特点&#xff0c;进行飞行任务或操作的模拟&#xff0c;以代替某些费时、费力、费钱的真实试验或者真实试验无法开展的场合&#xf…...

一、八大排序(sort)

文章目录 一、时间复杂度&#xff08;一&#xff09;定义&#xff1a;常数操作 二、空间复杂度&#xff08;一&#xff09;定义&#xff1a; 三、排序&#xff08;一&#xff09;选择排序1.定义2.代码3.特性 &#xff08;二&#xff09;冒泡排序1.定义2.代码3.特性 &#xff08…...

【AWS】AI 代码生成器—Amazon CodeWhisperer初体验 | 开启开挂编程之旅

使用 AI 编码配套应用程序更快、更安全地构建应用程序 文章目录 1.1 Amazon CodeWhisperper简介1.2 Amazon CodeWhisperer 定价2.1 打开VS Code2.2 安装AWS ToolKit插件 一、前言 1.1 Amazon CodeWhisperper简介 1️⃣更快地完成更多工作 CodeWhisperer 经过数十亿行代码的训…...

【Mysql主从配置方法---单主从】

Mysql主从 主服务器 创建用户 create user “for_rep”“从服务器IP地址” IDENTIFIED by “123456” 授权 grant replication slave on . to “for_rep”“从服务器IP地址” IDENTIFIED by “123456” 查看用户权限 SHOW GRANTS FOR “for_rep”“从服务器IP地址”; 修改M…...

⼀⽂读懂加密资产交易赛道的新锐⼒量Bitdu

交易所&#xff0c;仍然是加密资产赛道的皇冠级赛道。围绕这个领域展开的商业竞争&#xff0c;最能引起⼴⼤⽤⼾的关注。 经历了数轮资产价格涨跌的⽜熊之后&#xff0c;⼀批批创业者也在不断地思考这⼀议题 — 如何在去中⼼化的世界中&#xff0c;最⾼效率地集结流量、资本和…...

万里牛与金蝶云星空对接集成查询调拨单连通调拨单新增(万里牛调拨单-金蝶【直接调拨单】)

万里牛与金蝶云星空对接集成查询调拨单连通调拨单新增(万里牛调拨单-金蝶【直接调拨单】) 源系统:万里牛 万里牛是杭州湖畔网络技术有限公司旗下SaaS软件品牌&#xff0c;主要针对电商、外贸、实体门店等业务群体&#xff0c;帮助企业快速布局新零售&#xff0c;提升订单处理效…...

虚拟DOM与diff算法

虚拟DOM与diff算法 snabbdom虚拟DOMdiff算法 snabbdom 是什么&#xff1a;snabbdom是著名的虚拟DOM库&#xff0c;是diff算法的鼻祖&#xff0c;Vue源码借鉴了snabbdom 虚拟DOM 是什么&#xff1a;本质上是存在内存里的 JavaScript 对象 作用&#xff1a;用来描述真实DOM的层…...

K8S:pod资源限制及探针

文章目录 一.pod资源限制1.pod资源限制方式2.pod资源限制指定时指定的参数&#xff08;1&#xff09;request 资源&#xff08;2&#xff09; limit 资源&#xff08;3&#xff09;两种资源匹配方式 3.资源限制的示例&#xff08;1&#xff09;官网示例&#xff08;2&#xff0…...

CSS中的定位

position 的属性与含义 CSS 中的 position 属性用于控制元素在页面中的定位方式&#xff0c;有四个主要的取值&#xff0c;每个取值都会影响元素的布局方式&#xff0c;它们是&#xff1a; static&#xff08;默认值&#xff09;&#xff1a; 这是所有元素的初始定位方式。在静…...

二、链表(linked-list)

文章目录 一、定义二、经典例题&#xff08;一&#xff09;[21.合并两个有序链表](https://leetcode.cn/problems/merge-two-sorted-lists/description/)1.思路2.复杂度分析3.注意4.代码 &#xff08;二&#xff09;[86.分割链表](https://leetcode.cn/problems/partition-list…...

Android EditText筛选+选择功能开发

在日常开发中经常会遇到这种需求&#xff0c;EditText既需要可以筛选&#xff0c;又可以点击选择。这里筛选功能用的是AutoCompleteTextView&#xff0c;选择功能使用的是第三方库https://github.com/kongzue/DialogX。 Android AutoCompleteTextView(自动完成文本框)的基本使用…...

Linux 信号 alarm函数 setitimer函数

/*#include <unistd.h>unsigned int alarm(unsigned int seconds);功能&#xff1a;设置定时器。函数调用&#xff0c;开始倒计时&#xff0c;0的时候给当前的进程发送SIGALARM信号参数&#xff1a;倒计时的时长。。单位&#xff1a;秒 如果参数为0&#xff0c;无效返回…...

自主设计,模拟实现 RabbitMQ - 实现发送方消息确认机制

目录 一、实现发送方消息确认 1.1、需求分析 什么是发送方的消息确认? 如何实现?...

【数据结构】二叉树的·深度优先遍历(前中后序遍历)and·广度优先(层序遍历)

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …...

优彩云采集器下载-免费优彩云采集器下载地址

免费优彩云采集器。您是否曾为了数据采集而感到头疼不已&#xff1f;是否一直在寻找一种能够轻松、高效地获取所需数据的方法&#xff1f;别着急&#xff0c;让我们一起来了解如何通过优彩云采集器解决这些问题&#xff0c;从而让您产生购买的欲望。 免费全自动采集发布批量管理…...

【Python】OJ 常用函数

这里写目录标题 一. math1. 求阶乘 - factorial()2. 绝对值 - fabs() 二. 容器的方法1. reverse() 三. Python 内置函数1. sort() 一. math 需要引入 math 包&#xff1a;import math 1. 求阶乘 - factorial() import math print(math.factorial(5))--------运行结果-------…...

【Vue】上万个字把事件处理讲解的淋漓尽致

hello&#xff0c;我是小索奇&#xff0c;精心制作的Vue系列教程持续更新哈&#xff0c;想要学习&巩固&避坑就一起学习吧~ 事件处理 事件的基本用法 重点内容 使用v-on:xxx缩写xxx绑定事件&#xff0c;其中 xxx 是事件名&#xff08;回顾&#xff1a;v-bind缩写为冒号…...

Remmina中VNC、SSH和RDP的区别

Remmina 可以在 Linux 系统上对远程进行连接。它支持多种远程连接协议&#xff0c;包括 VNC&#xff08;Virtual Network Computing&#xff09;、SSH&#xff08;Secure Shell&#xff09;和 RDP&#xff08;Remote Desktop Protocol&#xff09;。这些协议用于实现不同类型的…...

Spring Boot实现web.xml功能

Spring Boot实现web.xml功能 1. 基于注解实现1.1 组件注册1.2 WebInitParam注解 2. 基于编码实现2.1 Servlet & Filter2.2 Listener 3. 总结 在Spring Boot中&#xff0c;不再需要使用传统的 web.xml 文件来配置web应用的功能&#xff0c;Spring Boot支持通过注解和基于代码…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

rknn toolkit2搭建和推理

安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 &#xff0c;不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源&#xff08;最常用&#xff09; conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...