1144. 递减元素使数组呈锯齿状

news/2024/3/29 23:47:12/文章来源:https://blog.csdn.net/qq_39304630/article/details/129252990

1144. 递减元素使数组呈锯齿状

难度中等116收藏分享切换为英文接收动态反馈

给你一个整数数组 nums,每次 操作 会从中选择一个元素并 将该元素的值减少 1

如果符合下列情况之一,则数组 A 就是 锯齿数组

  • 每个偶数索引对应的元素都大于相邻的元素,即 A[0] > A[1] < A[2] > A[3] < A[4] > ...
  • 或者,每个奇数索引对应的元素都大于相邻的元素,即 A[0] < A[1] > A[2] < A[3] > A[4] < ...

返回将数组 nums 转换为锯齿数组所需的最小操作次数。

示例 1:

输入:nums = [1,2,3]
输出:2
解释:我们可以把 2 递减到 0,或把 3 递减到 1。

示例 2:

输入:nums = [9,6,1,6,2]
输出:4

提示:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000

思路:不管是每个偶数索引对应的元素都大于相邻的元素还是每个奇数索引对应的元素都大于相邻的元素,绕不开的一个问题就是如何让一个位置的数nums[i]比两边小,实际上等价于比两边值中更小的那个还小,而最小操作数意味着我们尽可能少地减少nums[i],那么在最少操作次数下的目标值为min(nums[i-1],nums[i+1]) - 1,操作步数为nums[i] - ( min(nums[i-1],nums[i+1])-1 )。还需要处理的一个事情是nums[i]本身就满足nums[i] < min(nums[i-1],nums[i+1]),此时会得到操作数nums[i] - ( min(nums[i-1],nums[i+1]) -1 )  <= 0,但是其实对于这种情况我们是不需要处理的,因此最终每个位置的操作步数为max(0, nums[i] - ( min(nums[i-1],nums[i+1]) -1))。

现在我们只需要分两种情况(每个偶数索引对应的元素都大于相邻的元素;每个奇数索引对应的元素都大于相邻的元素)分别计算一下操作步数,取小即可啦

