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

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

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

题目: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数据类型格式数据。

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

相关文章:

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

大家好&#xff0c;我是星恒&#xff0c;今天给大家带来的是一道需要感觉规律的题目&#xff0c;只要读懂题目中的规律&#xff0c;就可以做出来了 这道题用到了哈希&#xff0c;还有一个关键点比较类似循环队列 题目&#xff1a;leetcode 2808 给你一个下标从 0 开始长度为 n…...

canvas实现涂鸦画板功能

查看专栏目录 canvas实例应用100专栏&#xff0c;提供canvas的基础知识&#xff0c;高级动画&#xff0c;相关应用扩展等信息。canvas作为html的一部分&#xff0c;是图像图标地图可视化的一个重要的基础&#xff0c;学好了canvas&#xff0c;在其他的一些应用上将会起到非常重…...

6-3、T型加减速单片机程序【51单片机+L298N步进电机系列教程】

↑↑↑点击上方【目录】&#xff0c;查看本系列全部文章 摘要&#xff1a;根据前两节内容&#xff0c;已完成所有计算工作&#xff0c;本节内容介绍具体单片机程序流程及代码 一、程序流程图 根据前两节文章内容可知&#xff0c;T型加减速的关键内容是运动类型的判断以及定时…...

Flutter组件 StatefulWidget、StatelessWidget 可继承写法

前言 学过Java的同学&#xff0c;应该都知道面向对象语言的三大特征&#xff0c;封装、继承、多态&#xff1b; Dart也是面向对象的语言&#xff0c;但是在Flutter中的很多组件都被下划线 _ 标记为私有&#xff0c;导致无法继承&#xff0c;本文将介绍一种非私有的创建组件写…...

skywalking链路追踪

skywalking 1.简介1.1 skywalking介绍1.2 链路追踪框架对比1.3 Skywalking架构 2 环境构建2.1 windows环境2.1.1 启动skywalking服务和UI界面2.1.2 在IDEA启动项目中使用Skywalking2.1.3 skywalking持久化 2.2 linux环境 1.简介 微服务架构已经是一个很通用的系统架构&#xf…...

如何在苹果Mac上进行分屏,多任务处理?

Apple 在 macOS Catalina 中引入了 Split View&#xff0c;让您可以同时查看两个应用程序。如果同时处理多个应用程序&#xff0c;但在它们之间切换时感到沮丧&#xff0c;小编教给大家在 Macbook Pro/Air 或 iMac 上使用分屏功能流畅地进行多任务处理。 注意&#xff1a;您可…...

【Java EE】----Spring框架创建和使用

1.Spring框架创建 创建一个maven项目 添加Spring框架支持 <dependencies> 上下文<dependency><groupId>org.springframework</groupId><artifactId>spring-context</artifactId><version>5.2.3.RELEASE</version></depende…...

UE4 C++ 静态加载类和资源

静态加载类和资源&#xff1a;指在编译时加载&#xff0c;并且只能在构造函数中编写代码 .h //增加所需组件的头文件 #include "Components/SceneComponent.h" //场景组件 #include "Components/StaticMeshComponent.h" //静态网格体组件 #include &qu…...

洛谷C++简单题小练习day9—[AHOI2017]寻找探监点

day9--[AHOI2017]寻找探监点--2.7 习题概述 题目描述 一个nn 的网格图&#xff08;标号由 1,1 开始&#xff09;上有 m 个探测器&#xff0c;每个探测器有个探测半径 r &#xff0c;问这 nn 个点中有多少个点能被探测到。 输入格式 第一行 3 个整数 n,m,r。 接下来 m 行&…...

JVM双亲委派机制

双亲委派模型是一种组织类加载器之间关系的一种规范,他的工作原理是:如果一个类加载器收到了类加载的请求,它不会自己去尝试加载这个类,而是把这个请求委派给父类加载器去完成,这样层层递进,最终所有的加载请求都被传到最顶层的启动类加载器中,只有当父类加载器无法完成这个加载…...

思科模拟器实验合集

目 录 实验一 常用网络命令的使用.................................... 1 实验二 双绞线制作.................................................. 12 实验三 网络模拟软件.............................................. 15 实验四 交换机基本配置..................…...

18.AUTOSAR 网络管理系统(一)

目录 1.为什么需要整车网络管理 2.本地唤醒和网络唤醒 3.小结 1.为什么需要整车网络管理 在描述AUTOSAR网络管理细节前&#xff0c;大家可以思考几个问题&#xff1a; 1.网络管理为整车系统提供了什么样的服务&#xff1f; 2.整车网络视角看&#xff0c;每个ECU的上下电是…...

802.11 MAC帧介绍

