Python每日一练(20230506) 存在重复元素I、II、III

目录

1. 存在重复元素 Contains Duplicate I

2. 存在重复元素 Contains Duplicate II

3. 存在重复元素 Contains Duplicate III

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏


1. 存在重复元素 Contains Duplicate I

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false 。

示例 1:

输入:nums = [1,2,3,1]
输出:true

示例 2:

输入:nums = [1,2,3,4]
输出:false

示例 3:

输入:nums = [1,1,1,3,3,4,3,2,4,2]
输出:true

提示:

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

代码: 多种方法实现

from typing import List
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] == nums[j]:
                    return True
        return False

    def containsDuplicate2(self, nums: List[int]) -> bool:
        num_set = set()
        for num in nums:
            if num in num_set:
                return True
            num_set.add(num)
        return False

    def containsDuplicate3(self, nums: List[int]) -> bool:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False

    def containsDuplicate4(self, nums: List[int]) -> bool:
        return len(nums) != len(set(nums))


if __name__ == '__main__':
    s = Solution()
    nums = [1,2,3,1]
    print(s.containsDuplicate(nums))
    print(s.containsDuplicate2(nums))
    print(s.containsDuplicate3(nums))
    print(s.containsDuplicate4(nums))
    nums = [1,2,3,4]
    print(s.containsDuplicate(nums))
    print(s.containsDuplicate2(nums))
    print(s.containsDuplicate3(nums))
    print(s.containsDuplicate4(nums))
    nums = [1,1,1,3,3,4,3,2,4,2]
    print(s.containsDuplicate(nums))
    print(s.containsDuplicate2(nums))
    print(s.containsDuplicate3(nums))
    print(s.containsDuplicate4(nums))

输出:

True
True
True
True
False
False
False
False
True
True
True
True


2. 存在重复元素 Contains Duplicate II

给你一个整数数组 nums 和一个整数 k ,判断数组中是否存在两个 不同的索引 i 和 j ,满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在,返回 true ;否则,返回 false 。

示例 1:

输入:nums = [1,2,3,1], k = 3
输出:true

示例 2:

输入:nums = [1,0,1,1], k = 1
输出:true

示例 3:

输入:nums = [1,2,3,1,2,3], k = 2
输出:false

提示:

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • 0 <= k <= 10^5

代码: 多种方法实现