class Solution {
public:int movesToMakeZigzag(vector<int>& nums) {//BFS//return min(DFS(nums, true, 0, 0), DFS(nums, false, 0, 0));//1.计算奇最小情况 直接减小奇位置还是间接变小偶位置int add_step = 0, odd_step = 0, neighbour_min, idx;for(idx = 1; idx < nums.size(); idx += 2){//把奇位置变小neighbour_min = nums[idx - 1];if(idx + 1 < nums.size()){neighbour_min = min(neighbour_min, nums[idx + 1]);}add_step += max(0, nums[idx] - (neighbour_min - 1));}//2.计算偶情况for(idx = 0; idx < nums.size(); idx += 2){//把偶位置变小neighbour_min = 0x3f3f3f3f;if(idx > 0){//算一下左边neighbour_min = min(neighbour_min, nums[idx - 1]);}if(idx + 1 < nums.size()){neighbour_min = min(neighbour_min, nums[idx + 1]);}odd_step += max(0, nums[idx] - (neighbour_min - 1));}return min(add_step, odd_step);}
};

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

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

相关文章

2020蓝桥杯真题跑步锻炼(填空题) C语言/C++

题目描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 小蓝每天都锻炼身体。 正常情况下&#xff0c;小蓝每天跑 1 千米。如果某天是周一或者月初&#xff08;1 日&#xff09;&#xff0c;为了激励自己&#xff0c;小蓝…

Docker在Windows环境的搭建和使用

文章目录安装WSL安装Docker安装Docker镜像下载Docker镜像启动gpu启动传送文件训练yolov5安装WSL Windows10和11支持Docker的安装&#xff0c;安装需要用到WSL。所以&#xff0c;我们先安装WSL。 参考文章&#xff1a;旧版 WSL 的手动安装步骤 以管理员身份打开powershell, 执行…

软考信息系统监理师备考建议

用好备考方法&#xff0c;两三个月就可以过的。信息系统监理师备考最好以教材和历年真题为主&#xff0c;教学视频模拟题为辅。考试介绍与复习建议&#xff1a;考试设置的科目包括&#xff1a;&#xff08;1&#xff09;信息系统工程监理基础知识&#xff0c;考试时间150分钟&a…

Three.js初试——基础概念

一、Three.js 是什么 先附上文档&#xff1a; 官网&#xff1a;JavaScript 3D Library 中文文档&#xff1a;中文文档 Three.js 是一个让用户通过 javascript 入手进入搭建 WebGL 项目的类库。众所周知学习 WebGL 需要图形学知识&#xff0c;而 webgl 需要通过 js 和 glsl …

第八届蓝桥杯省赛——4承压计算(二维数组,嵌套循环)

题目&#xff1a;X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。每块金属原料的外形、尺寸完全一致&#xff0c;但重量不同。金属材料被严格地堆放成金字塔形。7 5 8 7 8 8 9 2 7 2 8 1 4 9 1 8 1 8 8 4 1 7 9 6 1 4 5 4 5 6 5 5 6 9 5 6 5 5 4 7 9 3 5 5 1 7 5 7 9 7 4…

车辆热管理测试方案

车辆热管理是在能源危机出现、汽车排放法规日益严格以及人们对汽车舒适性要求更高的背景下应运而生的。将各个系统或部件如冷却系统、润滑系统和空调系统等集成一个有效的热管理系统&#xff1b;控制和优化车辆的热量传递过程&#xff0c;保证各关键部件和系统安全高效运行&…

社交媒体营销的5个好处

有些人认为&#xff0c;社交媒体营销不能直接与销售挂钩。这就是为什么在制定营销策略时&#xff0c;社交媒体营销会被部分人忽视的原因。然而&#xff0c;与其他广告渠道不同&#xff0c;社交媒体是双向渠道。忽视社交媒体营销将影响与客户的关系。最重要的是&#xff0c;它将…

回顾1-idea创建Java项目

创建Java项目 创建项目和模块的区别 环境前置 IDEA开发工具JDK及配置环境变量 创建项目/工程 新建项目 选择Java模块 > SDK( 已配置的JDK ) > 下一步 直接下一步 填写项目信息 QQ游戏工程 里的 叫项目 所以 QQgame目录下 可以放 > 斗地主项目 / 美女来找茬等… …

C while 循环for循环

C 循环 只要给定的条件为真&#xff0c;C 语言中的 while 循环语句会重复执行一个目标语句。 语法 C 语言中 while 循环的语法&#xff1a; while(condition) {statement(s); }在这里&#xff0c;statement(s) 可以是一个单独的语句&#xff0c;也可以是几个语句组成的代码块…

深度学习基础实例与总结

一、神经网络 1 深度学习 1 什么是深度学习&#xff1f; 简单来说&#xff0c;深度学习就是一种包括多个隐含层 (越多即为越深)的多层感知机。它通过组合低层特征&#xff0c;形成更为抽象的高层表示&#xff0c;用以描述被识别对象的高级属性类别或特征。 能自生成数据的中…

DNS服务器部署的详细操作(图文版)

DNS服务器的部署 打开虚拟机后查看已经开放的端口&#xff0c;可以看到没有TCP53、UDP53&#xff0c;说明DNS服务端口没有打开 打开我的电脑—双击CD驱动器— 选择安装可选的Windows组件 选择网络服务—域名系统&#xff08;DNS&#xff09;— 点击下一步后会弹出如下弹…

线程安全实例分析

一、变量的线程安全分析 成员变量和静态变量是否线程安全&#xff1f; ● 如果它们没有共享&#xff0c;则线程安全 ● 如果它们被共享了&#xff0c;根据它们的状态是否能够改变&#xff0c;又分两种情况 —— 如果只有读操作&#xff0c;则线程安全 —— 如果有读写操作&am…

实时手势识别(C++与python都可实现)

一、前提配置&#xff1a; Windows&#xff0c;visual studio 2019&#xff0c;opencv&#xff0c;python10&#xff0c;opencv-python&#xff0c;numpy&#xff0c;tensorflow&#xff0c;mediapipe&#xff0c;math 1.安装python环境 这里我个人使用的安装python10&#…

ABB机器人基础编程_常见数据类型及使用方法介绍

ABB机器人基础编程_常见数据类型及使用方法介绍 1. bool-逻辑值 描述:bool型数据可以为TRUE或FALSE 使用方法举例: 2. 字节-整数值 描述:byte用于符合字节范围的整数值0-255,该数据类型连同处理操作并转换特征的指令和函数一同使用。 使用方法举例: 3. dnum-双数值 描…

云原生是什么?核心概念和应用方法解析

什么是云原生&#xff1f; 云原生是一种基于容器、微服务和自动化运维的软件开发和部署方法。它可以使应用程序更加高效、可靠和可扩展&#xff0c;适用于各种不同的云平台。 如果要更直接通俗的来解释下上面的概念。云原生更准确来说就是一种文化&#xff0c;是一种潮流&…

供应链的有效管理,分析指标有哪些

对于企业而言&#xff0c;供应链是一个很复杂的、体系化的生态系统&#xff0c;从原材料、到供应商、到生产、仓库、物流&#xff0c;最后到达经销商或者最终客户那里&#xff0c;这个链条很长。相关的分析指标也有很多&#xff0c;在这些指标里面也有非常多可以扩展、延申的内…

【Linux驱动】驱动设计硬件基础----串口、I2C、SPI、以太网接口、PCIE

1.前言 常见的外设接口与总线的工作方式&#xff0c;包括串口、I2C、SPI、USB、以太网接口、PCI和PCI-E、SD和SDIO等。 2.串口 RS-232、RS-422与RS-485都是串行数据接口标准&#xff0c;最初都是由电子工业协会&#xff08;EIA&#xff09;制订并发布的。 3.I2C I2C&…

【RabbitMQ七】——RabbitMQ发布确认模式(Publisher Confirms)

RabbitMQ发布确认模式前言如何实现发布确认发布确认模式有三种策略单独发布消息执行结果批量发布消息执行结果异步处理发布确认执行结果思考点如何追踪未完成的确认?重新发布丢失的消息总结收获前言 发布确认是解决消息不丢失的重要环节&#xff0c;在设置队列持久化、消息持…

MySQL实战解析底层---基础架构:一条SQL查询语句是如何执行的?

目录 前言 连接器 查询缓存 分析器 优化器 执行器 前言 平时使用数据库&#xff0c;看到的通常都是一个整体比如&#xff0c;有个最简单的表&#xff0c;表里只有一个 ID 字段&#xff0c;在执行下面这个查询语句时&#xff1a; 看到的只是输入一条语句&#xff0c;返回…

Billu靶场黑盒盲打——思路和详解

一、信息收集 1、探测内网主机IP可以使用各种扫描工具比如nmap&#xff0c;我这里用的是自己编写的。 nmap -n 192.168.12.0/24 #扫描IP&#xff0c;发现目标主机 2、先不着急&#xff0c;先收集一波它的端口&#xff08;无果&#xff09; nmap -n 192.168.12.136 -p 1-10000…