算法每日一题: 使用循环数组所有元素相等的最少秒数 | 哈希

大家好,我是星恒,今天给大家带来的是一道需要感觉规律的题目,只要读懂题目中的规律,就可以做出来了
这道题用到了哈希,还有一个关键点比较类似循环队列

题目:leetcode 2808

给你一个下标从 0 开始长度为 n 的数组 nums 。
每一秒,你可以对数组执行以下操作:

  • 对于范围在 [0, n - 1] 内的每一个下标 i ,将 nums[i] 替换成 nums[i] ,nums[(i - 1 + n) % n] 或者 nums[(i + 1) % n] 三者之一。

注意,所有元素会被同时替换。
请你返回将数组 nums 中所有元素变成相等元素所需要的 最少 秒数。

示例 1:

输入:nums = [1,2,1,2]
输出:1
解释:我们可以在 1 秒内将数组变成相等元素:
- 第 1 秒,将每个位置的元素分别变为 [nums[3],nums[1],nums[3],nums[3]] 。变化后,nums = [2,2,2,2] 。
1 秒是将数组变成相等元素所需要的最少秒数。

示例 2:

输入:nums = [2,1,3,3,2]
输出:2
解释:我们可以在 2 秒内将数组变成相等元素:
- 第 1 秒,将每个位置的元素分别变为 [nums[0],nums[2],nums[2],nums[2],nums[3]] 。变化后,nums = [2,3,3,3,3] 。
- 第 2 秒,将每个位置的元素分别变为 [nums[1],nums[1],nums[2],nums[3],nums[4]] 。变化后,nums = [3,3,3,3,3] 。
2 秒是将数组变成相等元素所需要的最少秒数。

示例 3:

输入:nums = [5,5,5,5]
输出:0
解释:不需要执行任何操作,因为一开始数组中的元素已经全部相等。

提示:

  • 1 <= n == nums.length <= 105
  • 1 <= nums[i] <= 109

分析:
阅读题目,大家首先可能对这两个式子有些迷惑:nums[(i - 1 + n) % n] 和 nums[(i + 1) % n]
其实他们就是处理了一下首尾元素:

  • nums[(i - 1 + n) % n]:当元素为首元素时(下标为0),式子变为了nums[n - 1];其他元素相当于nums[i - 1]
  • nums[(i + 1) % n]:当元素为尾元素时(下标为n - 1),式子变为了nums[0];其他元素相当于nums[i + 1]

这样做的目的是可以让首尾相连,感觉首元素和尾元素相邻了

好,知道了这个,我们正式开始分析这道题目:
读题,我们可以知道,一个元素,一次可以将相邻的两个元素下标变为自己的,所以每一秒我们可以影响相邻元素。


结合上面的理论,我们来看这个图

也就是说,变成相等元素所需要的 最少 秒数,就是两个相邻相同元素的 最大 距离 / 2
注意,首尾距离也要计算

至于我们选择哪个作为相同元素更好,我们只要将每一种元素的所需最大秒数求出来比较就可以了

我们来看题解:

题解:

class Solution {public int minimumSeconds(List<Integer> nums) {HashMap<Integer, List<Integer>> mp = new HashMap<>();int n = nums.size(), res = n;for (int i = 0; i < n; ++i) {mp.computeIfAbsent(nums.get(i), k -> new ArrayList<>()).add(i);}for (List<Integer> positions : mp.values()) {int mx = positions.get(0) + n - positions.get(positions.size() - 1);for (int i = 1; i < positions.size(); ++i) {mx = Math.max(mx, positions.get(i) - positions.get(i - 1));}res = Math.min(res, mx / 2);}return res;}
}

注意:
mp.computeIfAbsent(nums.get(i), k -> new ArrayList<>()).add(i);的意思表示key为“i”的键值对是否存在

  • 如果存在则获取i的值,并操作值的list添加数据“i"。
  • 如果不存在,则调用方法,新创建list结构,将"i"添加到list中,再存入到hashMap中。
  • – 这个API适合用于值为集合的

