【滑动窗口】 LCR 057. 存在重复元素 III

2024-01-27 16:04

本文主要是介绍【滑动窗口】 LCR 057. 存在重复元素 III,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

LCR 057. 存在重复元素 III

解题思路

  • 使用一个 HashMap(map)来存储元素的 ID 和元素值
  • 将元素的 ID 计算为元素值除以窗口大小 w,w 的计算为 t + 1
  • 遍历数组,对于每个元素:
  • 检查是否存在相同 ID 的元素,如果存在,说明找到了索引差值不超过 k 的两个元素,直接返回 true
  • 检查相邻的两个 ID,如果它们的差值为 1,再检查对应的元素值是否差值不超过 t,如果是,则返回 true
  • 将当前元素的 ID 和值存入 map 中
  • 如果当前索引大于等于 k,移除最早加入窗口的元素,即索引为 i - k 的元素
  • 如果遍历完成都没有找到符合条件的元素对,则返回 false。
class Solution {public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {int n = nums.length;Map<Long,Long> map = new HashMap<Long,Long>();// 存储元素ID和元素值long w = (long)t + 1;for(int i = 0; i < n; i++){long id = getId(nums[i],w);if(map.containsKey(id)){return true;}if(map.containsKey(id - 1) && Math.abs(nums[i] - map.get(id - 1)) < w){return true;}if(map.containsKey(id + 1) && Math.abs(nums[i] - map.get(id + 1)) < w){return true;}map.put(id,(long)nums[i]);if(i >= k){map.remove(getId(nums[i - k],w));}}return false;}public long getId(long x,long w){if(x >= 0){return x / w;}return (x + 1) / w - 1;}
}

这篇关于【滑动窗口】 LCR 057. 存在重复元素 III的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/650768

相关文章

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

easyui同时验证账户格式和ajax是否存在

accountName: {validator: function (value, param) {if (!/^[a-zA-Z][a-zA-Z0-9_]{3,15}$/i.test(value)) {$.fn.validatebox.defaults.rules.accountName.message = '账户名称不合法(字母开头,允许4-16字节,允许字母数字下划线)';return fal

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G,设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断,有两种做法:(本文的实现均基于邻接矩阵存储方式的图) 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历,遍历过程中遇到结点i就表示存在路径start->i,故只需判断每个结点i是否就是stop

遮罩,在指定元素上进行遮罩

废话不多说,直接上代码: ps:依赖 jquer.js 1.首先,定义一个 Overlay.js  代码如下: /*遮罩 Overlay js 对象*/function Overlay(options){//{targetId:'',viewHtml:'',viewWidth:'',viewHeight:''}try{this.state=false;//遮罩状态 true 激活,f

使用JS/Jquery获得父窗口的几个方法(笔记)

<pre name="code" class="javascript">取父窗口的元素方法:$(selector, window.parent.document);那么你取父窗口的父窗口的元素就可以用:$(selector, window.parent.parent.document);如题: $(selector, window.top.document);//获得顶级窗口里面的元素 $(

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

C# 防止按钮botton重复“点击”的方法

在使用C#的按钮控件的时候,经常我们想如果出现了多次点击的时候只让其在执行的时候只响应一次。这个时候很多人可能会想到使用Enable=false, 但是实际情况是还是会被多次触发,因为C#采用的是消息队列机制,这个时候我们只需要在Enable = true 之前加一句 Application.DoEvents();就能达到防止重复点击的问题。 private void btnGenerateSh

JS和jQuery获取节点的兄弟,父级,子级元素

原文转自http://blog.csdn.net/duanshuyong/article/details/7562423 先说一下JS的获取方法,其要比JQUERY的方法麻烦很多,后面以JQUERY的方法作对比。 JS的方法会比JQUERY麻烦很多,主要则是因为FF浏览器,FF浏览器会把你的换行也当最DOM元素。 <div id="test"><div></div><div></div