每日一练 2024.5.16(补 2024.5.14)

题目;

我们定义 arr 是 山形数组 当且仅当它满足:

  • arr.length >= 3
  • 存在某个下标 i (从 0 开始) 满足 0 < i < arr.length - 1 且:
    • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
    • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给你整数数组 nums​ ,请你返回将 nums 变成 山形状数组 的​ 最少 删除次数。

示例 1:

输入:nums = [1,3,1]
输出:0
解释:数组本身就是山形数组,所以我们不需要删除任何元素。

示例 2:

输入:nums = [2,1,1,5,6,2,3,1]
输出:3
解释:一种方法是将下标为 0,1 和 5 的元素删除,剩余元素为 [1,5,6,3,1] ,是山形数组。

提示:

  • 3 <= nums.length <= 1000
  • 1 <= nums[i] <= 109
  • 题目保证 nums 删除一些元素后一定能得到山形数组。
解题:
  1. 解决这个问题的关键在于理解如何利用动态规划(DP)来找到任意一个元素作为山顶时的最长山形子序列。这一过程可以分解为几个步骤:

  2. 定义状态

    • 我们维护两个DP数组来记录状态,即lis[i]lds[i]
      • lis[i]代表以nums[i]结尾的最长上升子序列的长度(Longest Increasing Subsequence, LIS)。
      • lds[i]代表从nums[i]开始的最长下降子序列的长度(Longest Decreasing Subsequence, LDS)。
  3. 状态转移

    • 对于lis[i],我们通过比较nums[i]与其之前的元素nums[j]j < i)来更新lis[i]的值。
    • 对于lds[i],我们通过比较nums[i]与其之后的元素nums[j]j > i)来更新lds[i]的值。
  4. 合并上升和下降序列

    • 一旦我们有了每个元素为山顶时的上升和下降序列长度,我们就可以找到以该元素为山顶时的最长山形序列的长度,即lis[i] + lds[i] - 1(因为山顶元素被计算了两次,需减去1)。
  5. 找到最长的山形子序列

    • 遍历所有元素,利用上述方法计算以每个元素为山顶的最长山形序列长度,取最大值maxLength
  6. 计算最小删除次数

    • 最后,用数组总长减去maxLength,即得到了得到山形数组的最少删除次数。

计算LIS:

for (int i = 0; i < n; i++) {lis[i] = 1;for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {lis[i] = Math.max(lis[i], lis[j] + 1);}}
}

计算LDS:

for (int i = n - 1; i >= 0; i--) {lds[i] = 1;for (int j = n - 1; j > i; j--) {if (nums[i] > nums[j]) {lds[i] = Math.max(lds[i], lds[j] + 1);}}
}

找出最长的山形子序列并计算需要删除的元素数量:

int maxLength = 0;
for (int i = 0; i < n; i++) {if (lis[i] > 1 && lds[i] > 1) {maxLength = Math.max(maxLength, lis[i] + lds[i] - 1);}
}
return n - maxLength;
代码:
public class Solution {public int minimumMountainRemovals(int[] nums) {int n = nums.length;int[] lis = new int[n];int[] lds = new int[n];// 计算 LISfor (int i = 0; i < n; i++) {lis[i] = 1;for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {lis[i] = Math.max(lis[i], lis[j] + 1);}}}// 计算 LDSfor (int i = n - 1; i >= 0; i--) {lds[i] = 1;for (int j = n - 1; j > i; j--) {if (nums[i] > nums[j]) {lds[i] = Math.max(lds[i], lds[j] + 1);}}}// 找出最长的山形子序列int maxLength = 0;for (int i = 0; i < n; i++) {if (lis[i] > 1 && lds[i] > 1) {maxLength = Math.max(maxLength, lis[i] + lds[i] - 1);}}// 返回需要删除的元素数量return n - maxLength;}
}
知识点解析:
  1. 动态规划(Dynamic Programming, DP):利用过去计算的结果来帮助解决后续的子问题,从而避免重复计算。这是解题的核心思想,通过分别计算最长上升子序列(LIS)和最长下降子序列(LDS)来找到最长的山形子序列。

  2. 数组操作:利用数组存储中间计算结果(如LIS和LDS的长度),以及最终的结果计算。

