存在重复元素模块-三道题
文章目录
- 存在重复元素
- 217. 存在重复元素
- 219. 存在重复元素 II
- 220. 存在重复元素 III (SortedList+二分)
- 小结
存在重复元素
217. 存在重复元素
题目链接:217. 存在重复元素
题目大意:给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false 。
注意:(1)1 <= nums.length <= 10510^5105;(2)−109-10^9−109 <= nums[i] <= 10910^9109。
示例:
输入:nums = [1,2,3,1]
输出:true输入:nums = [1,2,3,4]
输出:false输入:nums = [1,1,1,3,3,4,3,2,4,2]
输出:true
参考代码:
class Solution:def containsDuplicate(self, nums: List[int]) -> bool:# 取巧return len(set(nums)) != len(nums)'''# hash maphash_map = dict()for num in nums:if num not in hash_map:hash_map[num] = 1else:return Truereturn False''''''# 计数器counter = collections.Counter(nums)for num in nums:if counter[num] > 1:return Truereturn False'''
- (1)取巧办法:
- 时间复杂度:O(1)O(1)O(1)。
- 空间复杂度:O(n)O(n)O(n),其中 nnn 是 numsnumsnums 的长度。
- (2)hash map办法:
- 时间复杂度:O(n)O(n)O(n)
- 空间复杂度:O(n)O(n)O(n)
- (3)计数器办法:
- 时间复杂度:O(n)O(n)O(n)
- 空间复杂度:O(n)O(n)O(n)
219. 存在重复元素 II
题目链接:219. 存在重复元素 II
题目大意:给你一个整数数组 nums 和一个整数 k ,判断数组中是否存在两个 不同的索引 i 和 j ,满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在,返回 true ;否则,返回 false 。
注意:(1)1 <= nums.length <= 10510^5105;(2)−109-10^9−109 <= nums[i] <= 10910^9109;(3)0 <= k <= 10510^5105。
示例:
输入:nums = [1,2,3,1], k = 3
输出:true输入:nums = [1,0,1,1], k = 1
输出:true输入:nums = [1,2,3,1,2,3], k = 2
输出:false
参考代码:
class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:hash_map = dict()for i,num in enumerate(nums):if num not in hash_map:hash_map[num] = ielse:if i - hash_map[num] <= k:return Truehash_map[num] = ireturn False
- 时间复杂度:O(n)O(n)O(n),其中 nnn 是 numsnumsnums 的长度。
- 空间复杂度:O(n)O(n)O(n)
220. 存在重复元素 III (SortedList+二分)
题目链接:220. 存在重复元素 III
题目大意:给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j,使得 abs(nums[i] - nums[j]) <= t ,同时又满足 abs(i - j) <= k 。
如果存在则返回 true,不存在返回 false。
注意:(1)0 <= nums.length <= 2∗1042 * 10^42∗104;(2)−231-2^{31}−231 <= nums[i] <= 231−12^{31} - 1231−1;(3)0 <= k <= 10410^4104;(4)0 <= t <= 231−12^{31} - 1231−1。
示例:
输入:nums = [1,2,3,1], k = 3, t = 0
输出:true输入:nums = [1,0,1,1], k = 1, t = 2
输出:true输入:nums = [1,5,9,1,5,9], k = 2, t = 3
输出:false
参考代码:
from sortedcontainers import SortedList class Solution:def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:wd = SortedList()n = len(nums)for i in range(n):# print(wd)if i>k:wd.remove(nums[i-1-k])wd.add(nums[i])idx = bisect.bisect_left(wd,nums[i])if idx>0 and abs(wd[idx]-wd[idx-1])<=t:return Trueif idx<len(wd)-1 and abs(wd[idx+1]-wd[idx])<=t:return Truereturn False
- 时间复杂度:O(nlogk)O(n \log{k})O(nlogk),其中 nnn为数组的长度,TreeSet 基于红黑树,查找和插入都是 O(logk)O(\log{k})O(logk) 复杂度。
- 空间复杂度:O(k)O(k)O(k)
小结
- 这三道题挺有趣的,之间的关联并不是非常大,不过都用到了哈希表这个容器,是一套不错的练习题,总结记录一下,便于快速查询,加油(23.3.3)。
相关文章:
存在重复元素模块-三道题
文章目录存在重复元素217. 存在重复元素219. 存在重复元素 II220. 存在重复元素 III (SortedList二分)小结存在重复元素 217. 存在重复元素 题目链接:217. 存在重复元素 题目大意:给你一个整数数组 nums 。如果任一值在数组中出…...
3种方法删除7-Zip压缩包的密码
7-Zip压缩软件是一款完全免费且开源的软件,不仅能压缩和解压7-Zip压缩包,还能给压缩包设置打开密码。 有些小伙伴可能会遇到这样的问题,7-Zip压缩包设置密码后,过了一段时间不需要密码保护了,或者一不小心忘记了密码&…...
Codeforces Round 855 (Div. 3)(A~F)
A. Is It a Cat?定义满足条件的字符串为:其中仅可能含有meow四种字母的大小写,而且相同种类的字母必须挨在一起,四种字母的顺序必须按照meow排列。给出一个字母串,求是否满足条件。思路:感觉是个很麻烦的模拟。首先把…...
【SpringCloud】SpringCloud详解之Feign实战
目录前言SpringCloud Feign远程服务调用一.需求二.两个服务的yml配置和访问路径三.使用RestTemplate远程调用(order服务内编写)四.使用Feign远程调用(order服务内配置)五.自定义Feign配置(order服务内配置)六.Feign配置日志(oder服务内配置)七.Feign调优(order服务内配置)八.抽…...
tuts4you上lena‘s40个crackme(1)
本来是不打算写文章了,因为懒,想以后通过录屏的形式保存一下自己学的路程。但奈何开学后一直没找到机会,在宿舍也不愿意大吼大叫的讲东西,只好再写写文章了 最近学了一些汇编语言和逆向工程,所以就想通过这40给题目来看…...
研讨会回顾 | Perforce版本控制工具Helix Core入华十年,携手龙智赋能企业大规模研发
2023年2月28日,龙智联合全球领先的数字资产管理工具厂商Perforce共同举办Perforce on Tour网络研讨会,主题为“赋能‘大’研发,助力‘快’交付”。 作为Perforce Helix Core产品在中国地区的唯一授权合作伙伴,龙智董事长何明女士为…...
C++ vscode 开发环境搭建
C vscode 开发环境搭建 笔记内容: C vscode 开发环境搭建准备了解g命令编译调试掌握使用launch.json和tasks.json配置文件编译调试了解使用cmake构建 git: https://github.com/weichangk/hellocpp/tree/master/vscodecmakecpp 环境搭建准备 安装vscode安装qt&a…...
ANR系列(二)——ANR监听方案之SyncBarrier
前言 在项目中经常遇到了手机假死问题,无规律的偶现问题,大量频繁随机操作后,便会出现假死,整个应用无法操作,不会响应事件,会发生各种奇怪的ANR,且trace不固定。而SyncBarrier是其中的罪魁祸首…...
【完美解决】应用程序无法正常启动(0xc000007b)请单击“确定”关闭应用程序
年期安装CorelDRAW X8 (64-Bit),安装完成之后运行一点毛病都没有,可是过了两三个月,再打开就出现“应用程序无法正常启动(0xc000007b)请单击“确定”关闭应用程序”这个提示框,如下图示 出现这个问题我就上网查找,无非…...
.NET基础加强第二课--静态成员,静态类
类 实例类 默认是实例类 静态类 在类前加上static ,就是静态类 静态类中,所有包含的成员必须是静态成员 实例成员是属于具体某个对象的 举例代码 Person p1 new Person(); p1.Age 20; p1.Name “张三”; class Person { public string Name { get; set;…...
【UML+OOPC嵌入式C语言开发】使用C语言实现一个面向对象语言才能够实现的类
文章目录简述OOPC开发环境知识讲解函数示例类的实现示例接口实现示例(前面两部分有点无聊,如果大家没兴趣看可以直接从知识讲解开始看) 简述OOPC oopc,是一种轻量级的面向对象的C语言编程框架, LW_OOPC是Light-Weight …...
软件测试自动化Java篇【Selenium+Junit 5】
文章目录Selenium环境部署自动化测试例子常见的元素操作窗口等待浏览器的操作弹窗选择器执行脚本文件上传浏览器参数Junit 5导入依赖Junit 4 和 Junit5 注解对比断言测试顺序参数化单参数多参数动态参数测试套件指定类来运行测试用例指定包名来运行包下测试用例Selenium 为什么…...
Clip:学习笔记
Clip 文章目录Clip前言一、原理1.1 摘要1.2 引言1.3 方法1.4 实验1.4.1 zero-shot Transfer1.4.2 PROMPT ENGINEERING AND ENSEMBLING1.5 局限性二、总结前言 阅读论文: Learning Transferable Visual Models From Natural Language Supervision CLIP 论文逐段精读…...
STM32CubexMX与FreeRTOS学习
目录 LED与EXTI配置 基本定时器使用 软件定时器 在HAL库中实现printf 重点--记得自己添加头文件 队列实现 二值信号量实现 计数信号量实现 DMA实现 ADC配置 RTC配置 看门狗 窗口看门狗 FreeRTOS结合MX软件开发,基础配置直接生成,我们只…...
Master Slave 主从同步错误 Slave_IO_Running:NO/Slave_SQL_Running: No
Master Slave 主从同步错误 Slave_IO_Running:NO Slave_SQL_Running:Yes #在Slave库上查看状态 mysql> show slave status\G Slave_IO_Running: No Slave_SQL_Running: Yes #重启master库:service mysqld restart mysql> show master status; ------------…...
JavaScript函数之prototype原型和原型链
文章目录1. 原型2. 显式和隐式原型3. 原型链3.1 访问顺序4. instanceof4.1 如何判断1. 原型 函数的prototype属性 每个函数都有一个prototype属性,它默认指向一个Object空对象(即:原型对象)。原型对象中有一个属性constructor&a…...
从上海分时电价机制调整看转供电用户电能计费
安科瑞 耿敏花2022年12月16日,上海市发改委发布《关于进一步完善我市分时电价机制有关事项的通知》(沪发改价管〔2022〕50号)。通知明确上海分时电价机制,一般工商业及其他两部制、大工业两部制用电夏季(7、8、9月)和冬季…...
TypeScript类型体操:获取数组中元素对象属性的值作为新类型
title: TypeScript类型体操:获取数组中元素对象属性的值作为新类型 date: 2023-03-03 20:58:24 categories: TypeScript类型体操 tags: TypeScript类型体操TypeScript 首先先说获取数组中元素对象属性的值作为新类型的解决方案 使用 as const 强调不可变数组使用 …...
npm,yarn和pnpm
npm扁平的node_modules结构比如项目依赖了A 和 C,而 A 和 C 依赖了不同版本的 B1.0 和 B2.0,D也依赖B1.0, node_modules 结构如下:node_modules ├── A1.0.0 ├── B1.0.0 └── C1.0.0└── node_modules└── B2.0.0C依赖的B2.0因为版…...
【算法】【数组与矩阵模块】在排好序的矩阵中找数,时间复杂度O(M+N)
目录前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本思考感悟写在最后前言 当前所有算法都使用测试用例运行过,但是不保证100%的测试用例,如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识! 问题介绍 …...
别再被Linux的free命令骗了!手把手教你读懂‘可用内存’和‘实际空闲内存’的区别
别再被Linux的free命令骗了!手把手教你读懂‘可用内存’和‘实际空闲内存’的区别 刚接触Linux服务器管理时,看到free -m输出里那个触目惊心的"free"数值,我的第一反应是:"天哪,内存快用完了࿰…...
多云配置管理工具MCP:统一编排AWS、GCP等云资源的实战指南
1. 项目概述:一个高效的多云配置管理工具 最近在梳理团队的基础设施配置时,发现了一个挺有意思的开源项目,叫 malminhas/mcp 。乍一看这个名字,你可能会有点懵,这缩写代表什么?其实,MCP 在这里…...
使用Taotoken后API调用延迟稳定在可接受范围且账单清晰可见
🚀 告别海外账号与网络限制!稳定直连全球优质大模型,限时半价接入中。 👉 点击领取海量免费额度 使用Taotoken后API调用延迟稳定在可接受范围且账单清晰可见 1. 引言 对于需要集成大模型能力的开发者而言,除了模型效…...
华为MateBook D 2018 BIOS隐藏选项实战:手动解锁TPM2.0迎战Win11
1. 为什么需要手动解锁TPM2.0 去年Windows 11正式发布时,很多华为MateBook D 2018用户都遇到了一个尴尬问题:明明硬件配置完全达标,却因为BIOS里找不到TPM2.0开关而无法升级。我当时也卡在这个环节整整两天,直到发现原来TPM功能被…...
TrollInstallerX技术深度解析:iOS 14.0-16.6.1系统权限获取完全指南
TrollInstallerX技术深度解析:iOS 14.0-16.6.1系统权限获取完全指南 【免费下载链接】TrollInstallerX A TrollStore installer for iOS 14.0 - 16.6.1 项目地址: https://gitcode.com/gh_mirrors/tr/TrollInstallerX TrollInstallerX是一款面向iOS 14.0至16…...
Get-cookies.txt-LOCALLY:浏览器Cookie本地导出终极指南
Get-cookies.txt-LOCALLY:浏览器Cookie本地导出终极指南 【免费下载链接】Get-cookies.txt-LOCALLY Get cookies.txt, NEVER send information outside. 项目地址: https://gitcode.com/gh_mirrors/ge/Get-cookies.txt-LOCALLY 在数字时代,浏览器…...
Taotoken模型广场在项目技术选型阶段提供的便利性体验
🚀 告别海外账号与网络限制!稳定直连全球优质大模型,限时半价接入中。 👉 点击领取海量免费额度 Taotoken模型广场在项目技术选型阶段提供的便利性体验 启动一个新的AI项目时,技术决策者面临的首要挑战往往是模型选型…...
凡亿AD22-原理图页大小设置及注意事项(实操笔记)
核心前提:原理图页大小需在绘制元器件、导线前设置(前期准备工作),避免绘制完成后调整尺寸,导致元器件、导线布局混乱,节省后期调整时间。一、为什么要设置原理图页大小?软件默认的原理图页尺寸…...
构建研发效能平台:从数据采集到智能洞察的工程实践
1. 项目概述:从“任务控制”到现代研发效能平台在软件研发领域,尤其是当团队规模从几个人扩展到几十甚至上百人时,一个经典的管理困境就会浮现:如何清晰地知道每个工程师在做什么?项目的真实进度如何?代码质…...
基于MCP协议构建技术生态分析工具:架构设计与工程实践
1. 项目概述:一个技术生态分析工具的诞生最近在折腾一个挺有意思的东西,一个叫apifyforge/tech-ecosystem-analysis-mcp的项目。光看这个名字,可能有点唬人,但说白了,它就是一个用来“解剖”技术生态系统的工具。想象一…...