from typing import List
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, min(i + k + 1, n)):
                if nums[i] == nums[j]:
                    return True
        return False

    def containsNearbyDuplicate2(self, nums: List[int], k: int) -> bool:
        num_index = {}
        for i in range(len(nums)):
            if nums[i] in num_index and i - num_index[nums[i]] <= k:
                return True
            num_index[nums[i]] = i
        return False

    def containsNearbyDuplicate3(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        if k >= n:
            k = n - 1
        num_set = set(nums[:k + 1])
        if len(num_set) != k + 1:
            return True
        for i in range(k + 1, n):
            num_set.remove(nums[i - k - 1])
            if nums[i] in num_set:
                return True
            num_set.add(nums[i])
        return False


if __name__ == '__main__':
    s = Solution()
    nums = [1,2,3,1]
    print(s.containsNearbyDuplicate(nums, 3))
    print(s.containsNearbyDuplicate2(nums, 3))
    print(s.containsNearbyDuplicate3(nums, 3))
    nums = [1,0,1,1]
    print(s.containsNearbyDuplicate(nums, 1))
    print(s.containsNearbyDuplicate2(nums, 1))
    print(s.containsNearbyDuplicate3(nums, 1))
    nums = [1,2,3,1,2,3]
    print(s.containsNearbyDuplicate(nums, 2))
    print(s.containsNearbyDuplicate2(nums, 2))
    print(s.containsNearbyDuplicate3(nums, 2))

输出:

True
True
True
True
True
True
False
False
False


3. 存在重复元素 Contains Duplicate III

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j,使得 abs(nums[i] - nums[j]) <= t ,同时又满足 abs(i - j) <= k 

如果存在则返回 true,不存在返回 false

示例 1:

输入:nums = [1,2,3,1], k = 3, t = 0
输出:true

示例 2:

输入:nums = [1,0,1,1], k = 1, t = 2
输出:true

示例 3:

输入:nums = [1,5,9,1,5,9], k = 2, t = 3
输出:false

提示:

  • 0 <= nums.length <= 2 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
  • 0 <= k <= 10^4
  • 0 <= t <= 2^31 - 1

代码: 多种方法实现

from typing import List
import bisect
class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, min(i + k + 1, n)):
                if abs(nums[i] - nums[j]) <= t and abs(i - j) <= k:
                    return True
        return False

    def containsNearbyAlmostDuplicate2(self, nums: List[int], k: int, t: int) -> bool:
        n = len(nums)
        if t < 0 or k <= 0:
            return False
        bst = []
        for i in range(n):
            idx = bisect.bisect_left(bst, nums[i] - t)
            if idx < len(bst) and abs(bst[idx] - nums[i]) <= t:
                return True
            bisect.insort(bst, nums[i])
            if i >= k:
                bst.remove(nums[i - k])
        return False

    def containsNearbyAlmostDuplicate3(self, nums: List[int], k: int, t: int) -> bool:
        if t < 0 or k <= 0:
            return False
        n = len(nums)
        dic = dict()
        w = t + 1
        for i in range(n):
            m = nums[i] // w
            if m in dic:
                return True
            elif m - 1 in dic and abs(nums[i] - dic[m - 1]) < w:
                return True
            elif m + 1 in dic and abs(nums[i] - dic[m + 1]) < w:
                return True
            dic[m] = nums[i]
            if i >= k:
                del dic[nums[i - k] // w]
        return False


if __name__ == '__main__':
    s = Solution()
    nums = [1,2,3,1]
    print(s.containsNearbyAlmostDuplicate(nums, 3, 0))
    print(s.containsNearbyAlmostDuplicate2(nums, 3, 0))
    print(s.containsNearbyAlmostDuplicate3(nums, 3, 0))
    nums = [1,0,1,1]
    print(s.containsNearbyAlmostDuplicate(nums, 1, 2))
    print(s.containsNearbyAlmostDuplicate2(nums, 1, 2))
    print(s.containsNearbyAlmostDuplicate3(nums, 1, 2))
    nums = [1,5,9,1,5,9]
    print(s.containsNearbyAlmostDuplicate(nums, 2, 3))
    print(s.containsNearbyAlmostDuplicate2(nums, 2, 3))
    print(s.containsNearbyAlmostDuplicate3(nums, 2, 3))

输出:

True
True
True
True
True
True
False
False
False


🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力! 

🌟 收藏,你的青睐是我努力的方向! 

评论,你的意见是我进步的财富!  

 主页:https://hannyang.blog.csdn.net/

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/17303.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Linux 裸机篇(八)】I.MX6U EPIT 定时器中断、定时器按键消抖

目录 一、EPIT 定时器简介二、定时器按键消抖 一、EPIT 定时器简介 EPIT 的全称是&#xff1a; Enhanced Periodic Interrupt Timer&#xff0c;直译过来就是增强的周期中断定时器&#xff0c;它主要是完成周期性中断定时的。学过 STM32 的话应该知道&#xff0c; STM32 里面的…

电脑系统怎么选?Win?MacOS?Linux?

马上要学编程了&#xff0c;我们要学什么操作系统呢&#xff1f;是MacOS&#xff0c;还是Windows&#xff0c;或者是Linux或者其他&#xff01;那我们今天就来说说MacOS系统和Windows系统的优缺点&#xff0c;也介绍一下其他的系统。让你心里有底&#xff01; 1、Windows 首先当…

Neo4j导出和导入数据库

Neo4j 4.x版本和5.x版本的导出导入有区别&#xff0c;这里分开来讲。 1 4.x版本 1.1 准备 导入导出之前要先关闭neo4j服务。 .neo4j stop 1.2 数据导出 进入$NEO4J_HOME%/bin目录执行如下数据库导出命令&#xff1a; neo4j-admin dump --databaseneo4j --toF:/neo4j_bac…

《Netty》从零开始学netty源码(五十四)之PoolThreadLocalCache

PoolThreadLocalCache 前面讲到PoolThreadCache&#xff0c;它为线程提供内存缓存&#xff0c;当线程需要分配内存时可快速从其中获取&#xff0c;在Netty中用PoolThreadLocalCache来管理PoolThreadCache&#xff0c;它的数据结构如下&#xff1a; PoolThreadLocalCache相当…

Unity3D:内置着色器的用途和性能

推荐&#xff1a;将 NSDT场景编辑器 加入你的3D工具链 3D工具集&#xff1a; NSDT简石数字孪生 内置着色器的用途和性能 Unity 中的着色器是通过__材质__来使用的&#xff0c;材质本质上结合了着色器代码与纹理等参数。此处提供了关于着色器/材质关系的深入说明。 当选择材质…

延时队列的三种实现方案

延时队列的三种实现方案 什么是延时队列延时队列的应用场景基于Java DelayQueue的实现源码剖析 基于Redis的zset实现实现步骤Redis延时队列优势Redis延时队列劣势 基于RabbitMQ的延时队列实现TTL DXL(死信队列)插件实现 总结参考文章 什么是延时队列 在分布式系统中&#xff…

Java之多线程初阶2

目录 一.上节内容复习 1.进程和线程的区别 2.创建线程的四种方式 二.多线程的优点的代码展示 1.多线程的优点 2.代码实现 三.Thread类常用的方法 1.Thread类中的构造方法 2.Thread类中的属性 1.为线程命名并获取线程的名字 2.演示isDaemon() 3.演示isAlive() 4.演示…

ChatGPT写文章效果-ChatGPT写文章原创

ChatGPT写作程序&#xff1a;让文案创作更轻松 在当前数字化的时代&#xff0c;营销推广离不开文案创作。然而&#xff0c;写作对许多人来说可能是一项耗时而枯燥的任务。如果您曾经为写出较高质量的文案而苦恼过&#xff0c;那么ChatGPT写作程序正是为您而设计的。 ChatGPT是…

Python 模块

目录 1.模块导入语言 1.1 import 语句 1.2 from…import 语句​编辑 2. 搜索路径 3.命名空间和作用域 4.globals() 和 locals() 函数 5.reload() 函数 6.Python中的包 7.自定义模块及其调用 7.1 创建模块及__init__.py初始化文件 7.2 __init__.py的参数__all__ …

【vite+vue3.2 项目性能优化实战】打包体积分析插件rollup-plugin-visualizer视图分析

rollup-plugin-visualizer是一个用于Rollup构建工具的插件&#xff0c;它可以生成可视化的构建报告&#xff0c;帮助开发者更好地了解构建过程中的文件大小、依赖关系等信息。 使用rollup-plugin-visualizer插件&#xff0c;可以在构建完成后生成一个交互式的HTML报告&#xf…

从血缘进化论的角度,破解婆媳关系的世纪难题

从血缘进化论的角度&#xff0c;破解婆媳关系的世纪难题 有个粉丝的留言&#xff0c;很长很复杂&#xff0c;是关于他们家的婆媳关系问题。 青木老师&#xff0c;您好&#xff0c;我也有一些问题想咨询您&#xff0c;是关于婆媳关系的&#xff0c;字数有些多&#xff0c;分开…

【ElasticSearch】EQL操作相关

文章目录 EQL操作基础语法数据准备数据窗口搜索统计符合条件的事件事件序列 安全检测数据准备查看数据导入情况获取 regsvr32 事件的计数检查命令行参数检查恶意脚本加载检查攻击成功可能性 EQL操作 EQL 的全名是 Event Query Language (EQL)。事件查询语言&#xff08;EQL&…

【问题记录】flask开发blog

文章目录 小知识点问题1. 文章标签显示错误2. 文章状态无法回显&#xff08;open)3. 用户管理页面&#xff0c;图标无法显示4. BuildError5. 用户管理添加用户&#xff0c;使用重复的用户名会报错(open)6. 添加用户&#xff0c;不上传头像会报错(open)7. 部分标签删除时报错&am…

JAVA springboot创业实践学分管理系统idea开发mysql数据库web结构计算机java编程MVC

一、源码特点 idea springboot创业实践学分管理系统是一套完善的web设计系统mysql数据库MVC模式开发&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式 开发。 JAVA springboot创业实践学分管理系统ide…

Ubuntu搜狗输入法安装指南

Ubuntu搜狗输入法安装指南 Ubuntu搜狗输入法安装指南搜狗输入法已支持Ubuntu1604、1804、1910、2004、2010Ubuntu20.04及以上安装搜狗输入法步骤 Ubuntu搜狗输入法安装指南 下载地址&#xff1a;https://shurufa.sogou.com/ 计算为amd64的选择x86_64&#xff0c;以下教程来源…

2023Java商城毕业设计(附源码和数据库文件下载链接)Spring Boot + mysql + maven + mybatis-plus

2023Java商城毕业设计Spring Boot mysql maven mybatis-plus 用户注册用户登录修改密码商品列表&#xff08;分类模糊查询&#xff09;个人信息用户信息修改订单信息添加至购物车商品列表商铺详情商品详情商铺列表 资源目录如下&#xff1a;&#xff08;源码sql文件&#xf…

Linux入门2(常用命令)

Linux入门2 Linux常用命令快捷键基础命令文件查看命令文件编辑命令进程管理命令用户管理命令 Linux常用命令 快捷键 Ctrl Alt T打开终端 Ctrl shift 加号 终端字体放大 ctrl 减号 终端字体缩小 基础命令 sudo su 进入管理员目录 exit 返回到用户目录 ls 当前目录下的文…

Illustrator如何使用基础功能?

文章目录 0.引言1.菜单栏2.工具箱 0.引言 因科研等多场景需要进行绘图处理&#xff0c;笔者对Illustrator进行了学习&#xff0c;本文通过《Illustrator CC2018基础与实战》及其配套素材结合网上相关资料进行学习笔记总结&#xff0c;本文对软件界面基本功能进行阐述。    1…

K8s 安全是云安全的未来

导语 到 2025 年&#xff0c;保护 Kubernetes (K8s) 将被认为是云安全最重要的方面。 在最成功的组织中&#xff0c;CTO 和 CISO 已经意识到 Kubernetes 安全的重要性。 但是&#xff0c;虽然 Kubernetes 已经占 CTO 云支出的很大一部分&#xff0c;但 CISO 仍然有所落后。 大…

Android Studio开发图书管理系统APP

Android Studio开发项目图书管理系统项目视频展示&#xff1a; 点击进入图书管理系统项目视频 引 言 现在是一个信息高度发达的时代&#xff0c;伴随着科技的进步&#xff0c;文化的汲取&#xff0c;人们对于图书信息的了解与掌握也达到了一定的高度。尤其是学生对于知识的渴…