  3. 双层循环:用于计算LIS和LDS,内层循环遍历小于当前索引的所有元素,寻找合适的元素更新当前的LIS或LDS值。

  4. 条件判断:在计算LIS和LDS时,需要通过条件判断来确保只有在当前元素大于遍历到的元素时才进行计算。

  5. 数学运算:在各个步骤中用到了基本的数学运算,如最大值Math.max()的计算。

知识点描述应用
动态规划通过解决子问题的方式来解决主问题,避免重复计算。分别计算最长上升子序列(LIS)和最长下降子序列(LDS)。
数组操作使用数组来存储数据和结果。存储LIS和LDS的长度及用于遍历查找的过程中的中间结果。
双层循环使用嵌套循环遍历数组中的元素。在计算LIS和LDS时,内层循环遍历并更新当前索引的LIS或LDS值。
条件判断根据特定条件来执行不同的逻辑。确保在适当的条件下(如要求严格递增/递减)更新LIS和LDS值。
数学运算使用基本的数学运算和函数。使用Math.max()来找到最大的LIS、LDS值,以及计

2024.5.14

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/328908.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【大模型微调】一文掌握7种大模型微调的方法

本篇文章深入分析了大型模型微调的基本理念和多样化技术&#xff0c;细致介绍了LoRA、适配器调整(Adapter Tuning)、前缀调整(Prefix Tuning)等多个微调方法。详细讨论了每一种策略的基本原则、主要优点以及适宜应用场景&#xff0c;使得读者可以依据特定的应用要求和计算资源限…

Vue的学习 —— <vue组件>

目录 前言 正文 一、选项式API与组合式API 二、生命周期函数 1、onBeforeMount() 2、onMounted() 3、onBeforeUpdate() 4、onUpdated() 5、onBeforeUnmount() 6、onUnmounted() 三、组件之间的样式冲突 四、父组件向子组件传递数据 1、定义props 2、静态绑定props…

1709 ssm互联网消费信贷系统myeclipse开发mysql数据库springMVC模式java编程计算机网页设计

一、源码特点 java ssm互联网消费信贷系统是一套完善的web设计系统&#xff08;系统采用SSM框架进行设计开发&#xff0c;springspringMVCmybatis&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源 代码和数据库&#xff0c;系统主要…

淘宝评论api接口的探索与实践

一、淘宝评论api接口简介 淘宝评论api接口是淘宝开放平台提供的一种数据接口&#xff0c;通过该接口&#xff0c;开发者可以获取淘宝商品的评论信息&#xff0c;包括评论内容、评论评分、评论时间等。此接口为开发者提供了丰富的评论数据&#xff0c;便于进行商品评价分析、营…

在 Django 中获取已渲染的 HTML 文本

在Django中&#xff0c;你可以通过多种方式获取已渲染的HTML文本。这通常取决于你希望在哪个阶段获取HTML文本。下面就是我在实际操作中遇到的问题&#xff0c;并且通过我日夜奋斗终于找到解决方案。 1、问题背景 在 Django 中&#xff0c;您可能需要将已渲染的 HTML 文本存储…

图文并茂:解析Spring Boot Controller返回图片的三种方式

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 图文并茂&#xff1a;解析Spring Boot Controller返回图片的三种方式 前言使用Base64编码返回图片使用byte数组返回图片使用Resource对象返回图片图片格式转换与性能对比 前言 在互联网的世界里&…

C# 结合 JavaScript 对 Web 控件进行数据输入验证

目录 关于数据验证 范例运行环境 验证设计 JavaScript 方法 设计 实现 调用示例 C# 方法 设计 实现 调用示例 小结 关于数据验证 在 Web 应用的录入界面&#xff0c;数据验证是一项重要的实现功能&#xff0c;数据验证是指确认 Web 控件输入或选择的数据&#xff…

宁静致远(“静”)

宁静致远是一个成语&#xff0c;读音为nng jng zh yuǎn&#xff0c;意思是只有心境平稳沉着、专心致志&#xff0c;才能厚积薄发、 有所作为。出自《淮南子:主术训》。 出处 宁静致远张铭篆刻 此句最早出自西汉初年道家刘安的《淮南子:主术训》&#xff0c;蜀汉丞相诸葛亮的…

2025秋招Java还是c++?

一、我的编程经 说说我的编程经历&#xff0c;在C和Java之间我经历了几个阶段&#xff1a; 大学期间&#xff0c;我浅尝辄止地学习了一段时间的Java&#xff0c;但后来放弃了&#xff0c;开始学习C/C。本科毕业后&#xff0c;我选择攻读硕士学位&#xff0c;并一直专注于C的学…

美团小程序mtgsig1.2逆向

声明 本文章中所有内容仅供学习交流使用&#xff0c;不用于其他任何目的&#xff0c;抓包内容、敏感网址、数据接口等均已做脱敏处理&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff01;wx a15018601872 本文章未…

汇编--栈和寄存器

栈 栈是一种运算受限的线性表&#xff0c;其限定仅在表尾进行插入和删除操作的线性表&#xff0c;表尾也被叫做栈顶。简单概括就是我们对于元素的操作只能够在栈顶进行&#xff0c;也造就了其先进后出的结构特性。 栈 这种内存空间其实本质上有两种操作&#xff1a;将数据放入…

C语言如何删除表中指定位置的结点?

一、问题 如何删除链表中指定位置的结点&#xff1f; 二、解答 删除链表中指定的结点&#xff0c;就像是排好队的⼩朋友⼿牵着⼿&#xff0c;将其中⼀个⼩朋友从队伍中分出来&#xff0c;只需将这个⼩朋友的双⼿从两边松开。 删除结点有两种情况&#xff1a; &#xff08;1&am…

CRM与SCRM:联系与区别

引言 在当今数字化时代&#xff0c;企业与客户之间的互动变得日益频繁而复杂。为了更好地管理客户关系并提供更个性化的服务&#xff0c;许多企业采用了客户关系管理&#xff08;CRM&#xff09;系统。与此同时&#xff0c;随着社交媒体的普及和社交化互动的增加&#xff0c;社…

【文末附gpt升级方案】探讨当前时机是否适合进入AIGC行业(一)

随着科技的飞速发展&#xff0c;人工智能生成内容&#xff08;AIGC&#xff09;作为新兴的技术领域&#xff0c;正逐步走进公众的视野&#xff0c;并在多个行业展现出巨大的应用潜力。然而&#xff0c;对于创业者、投资者以及希望进入这一领域的专业人士来说&#xff0c;当前时…

传输层协议——TCP协议

目录 一、TCP协议 二、TCP协议格式 三、序号和确认序号 四、窗口大小 五、六个标记位 六、三次握手和四次挥手 七、滑动窗口 八、拥塞控制 九、延迟应答和捎带应答 1、延迟应答 2、捎带应答 十、面向字节流 十一、粘包问题 十二、TCP异常情况 十三、再谈listen函…

小程序|锁定查询功能如何使用?

学生或家长想要实现自己查询完成后&#xff0c;任何人都无法再次查询&#xff0c;老师应该如何设置&#xff1f;易查分的【锁定查询功能】就可实现&#xff0c;下面教大家如何使用吧。 &#x1f4cc;使用教程 &#x1f512;锁定查询功能介绍 ✅学生或家长自主锁定&#xff1a;开…

实现mysql的主从复制、实现MySQL的读写分离与负载均衡

实验环境 &#xff08;注明&#xff09;以下的所有关于yum和rpm以及tar的软件需要自己准备&#xff0c;没有的话可以私信博主 实验目标&#xff1a; 1.实现mysql主从复制 2.实现mysql读写分离与负载均衡 实验一、搭建mysql主从复制 1.建立时间同步环境&#xff0c;在主节…

Linux-笔记 开发板Uboot命令使用

将之前自学的知识整理了一下笔记&#xff0c;以便回忆 信息查询命令 1、help/?&#xff1a;查看所支持命令 > ? md md - memory displayUsage: md [.b, .w, .l] address [# of objects]2、bdinfo&#xff1a;查询板子信息 > bdinfo arch_number 0x00000000 boot_p…

C#知识|上位机子窗体嵌入主窗体方法(实例)

哈喽,你好啊,我是雷工! 上位机开发中,经常会需要将子窗体嵌入到主窗体, 本节练习C#中在主窗体的某个容器中打开子窗体的方法。 01 需求说明 本节练习将【账号管理】子窗体在主窗体的panelMain容器中打开。 账号管理子窗体如下: 主窗体的panelMain容器位置如图: 02 实现…