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

本文主要是介绍算法每日一题: 使用循环数组所有元素相等的最少秒数 | 哈希,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

题目: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.chinasem.cn/article/680364

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

Hadoop数据压缩使用介绍

一、压缩原则 (1)运算密集型的Job,少用压缩 (2)IO密集型的Job,多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1)为了支持多种压缩/解压缩算法,Hadoop引入了编码/解码器 2)要在Hadoop中启用压缩,可以配置如下参数

Makefile简明使用教程

文章目录 规则makefile文件的基本语法:加在命令前的特殊符号:.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具,常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个