LeetCode 2919 使数组变美的最小增量运算数
动态规划解题:最小操作次数使数组变为美丽数组
问题描述
给定一个下标从0开始、长度为n
的整数数组nums
和一个整数k
。你可以对数组中的任意一个元素进行加1操作,操作次数不限。如果数组中任意长度大于或等于3的子数组的最大值都大于或等于k
,则称该数组为美丽数组。我们需要找到使数组变为美丽数组所需的最小操作次数。
问题分析
这个问题的核心是如何通过最少的操作次数,使得数组满足特定的条件。具体来说,我们需要确保数组中所有长度大于或等于3的子数组的最大值都大于或等于k
。为了实现这一目标,我们可以使用动态规划的方法。
动态规划思路
动态规划是一种将复杂问题分解为子问题的算法思想。在这个问题中,我们可以定义一个数组dp[i]
,表示将数组nums
的前i
个元素变成美丽数组所需的最小操作次数。
状态定义
-
dp[i]
:表示将数组nums
的前i
个元素变成美丽数组所需的最小操作次数。
状态转移
对于每个位置i
,我们需要考虑以下三种情况:
-
只考虑当前元素:即
nums[i]
单独作为一个子数组的一部分。 -
当前元素与前一个元素一起考虑:即
nums[i]
和nums[i-1]
作为一个长度为2的子数组的一部分。 -
当前元素与前两个元素一起考虑:即
nums[i]
、nums[i-1]
和nums[i-2]
作为一个长度为3的子数组。
为了满足美丽数组的条件,我们需要确保:
-
如果只考虑当前元素,那么
nums[i]
必须大于或等于k
。 -
如果考虑当前元素与前一个元素,那么
nums[i]
和nums[i-1]
中至少有一个必须大于或等于k
。 -
如果考虑当前元素与前两个元素,那么
nums[i]
、nums[i-1]
和nums[i-2]
中至少有一个必须大于或等于k
。
因此,dp[i]
的值应该是:
-
如果
nums[i] >= k
,则dp[i] = min(dp[i-1], dp[i-2], dp[i-3])
。 -
如果
nums[i] < k
,则dp[i] = min(dp[i-1], dp[i-2], dp[i-3]) + (k - nums[i])
。
初始化
-
如果数组长度小于3,直接返回0,因为不存在长度大于或等于3的子数组。
-
初始化
dp[0]
、dp[1]
和dp[2]
:-
dp[0] = Math.max(0, k - nums[0])
:只考虑第一个元素nums[0]
,如果它小于k
,则需要k - nums[0]
次操作。 -
dp[1] = Math.max(0, k - nums[1])
:只考虑第二个元素nums[1]
,如果它小于k
,则需要k - nums[1]
次操作。 -
dp[2] = Math.max(0, k - nums[2])
:只考虑第三个元素nums[2]
,如果它小于k
,则需要k - nums[2]
次操作。
-
返回结果
最终返回dp[n-1]
、dp[n-2]
和dp[n-3]
中的最小值。这是因为最后一个元素可能与前两个元素一起考虑,因此需要选择最小的操作次数。
代码实现
以下是Java代码实现:
class Solution {public long minIncrementOperations(int[] nums, int k) {int n = nums.length;if (n < 3) {return 0; // 如果数组长度小于3,直接返回0}// dp[i]表示将数组nums的前i个元素变成美丽数组所需的最小操作次数long[] dp = new long[n];dp[0] = Math.max(0, k - nums[0]); // 初始化第一个位置dp[1] = Math.max(0, k - nums[1]); // 初始化第二个位置dp[2] = Math.max(0, k - nums[2]); // 初始化第三个位置// 动态规划计算for (int i = 3; i < n; i++) {// 当前位置需要的操作次数long currentCost = Math.max(0, k - nums[i]);// 选择最小的操作次数dp[i] = Math.min(dp[i - 1], Math.min(dp[i - 2], dp[i - 3])) + currentCost;}// 返回最后三个位置的最小值return Math.min(dp[n - 1], Math.min(dp[n - 2], dp[n - 3]));}
}
示例解析
假设nums = [2, 3, 5, 1, 4]
,k = 4
。
-
初始化:
-
dp[0] = Math.max(0, 4 - 2) = 2
-
dp[1] = Math.max(0, 4 - 3) = 1
-
dp[2] = Math.max(0, 4 - 5) = 0
-
-
动态规划计算:
-
i = 3
:-
currentCost = Math.max(0, 4 - 1) = 3
-
dp[3] = min(dp[2], dp[1], dp[0]) + currentCost = min(0, 1, 2) + 3 = 3
-
-
i = 4
:-
currentCost = Math.max(0, 4 - 4) = 0
-
dp[4] = min(dp[3], dp[2], dp[1]) + currentCost = min(3, 0, 1) + 0 = 0
-
-
-
返回结果:
-
Math.min(dp[4], Math.min(dp[3], dp[2])) = Math.min(0, Math.min(3, 0)) = 0
-
因此,最终结果是0
,表示不需要任何操作即可满足条件。
总结
通过动态规划,我们可以高效地解决这个问题。动态规划的关键在于:
-
定义合适的状态
dp[i]
。 -
找到状态转移方程。
-
初始化边界条件。
-
返回最终结果。
希望这篇博客能帮助你更好地理解这个问题的解法!如果你有任何疑问或需要进一步的解释,欢迎留言讨论。
相关文章:
LeetCode 2919 使数组变美的最小增量运算数
动态规划解题:最小操作次数使数组变为美丽数组 问题描述 给定一个下标从0开始、长度为n的整数数组nums和一个整数k。你可以对数组中的任意一个元素进行加1操作,操作次数不限。如果数组中任意长度大于或等于3的子数组的最大值都大于或等于k,…...
5.VTK 相机
文章目录 概念示例 概念 在VTK(VisualizationToolkit)中,相机(vtkCamera)用于定义场景的观察视角。以下是关于VTK相机的主要概念和设置方法的总结: 相机位置:通过vtkCamera::SetPosition()方法设…...
基于Flask的网络安全渗透知识库系统架构解析
基于Flask的网络安全渗透知识库系统架构解析 一、系统架构概述 本系统采用经典的三层Flask架构设计,通过模块化的方式实现渗透技术知识库的展示与管理。整体架构包含以下核心组件: 路由控制层:app.py作为入口文件模板展示层:Ji…...
Flutter BigInt 是用于处理任意精度整数的特殊数字类型,专为解决超大整数运算需求而设计
在Flutter/Dart中,BigInt 是用于处理任意精度整数的特殊数字类型,专为解决超大整数运算需求而设计。以下是从原理到实践的全面解析: 一、核心特性 特性说明任意精度突破普通int的64位限制(-2^63 ~ 2^63-1),…...
绿幕抠图直播软件-蓝松抠图插件--使用相机直播,灯光需要怎么打?
使用SONY相机进行绿幕抠图直播时,灯光布置是关键,直接影响抠图效果和直播画质。以下是详细的灯光方案和注意事项: 一、绿幕灯光布置核心原则 均匀照明:绿幕表面光线需均匀,避免阴影和反光(亮度差控制在0.5…...
DeepSeek在数据仓库的10大应用场景
一、智能数据集成与清洗 多源数据整合:DeepSeek能够从多种数据源中提取、转换和加载数据,实现跨系统数据的高效整合。 数据清洗与标准化:通过智能算法自动识别并纠正数据中的错误、不一致性和缺失值,提升数据质量。 二、数据仓…...
Java 工厂设计模式详解:用统一入口打造灵活可扩展的登录系统----掌握 Spring 源码的基础第一步
一、前言 在实际开发中,我们经常面临以下场景: 系统支持多种登录方式(用户名密码、管理员登录、OAuth 登录、短信登录等) 每种登录方式的认证逻辑不同 我们希望对外提供一个统一的接口调用,而不暴露具体实现 这个…...
算法备案和大模型备案能否同时申请?
最近收到很多小伙伴咨询说“算法备案和大模型备案能不能同时申请?”也有一些小伙伴们还分不清算法备案和大模型备案的区别,纷纷询问做了大模型备案还需要做算法备案吗?今天一篇文章带大家了解一下,算法备案和大模型备案究竟是怎么…...
【2025“华中杯”大学生数学建模挑战赛】C题:就业状态分析与预测 详细解题思路
目录 2025“华中杯”大学生数学建模挑战赛C题 详细解题思路一、问题一1.1 问题分析1.2 数学模型 1.3 Python代码1.4 Matlab代码 二、问题二2.1 问题分析2.2 数学模型 2.3 Python代码2.4 Matlab代码 三、问题三3.1 问题分析 四、问题四4.1 问题分析与数学模型 2025“华中杯”大学…...
纷析云开源财务软件:助力企业财务管理数字化转型
在当今数字化时代,企业对财务管理工具的需求日益增长,而开源软件以其透明性、灵活性和成本优势成为越来越多企业的选择。纷析云开源财务软件作为一款专注于企业财务数字化的开源解决方案,不仅提供了强大的功能支持,还通过开源生态…...
APang网联科技项目报告(服务器域管理篇)
APang网联科技:连接未来,智能领航 公司简介 APang网联科技成立于 [2005年],总部位于 [广东深圳],是一家集网络技术研发、系统集成、项目实施与运维服务为一体的高新技术企业。我们致力于为客户提供全方位、定制化的网络部署解决…...
制作Unoconv项目的Docker镜像
制作Unoconv项目的Docker镜像 1 介绍 1.1 Unoconv 在Linux下将Office转换为pdf的很多包仅支持Windows,Unoconv是一个用LibreOffice转化文档的项目,已经归档(2025-3-31)。迁移后的新版本是unoserver,unoserver不太好…...
神经网络--拓扑排序+思维
1.c<0的点赋0,不然会影响后面的入度 2.最后输出层是出度为0的,且题干要求输出c大于0的 3.有q0的情况,所以输的事后就会有答案 https://www.luogu.com.cn/problem/P1038 #include<bits/stdc.h> #include<string> using nam…...
更强的视觉 AI!更智能的多模态助手!Qwen2.5-VL-32B-Instruct-AWQ 来袭
Qwen2.5-VL-32B-Instruct 是阿里巴巴通义千问团队于 2025 年 3 月 24 日开源的多模态大模型,基于 Apache 2.0 协议发布。该模型在 Qwen2.5-VL 系列的基础上,通过强化学习技术优化,以 32B 参数规模实现了多模态能力的突破。 核心特性升级&…...
逻辑过期怎么设计
设计“逻辑过期”通常用于缓存、令牌管理、数据有效性验证等场景,其核心是通过业务逻辑判断数据是否过期(而非单纯依赖物理时间)。以下是设计逻辑过期的关键思路和实现方案: 1. 核心思想 物理过期:基于固定的时间&…...
EMIF详解
一、EMIF的基本定义 EMIF(External Memory Interface,外部存储器接口) 是嵌入式处理器(如DSP、FPGA、SoC)用于连接外部存储器的专用硬件接口模块,负责管理处理器与存储器之间的地址/数据总线、控制信号及时…...
Kubernetes》》K8S》》Pod调度机制
nodeName 、nodeSelector nodeName 是强绑定,nodeSelector是弱绑定 强绑定,如果Node失效时,则会导致Pod也无法调度 apiVersion: v1 kind: Pod metadata:name: example-pod spec:# nodeName Pod应该被调度到哪个具体的节点上 强绑定nodeNam…...
具身智能机器人学习路线全解析
一、引言 具身智能机器人作为融合了机器人学、人工智能、认知科学等多领域知识的前沿技术,正逐渐改变着我们的生活和工作方式。从工业制造到家庭服务,从医疗护理到太空探索,具身智能机器人都展现出了巨大的潜力。对于想要深入了解和学习这一…...
【PGCCC】Postgres MVCC 内部:更新与插入的隐性成本
为什么 Postgres 中的更新操作有时感觉比插入操作慢?答案在于 Postgres 如何在后台管理数据版本。 Postgres 高效处理并发事务能力的核心是多版本并发控制(MVCC)。 在本文中,我将探讨 MVCC 在 Postgres 中的工作原理以及它如何影响…...
ESP-ADF外设子系统深度解析:esp_peripherals组件架构与核心设计(输入类外设之触摸屏 Touch)
目录 ESP-ADF外设子系统深度解析:esp_peripherals组件架构与核心设计(输入类外设之触摸屏 Touch)简介模块概述功能定义架构位置核心特性 触摸(Touch)外设触摸外设概述触摸外设API和数据结构外设层API(periph_touch.h/periph_touch…...
Python高级爬虫之JS逆向+安卓逆向1.5节: 控制结构
目录 引言: 1.5.1 Python中的控制结构 1.5.2 条件控制 1.5.3 循环控制 1.5.4 跳转控制 1.5.5 爬虫不要接学生单 引言: 大神薯条老师的高级爬虫安卓逆向教程: 这套爬虫教程会系统讲解爬虫的初级,中级,高级知识&a…...
Spine-Leaf 与 传统三层架构:全面对比与解析
本文将详细介绍Spine-Leaf架构,深入对比传统三层架构(Core、Aggre、Access),并探讨其与Full-mesh网络和软件定义网络(SDN)的关联。通过通俗易懂的示例和数据中心网络分析,我将帮助您理解Spine-L…...
微信小程序文字混合、填充动画有效果图
效果图 .wxml <view class"text" style"--deg:{{deg}}deg;"><view>混合父级颜色</view> </view> <view class"fill {{status?action:}}">文字颜色填充</view> <button bind:tap"setStatus"…...
山东大学软件学院创新项目实训开发日志(15)之中医知识问答历史对话查看bug处理后端信息响应成功但前端未获取到
在开发中医知识问答历史对话查看功能的时候,出现了前后端信息获取异同的问题,在经过非常非常非常艰难的查询之后终于解决了这一问题,而这一问题的罪魁祸首就是后端没有setter和getter方法!!!!&a…...
HttpSessionBindingListener 的用法笔记250417
HttpSessionBindingListener 的用法笔记250417 HttpSessionBindingListener 是 Java Servlet 规范中 唯一 由 被存储对象自身实现 的会话监听接口, 1. 核心功能 HttpSessionBindingListener 是一个由 会话属性对象自身实现 的接口,用于监听该对象被绑定…...
EuroCropsML:首个面向少样本时间序列作物分类的多国基准数据集
2025-04-15,由慕尼黑工业大学等机构创建的 EuroCropsML 数据集,这是一个结合了农民报告的作物数据与 Sentinel-2 卫星观测的时间序列数据集,覆盖了爱沙尼亚、拉脱维亚和葡萄牙。该数据集为解决遥感应用中作物类型数据空间不平衡问题提供了新的…...
《如何用 Function 实现动态配置驱动的处理器注册机制?》
大家好呀!👋 今天我们来聊聊一个超实用的技术话题 - 如何用Java的Function接口实现动态配置驱动的处理器注册机制。听起来很高大上?别担心,我会用最简单的方式讲清楚!😊 一、为什么要用Function实现处理器…...
PyTorch:学习 CIFAR-10 分类
🔍 开始你的图像分类之旅:一步一步学习 CIFAR-10 分类 图像分类是计算机视觉中最基础的任务之一,如果你是初学者,那么以 CIFAR-10 为训练场是一个不错的选择。本文一步一步带你从零开始,学习如何用深度学习模型实现图…...
SpringBoot整合Thymeleaf模板:构建现代化Web视图层的完整指南
在Java Web开发领域,Thymeleaf作为一款自然模板引擎,凭借其优雅的语法和与Spring生态的无缝集成,已成为替代传统JSP的首选方案。本文将从技术整合、核心原理到生产实践,深度解析SpringBoot与Thymeleaf的协同工作方式。 一、Thymel…...
学习笔记十五——rust柯里化,看不懂 `fn add(x) -> impl Fn(y)` 的同学点进来!
🧠 Rust 柯里化从零讲透:看不懂 fn add(x) -> impl Fn(y) 的同学点进来! 🍔 一、什么是柯里化?先用一个超好懂的生活比喻 假设你在点一个汉堡: 你说:我要点一个鸡腿汉堡! 店员…...
软件安装包-yum
yum:软件管理的得力助手 yum是一个软件下载安装管理的一个客户端,例如:小米应用商城、华为应用商城... Linux中软件包可能有依赖关系——yum会帮我们解决依赖关系的问题! 1、软件包是什么? 在Linux下安装软件, 一个通…...
C++面试
C面试 c面试100题 1、封装多态继承 2、数据集合 3、 4、便于外部文件访问 5、只能通过对象访问 6、通过类名 7、构造函数、析构函数、拷贝构造函数、拷贝复制函数 8、将一个对象复制给新建的对象 9、没有返回值 10、类的对象中有指针,防止多个指针指向同…...
Java SpringBoot设置自定义web的图片本地路径
一,设置配置文件:application.properties my.config.image-pathD:\\Download\\images二,新增配置类:MyImagesConfig import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; import org.springfr…...
Python HTTP库——requests
文章目录 简介安装基本概念RESTfulAPIOAuth2.0Cookie和Session 初试GET请求POST请求PUT请求DELETE请求HEAD请求OPTIONS请求传递查询参数响应内容自定义响应头传递表单参数传递文件响应状态码响应头Cookies重定向和历史记录超时错误和异常Session对象请求和响应对象预处理请求SS…...
用idea配置springboot+mybatis连接postersql数据库
从socket开始,我们就要开始部署前后端的交互了,所以今天带来一份热度比较高的框架springboot,并教大家如何连接数据库。 框架 先给大家看一下目录结构,因为有些需要调用文件路径: 创建项目: 新版本可以…...
【补充篇】Davinci工具要求的dbc格式
1 简介 DBC文件是一种用于描述CAN(Controller Area Network,控制器局域网络)通信协议中报文和信号的格式化文件,其全称为“Database CAN”。DBC文件的核心作用是定义和解析CAN网络中的通信数据,包括节点、报文、信号及其属性等信息。 对于不同角色的工程师,DBC文件有着…...
IT资产管理(一)之GLPI安装及部署
一、GLPI 介绍 GLPI:Gestionnaire Libre de Parc Informatique 是一个免费的资产和 IT 管理软件包,提供 ITIL 服务台功能、许可证跟踪和软件审计。 GLPI 的主要功能: 服务资产和配置管理 (SACM):管理您的 IT 资产和配置,跟踪计算机、外围设备、网络打印机及其相关组件…...
RPCRT4!OSF_CCALL::ActivateCall函数分析之RPCRT4!OSF_CCALL结构中的Bindings--RPC源代码分析
第一部分: 1: kd> t RPCRT4!OSF_CCALL::ActivateCall: 001b:77bf5789 55 push ebp 1: kd> kc # 00 RPCRT4!OSF_CCALL::ActivateCall 01 RPCRT4!OSF_CASSOCIATION::AllocateCCall 02 RPCRT4!OSF_BINDING_HANDLE::AllocateCCall 03 RPCRT4!OS…...
docker登录AWS ECR拉取镜像
1、配置AWS 登录key [rootip-172-31-13-6 ~]# aws configure AWS Access Key ID [None]: XXXXXXXXXXX AWS Secret Access Key [None]: %%YYYDSRGTHFGFSGRTHTHE$RHTSG Default region name [None]: ap-southeast-1 Default output format [None]: json2、登录AWS ECR镜像仓库 …...
IntelliJ IDEA download JDK
IntelliJ IDEA download JDK 自动下载各个版本JDK,步骤 File - Project Structure (快捷键 Ctrl Shift Alt S) 如果下载失败,换个下载站点吧。一般选择Oracle版本,因为java被Oracle收购了 好了。 花里胡哨&#…...
MQTT协议与HTTP协议的对比分析
以下是MQTT协议与HTTP协议的对比分析,从协议特性到应用场景的系统性对比: 一、协议层级与设计目标对比 维度MQTTHTTP协议层级应用层协议(基于TCP/IP)应用层协议(基于TCP/IP)核心设计目标机器间轻量级消息通…...
jenkins凭据管理(配置github密钥)
1.凭据管理 添加两种类型的凭据,Username with password和Secret text(填的token) Username with password是github登录的用户名和密码,Secret text填的github生成的token,权限的限制更细,安全性更高一些 Dashboard -> Manag…...
B端小程序如何突破常规,成为企业获客新利器?
数据驱动的用户旅程优化 在当今竞争激烈的市场环境中,了解并优化用户的交互路径对于吸引和保留客户至关重要。B端小程序可以通过收集用户行为数据来分析用户偏好和使用习惯。例如,应用热图分析工具可以直观展示用户点击最频繁的区域,帮助企业…...
25.4.17学习总结
关于bcrypt算法 BCrypt 的主要特点和优点: 加盐 (Salting): BCrypt 会自动为每个密码生成一个随机的盐值 (salt) 并将其与密码组合在一起,然后再进行哈希。 盐值是随机数据,用于防止彩虹表攻击。 这意味着即使两个用户使用相同的密码&#x…...
java 设计模式 策略模式
简介 策略模式(Strategy Pattern)是一种行为设计模式,旨在定义一系列算法,并将每一个算法封装起来,使它们可以互相替换。策略模式让算法的变化独立于使用算法的客户端。换句话说,策略模式通过将不同的算法…...
游戏盾和高防ip有什么区别
游戏盾和高防IP都是针对网络攻击的防护方案,但核心目标、技术侧重点和应用场景存在显著差异。以下是两者的详细对比分析: 一、核心定位与目标 维度高防IP游戏盾核心目标抵御大流量网络攻击(…...
关于 雷达(Radar) 的详细解析,涵盖其定义、工作原理、分类、关键技术、应用场景、挑战及未来趋势,结合实例帮助理解其核心概念
以下是关于 雷达(Radar) 的详细解析,涵盖其定义、工作原理、分类、关键技术、应用场景、挑战及未来趋势,结合实例帮助理解其核心概念: 一、雷达的定义与核心功能 1. 定义 雷达(Radar,Radio D…...
机器学习 Day11 决策树
1.决策树简介 原理:思想源于程序设计的 if - else 条件分支结构 ,是一种树形结构。内部节点表示属性判断,分支是判断结果输出,叶节点是分类结果 。案例:以母亲给女儿介绍男朋友为例。女儿依次询问年龄(≤3…...
【HFP】深入解析蓝牙 HFP 协议中呼叫转移、呼叫建立及保持呼叫状态的机制
目录 一、核心指令概述 1.1 ATCMER:呼叫状态更新的 “总开关” 1.2 ATBIA:指示器的 “精准控制器” 1.3 指令对比 1.4 指令关系图示 二、CIEV 结果码:状态传递的 “信使” 2.1 工作机制 2.2 三类核心指示器 三、状态转移流程详解 3…...
音频识别优化(FFT)
整合多频段检测、动态阈值调整和持续时长验证的完整代码实现,包含详细注释: #include "esp_dsp.h" #include "driver/i2s.h" #include "esp_log.h" #include "math.h" static const char* TAG "ADV_FRE…...