values(): 返回Map集合中所有value组成的以Collection数据类型格式数据。

如果大家有什么思考和问题,可以在评论区讨论,也可以私信我,很乐意为大家效劳。
好啦,今天的每日一题到这里就结束了,如果大家觉得有用,可以可以给我一个小小的赞呢,我们下期再见!

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

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

相关文章

支持向量机

支持向量机&#xff08;Support Vector Machine&#xff0c;SVM&#xff09;是一个非常优雅的算法&#xff0c;具有非常完善的数学理论&#xff0c;常用于数据分类&#xff0c;也可以用于数据的回归预测中。支持向量机在许多领域都有广泛的应用&#xff0c;如文本分类、图像识别…

数据库管理phpmyadmin

子任务1-PHPmyadmin软件的使用 本子任务讲解phpmyadmin的介绍和使用操作。 训练目标 1、掌握PHPmyadmin软件的使用方法。 步骤1 phpMyAdmin 介绍 phpmyadmin是一个用PHP编写的软件工具&#xff0c;可以通过web方式控制和操作MySQL数据库。通过phpMyAdmin可以完全对数据库进行…

如何构建起自己的伦敦银交易系统?

投资者在市场这个江湖中行走&#xff0c;就需要有一技防身&#xff0c;不然很容易会被市场的风险所淹没&#xff0c;这个“一技”指的就是伦敦银交易系统。如果投资者要构建起自己的伦敦银交易系统&#xff0c;应该从哪几个方面着手呢&#xff1f;下面我们就来讨论一下。 分析方…

【算法与数据结构】583、72、LeetCode两个字符串的删除操作+编辑距离

文章目录 一、583、两个字符串的删除操作二、72、编辑距离三、完整代码 所有的LeetCode题解索引&#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、583、两个字符串的删除操作 思路分析&#xff1a;本题的思路和115、不同的子序列差不多&#xff0c;只是变成…

Python—数据可视化Seaborn大全:参数详解与实战案例全解析【第52篇—python:Seaborn大全】

文章目录 Seaborn库常用绘图详解与实战引言安装与导入一、散点图参数说明实战案例 二、直方图参数说明实战案例 三、线性关系图参数说明实战案例 四、热力图参数说明实战案例 五、分布图参数说明实战案例 六、箱线图参数说明实战案例 七、联合分布图参数说明实战案例 八、小提琴…

echarts条形图添加滚动条