控制帧 RTS&#xff08;Request To Send&#xff09;&#xff1a;用于申请无线媒介的使用时间CTS&#xff08;Clear To Send&#xff09;&#xff1a;用于回复RTS帧ACK&#xff1a;对MAC帧的肯定确认PS-POLL&#xff1a;STA用于从AP中获取因省电模式而缓存的数据&#xff0c;只…...

【高阶数据结构】B-树详解

文章目录 1. 常见的搜索结构2. 问题提出使用平衡二叉树搜索树的缺陷使用哈希表的缺陷 3. B-树的概念4. B-树的插入分析插入过程分析插入过程总结 5. B-树的代码实现5.1 B-树的结点设计5.2 B-树的查找5.3 B-树的插入实现InsertKey插入和分裂测试 6. B-树的删除&#xff08;思想&…...

elementui常用组件-个人版(间断更新)

Dialog 对话框 el-dialog <el-dialogtitle"提示":visible.sync"dialogVisible"width"30%":before-close"handleClose"><span>这是一段信息</span><span slot"footer" class"dialog-footer"…...

无人机在化工消防救援中的应用,消防无人机应用场景分析

火灾对社会环境具有较大影响&#xff0c;因此需要重视消防灭火救援工作&#xff0c;注重现代化技术的运用&#xff0c;将无人机应用到救援过程并保障其应用质量。无人机是一项重要技术&#xff0c;便于消防灭火救援操作&#xff0c;使救援过程灵活展开&#xff0c;排除不利影响…...

java设计模式- 建造者模式

一 需求以及实现方式 1.1 需求描述 我们要创建一个表示汽车的复杂对象&#xff0c;汽车包含发动机、轮胎和座椅等部分。用传统方式创建&#xff0c;代码如下 1.2 传统实现方式 1.抽象类 public abstract class BuildCarAbstaract {//引擎public abstract void buildEng…...

【C++航海王:追寻罗杰的编程之路】类与对象你学会了吗?(下)

目录 1 -> 再谈构造函数1.1 -> 构造函数体赋值1.2 -> 初始化列表1.3 -> explicit关键字 2 -> static成员2.1 -> 概念2.2 -> 特性 3 -> 友元3.1 -> 友元函数3.2 -> 友元类 4 -> 内部类5 -> 匿名对象6 -> 拷贝对象时的一些编译器优化 1 -…...

解决TSP旅行商问题3个可以用Python编程的优化路径算法

旅行商问题&#xff08;Traveling Salesman Problem, TSP&#xff09;是一个经典的组合优化问题&#xff0c;它要求找到访问一系列城市并返回起点的最短可能路线&#xff0c;同时每个城市仅访问一次。这个问题是NP-hard的&#xff0c;意味着没有已知的多项式时间复杂度的精确算…...

10英寸安卓车载平板电脑丨ONERugged车载工业平板:解决农业工作效率

农业是人类社会的基石之一&#xff0c;而农业工作效率的提升一直是农民和农业专业人士关注的重要议题。随着技术的不断进步&#xff0c;车载工业平板成为了解决农业工作效率的创新解决方案。本文将探讨车载工业平板如何为农业带来巨大的改变&#xff0c;提高农民的工作效率和农…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...

Java多线程实现之Runnable接口深度解析

Java多线程实现之Runnable接口深度解析 一、Runnable接口概述1.1 接口定义1.2 与Thread类的关系1.3 使用Runnable接口的优势 二、Runnable接口的基本实现方式2.1 传统方式实现Runnable接口2.2 使用匿名内部类实现Runnable接口2.3 使用Lambda表达式实现Runnable接口 三、Runnabl…...

算法刷题-回溯

今天给大家分享的还是一道关于dfs回溯的问题&#xff0c;对于这类问题大家还是要多刷和总结&#xff0c;总体难度还是偏大。 对于回溯问题有几个关键点&#xff1a; 1.首先对于这类回溯可以节点可以随机选择的问题&#xff0c;要做mian函数中循环调用dfs&#xff08;i&#x…...

AT模式下的全局锁冲突如何解决?

一、全局锁冲突解决方案 1. 业务层重试机制&#xff08;推荐方案&#xff09; Service public class OrderService {GlobalTransactionalRetryable(maxAttempts 3, backoff Backoff(delay 100))public void createOrder(OrderDTO order) {// 库存扣减&#xff08;自动加全…...

[KCTF]CORE CrackMe v2.0

这个Reverse比较古老&#xff0c;已经有20多年了&#xff0c;但难度确实不小。 先查壳 upx压缩壳&#xff0c;0.72&#xff0c;废弃版本&#xff0c;工具无法解压。 反正不用IDA进行调试&#xff0c;直接x32dbg中&#xff0c;dump内存&#xff0c;保存后拖入IDA。 这里说一下…...