存在重复元素模块-三道题
文章目录
- 存在重复元素
- 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%的测试用例,如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识! 问题介绍 …...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
LangFlow技术架构分析
🔧 LangFlow 的可视化技术栈 前端节点编辑器 底层框架:基于 (一个现代化的 React 节点绘图库) 功能: 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...