效果展示: 测试数据: taskList:[{majorDeptName:测试,finishCount:54,notFinishCount:21}, {majorDeptName:测试,finishCount:54,notFinishCount:21}, {majorDeptName:测试,finishCount:54,notFinishCount:21}, {majorDeptName:测试,finishCount:54,notFinishCount:21}, {maj…

Pytest框架测试

Pytest 是什么? pytest 能够支持简单的单元测试和复杂的功能测试;pytest 可以结合 Requests 实现接口测试; 结合 Selenium、Appium 实现自动化功能测试;使用 pytest 结合 Allure 集成到 Jenkins 中可以实现持续集成。pytest 支持 315 种以上的插件;为什么要选择 Pytest 丰…

【axios报错异常】: Uncaught ReferenceError: axios is not defined

问题描述: 当前代码在vivo手机和小米手机运行是正常的,点击分享按钮调出相关弹框,发送接口进行分享,但是现在oppo手机出现了问题: 点击分享按钮没有反应. 问题解析: 安卓同事经过查询后,发现打印了错误: 但是不清楚这个问题是安卓端造成的还是前端造成的,大家都不清楚. 问题…

图论练习3

内容&#xff1a;过程中视条件改变边权&#xff0c;利用树状数组区间加处理 卯酉东海道 题目链接 题目大意 个点&#xff0c;条有向边&#xff0c;每条边有颜色和费用总共有种颜色若当前颜色与要走的边颜色相同&#xff0c;则花费为若当前颜色与要走的边颜色不同&#xff0c;…

Java面试——计网篇

一、基础篇 1、 TCP/IP 网络模型 对于同一台设备上的进程间通信&#xff0c;有很多种方式&#xff0c;比如有管道、消息队列、共享内存、信号等方式&#xff0c;而对于不同设备上的进程间通信&#xff0c;就需要网络通信&#xff0c;而设备是多样性的&#xff0c;所以要兼容多…

【Java程序设计】【C00245】基于Springboot的家政服务管理平台(有论文)

基于Springboot的家政服务管理平台&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的家政服务管理平台 本系统分为前台模块、管理员功能模块、用户功能模块以及服务人员功能模块。 前台模块&#xff1a;系统首页的…

C2-Search-Netlas:一款基于Netlas API的强大C2服务器识别与检测工具

关于C2-Search-Netlas C2-Search-Netlas是一款功能强大的命令与控制&#xff08;C2&#xff09;服务器检测工具&#xff0c;该工具使用Java语言开发&#xff0c;基于Netlas API实现其功能&#xff0c;可以帮助广大研究人员轻松快速地识别和检测目标C2服务器的相关信息。 C2-S…

【目标跟踪】相机运动补偿

文章目录 一、前言二、简介三、改进思路3.1、状态定义3.2、相机运动补偿3.3、iou和ReID融合3.4、改进总结 四、相机运动补偿 一、前言 目前 MOT (Multiple Object Tracking) 最有效的方法仍然是 Tracking-by-detection。今天给大家分享一篇论文 BoT-SORT。论文地址 &#xff0…

XCTF:warmup[WriteUP]

CtrlU查看页面源码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><meta http-equiv"X-UA-Compatible&q…

【Matplotlib】figure方法之图形的保存

&#x1f388;个人主页&#xff1a;甜美的江 &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;matplotlib &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进…

idea常用设置

1、内存优化 根据自己电脑本身的内存&#xff0c;对idea安装包里bin目录下的idea64.exe.vmoptions文件进行修改 -server -Xms256m -Xmx2048m -XX:MaxPermSize1024m -XX:ReservedCodeCacheSize256m -ea -Dsun.io.useCanonCachesfalse -Djava.Net.preferIPv4Stacktrue -Djsse.e…

STM32--HAL库定时器学习记录(易懂)--持续学习

一、什么是定时器 定时器就是计数器&#xff0c;通过计数完成一系列功能。 二、定时器的分类 定时器分为基本定时器、通用定时器、高级定时器。级别不同&#xff0c;功能不同。级别越高&#xff0c;功能越强。 三、定时器&#xff08;计数器&#xff09;三个重要寄存器 预分…

CSS:水平垂直居中

公共的 CSS 样式&#xff1a; .parent {width: 300px;height: 300px;background-color:#d0e4fe; }.child {width: 100px;height: 100px;background-color:orange; }HTML: <div class"parent"><div class"child"></div> </div>最…

C#之linq和lamda表达式GroupBy分组拼接字符串

文章目录 C#之linq和lamda表达式GroupBy分组拼接字符串业务需求核心代码调试 C#之linq和lamda表达式GroupBy分组拼接字符串 业务需求 点击提示信息&#xff0c;如&#xff1a;“售后单【SH001】序列号【001&#xff0c;002&#xff0c;006】&#xff1b;售后单【SH002】序列号…

华为自动驾驶干不过特斯拉?

文 | AUTO芯球 作者 | 李诞 什么&#xff1f; 华为的智能驾驶方案干不过蔚小理&#xff1f; 特斯拉的智能驾驶[FSD]要甩中国车企几条街&#xff1f; 这华为问界阿维塔刚刚推送“全国都能开”的城区“无图 NCA” 就有黑子来喷了 这是跪久了站不起来了吧 作为玩车14年&…