Python算法题集_无重复字符的最长子串
本文为Python算法题集之一的代码示例
题目3:无重复字符的最长子串
说明:给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
- 感慨:本题很特殊,特别特殊,超级无敌特殊!!!
程序员没有一个没写过字符串处理,没有一个没写过查找字符串子串
问题是谁都能写,可是写出来就是原形毕露,稍不留神,就要贻笑大方
大虾们是高手,十年练剑,深藏不露,都是传说中十步杀一人,千里不留行的人物
如果本文写得笨拙浅薄,还请大虾们多多包涵,高抬贵手~~
本题求解有两个重点工作
一是在子串中进行字符查重
可以使用基本查重【集合中查询子元素】、字典查重【哈希值,值为数字】、下标查重【ord(char)为下标,数组元素为数字】
二是对字符串进行遍历找出所有子串
可使用双重循环、单循环单指针、双指针【滑动窗口】
注意:代码运行每次速度都不同,估计服务器负载有波动
注意:代码运行每次速度都不同,估计服务器负载有波动
注意:代码运行每次速度都不同,估计服务器负载有波动
-
新手基本型【基本查重+双重循环】,无脑遍历,注定超时
用双重循环遍历所有子串,字符查重则可以采用集合
set去重查重或者字符串查子串函数查重。此算法颇为无脑,算是初学程序者的作品,肯定会超时,就不给它表现的机会了def longest_unique_substr_newbie(s): # 双循环遍历、集合查重iLen=len(s)iMaxsublen=0for iIdx in range(iLen):for iJdx in range(iIdx+1, iLen-1):if len(set(s[iIdx:iJdx])) == iJdx-iIdx:iMaxsublen = max(iMaxsublen, iJdx-iIdx)return iMaxsublenprint(longest_unique_substr_newbie('abcabcbb')) # 运行结果 3
-
下标查重+双重循环,有所改善,超过77%

def longest_unique_substr_ext1(s): # 下标查重+双重循环iLen = len(s)iMaxsublen = 0icharcount = [0] * 128ileft, iright = 0, 0while iright < iLen:icharcount[ord(s[iright])] += 1while icharcount[ord(s[iright])] > 1:icharcount[ord(s[ileft])] -= 1ileft += 1iMaxsublen = max(iMaxsublen, iright - ileft + 1)iright += 1return iMaxsublenprint(longest_unique_substr_ext1('abcabcbb')) # 运行结果 3 -
字典查重【单判断】+双指针,有所改善,超过77%

def longest_unique_substr_ext2(s): # 字典查重+双指针iLen = len(s)iMaxsublen = 0dictwindow = {}ileft, iright = 0, 0while iright < iLen:if s[iright] in dictwindow:ileft = max(ileft, dictwindow[s[iright]] + 1)dictwindow[s[iright]] = irightiMaxsublen = max(iMaxsublen, iright - ileft + 1)iright += 1return iMaxsublenprint(longest_unique_substr_ext2('abcabcbb')) # 运行结果 3 -
集合查重+双指针,表现良好,超过87%

def longest_unique_substr_ext3(s): # 集合查重+双指针iLen=len(s)iMaxsublen, ileft, iright = 0, 0, 0set_substr = set()while iright<iLen:if s[iright] in set_substr:set_substr.remove(s[ileft])ileft += 1else:set_substr.add(s[iright])iMaxsublen = max(iMaxsublen, iright-ileft+1)iright+=1return iMaxsublenprint(longest_unique_substr_ext3('abcabcbb')) # 运行结果 3 -
集合查重+单循环单指针,有所改善,超过77%

def longest_unique_substr_ext4(s): # 集合查重+单循环单指针iLen = len(s)iMaxsublen = 0set_substr = set()istart = 0for iIdx in range(iLen):while s[iIdx] in set_substr:set_substr.remove(s[istart])istart += 1set_substr.add(s[iIdx])iMaxsublen = max(iMaxsublen, iIdx - istart + 1)return iMaxsublenprint(longest_unique_substr_ext4('abcabcbb')) # 运行结果 3 -
下标查重+双指针,有所改善,超过76%

def longest_unique_substr_ext5(s): # ASC码下标定位,双指针iLen = len(s)iMaxsublen = 0char_index = [-1] * 128ileft, iright = 0, 0while iright < iLen:if char_index[ord(s[iright])] >= ileft:ileft = char_index[ord(s[iright])] + 1char_index[ord(s[iright])] = irightiMaxsublen = max(iMaxsublen, iright - ileft + 1)iright += 1return iMaxsublenprint(longest_unique_substr_ext5('abcabcbb')) # 运行结果 3 -
字典查重【双判断】+双指针,表现良好,超过87%

def longest_unique_substr_ext6(s): # 字典查重+双指针iLen = len(s)iMaxsublen = 0dictwindow = {}ileft, iright = 0, 0while iright < iLen:if s[iright] in dictwindow and dictwindow[s[iright]] >= ileft:ileft = dictwindow[s[iright]] + 1dictwindow[s[iright]] = irightiMaxsublen = max(iMaxsublen, iright - ileft + 1)iright += 1return iMaxsublenprint(longest_unique_substr_ext6('abcabcbb')) # 运行结果 3 -
下标查重+单循环单指针,表现良好,超过88

def longest_unique_substr_ext7(s): # 下标查重+单循环单指针iLen = len(s)iMaxsublen, istart = 0, 0dictwindow = {}for iIdx in range(iLen):if s[iIdx] in dictwindow and dictwindow[s[iIdx]] >= istart:istart = dictwindow[s[iIdx]] + 1dictwindow[s[iIdx]] = iIdxiMaxsublen = max(iMaxsublen, iIdx - istart + 1)return iMaxsublenprint(longest_unique_substr_ext7('abcabcbb')) # 运行结果 3 -
下标查重+单循环单指针跳跃,华山论剑,谁是英雄!

def longest_unique_substr_ext8(s): # 下标查重+单循环单指针iLen = len(s)iMaxsublen, istart = 0, 0listchar = [-1] * 128for iIdx in range(iLen):if listchar[ord(s[iIdx])] >= istart:istart = listchar[ord(s[iIdx])] + 1listchar[ord(s[iIdx])] = iIdxiMaxsublen = max(iMaxsublen, iIdx - istart + 1)return iMaxsublenprint(longest_unique_substr_ext8('abcabcbb')) # 运行结果 3一日练,一日功,一日不练十日空
may the odds be ever in your favor ~
相关文章:
Python算法题集_无重复字符的最长子串
本文为Python算法题集之一的代码示例 题目3:无重复字符的最长子串 说明:给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "a…...
12.Elasticsearch应用(十二)
Elasticsearch应用(十二) 1.单机ES面临的问题 海量数据存储问题单点故障问题 2.ES集群如何解决上面的问题 海量数据存储解决问题: 将索引库从逻辑上拆分为N个分片(Shard),存储到多个节点单点故障问题&a…...
linux -- 内存管理 -- SLAB分配器
SLAB分配器(slab allocator) SLAB分配器用于小内存空间管理,基本思想是:先利用页面分配器分配出单个或多个连续的物理页面,然后再此基础上将整块页面分割为多个相等的小内存单元,来满足小内存空间分配的需…...
【MySQL】学习如何通过DQL进行数据库数据的条件查询
🌈个人主页: Aileen_0v0 🔥热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 💫个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-63IIm2s5sIhQfsfy {font-family:"trebuchet ms",verdana,arial,sans-serif;font-siz…...
TS:子类型关系
子类型关系 1、概念1.1 里氏替换原则1.2 自反性1.3 传递性 2、顶端类型 和 尾端类型3、字面量类型4、undefined 和 null5、枚举类型6、函数类型6.1 变型6.1.1 协变6.1.2 逆变6.1.3 双变 6.2 函数类型间的子类型关系6.2.1 函数参数数量6.2.2 函数参数类型A、非严格函数类型检查B…...
IDEA插件(MyBatis Log Free)
引言 在Java开发中,MyBatis 是一款广泛使用的持久层框架,它简化了SQL映射并提供了强大的数据访问能力。为了更好地调试和优化MyBatis应用中的SQL语句执行,一款名为 MyBatis Log Free 的 IntelliJ IDEA 插件应运而生。这款插件旨在帮助开发者…...
Redis(八)哨兵机制(sentinel)
文章目录 哨兵机制案例认识异常 哨兵运行流程及选举原理主观下线(Subjectively Down)ODown客观下线(Objectively Down)选举出领导者哨兵选出新master过程 哨兵使用建议 哨兵机制 吹哨人巡查监控后台master主机是否故障,如果故障了根据投票数自动将某一个从库转换为新…...
[数据结构]-哈希
前言 作者:小蜗牛向前冲 名言:我可以接受失败,但我不能接受放弃 如果觉的博主的文章还不错的话,还请点赞,收藏,关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 本期学习目标&…...
宝塔控制面板配置SSL证书实现网站HTTPS
宝塔安装SSL证书提前申请好SSL证书,如果还没有,先去Gworg里面申请,一般几分钟就可以下来,申请地址:首页-Gworg官方店-淘宝网 一、登录邮箱下载:Gworg证书文件目录 ,都会有以下五个文件夹。宝塔…...
elasticsearch优化总结
参考: https://docs.docker.com/manuals/ Manuals | Docker Docs Run Elasticsearch locally | Elasticsearch Guide [8.12] | Elastic 让你的ES查询性能起飞:Elasticsearch 查询优化攻略“一网打尽” - 知乎...
图论第三天|127. 单词接龙 841.钥匙和房间 463. 岛屿的周长 1971. 寻找图中是否存在路径 684.冗余连接 685.冗余连接II
目录 Leetcode127. 单词接龙Leetcode841.钥匙和房间Leetcode463. 岛屿的周长Leetcode1971. 寻找图中是否存在路径Leetcode684.冗余连接Leetcode685.冗余连接II Leetcode127. 单词接龙 文章链接:代码随想录 题目链接:127. 单词接龙 思路:广搜搜…...
react的高阶函数HOC:
React 的高阶组件(Higher-Order Component,HOC)是一种用于复用组件逻辑的模式。它是一个函数,接收一个组件作为参数,并返回一个新的增强过的组件。 HOC 可以用于实现以下功能: 代码复用:通过将…...
STM32——中断系统和外部中断EXTI
一、中断 1.1中断系统 中断系统是管理和执行中断的逻辑结构; 1.2中断 系统在执行主程序过程中,出现了特定的触发条件(触发源),系统停止执行当前程序,转而去执行中断程序,执行完毕后…...
使用uniApp+vue3+Vite4+pinia+sass技术栈构建微信小程序
使用uniApp的cli模式安装,可以使用vscode开发。不用再单独去下载HBuilderX. 1.基础安装 vue3tsuniapp 方法一: npx degit dcloudio/uni-preset-vue#vite-ts my-vue3-project方法二:可以去uni-preset-vue的vite分支下选择vite-ts直接下载zi…...
npm 被滥用 -- 有人上传了 700 多个武林外传切片视频
Sonatype 安全研究团队最近曝光了一起滥用 npm 的案例 —— 他们发现在 npm 上托管的 748 个软件包实际上是视频文件。 据介绍,这些软件包每个大小约为 54.5MB,包名以 “wlwz” 为前缀,并附带了代表日期的数字。根据时间戳显示,这…...
代码随想录算法训练营29期|day34 任务以及具体任务
第八章 贪心算法 part03 1005.K次取反后最大化的数组和 class Solution {public int largestSumAfterKNegations(int[] nums, int K) {// 将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小nums IntStream.of(nums).boxed().sorted((o1, o2) -> Math.ab…...
LeetCode 每日一题 2024/1/22-2024/1/28
记录了初步解题思路 以及本地实现代码;并不一定为最优 也希望大家能一起探讨 一起进步 目录 1/22 670. 最大交换1/23 2765. 最长交替子数组1/24 2865. 美丽塔 I1/25 2859. 计算 K 置位下标对应元素的和1/26 2846. 边权重均等查询1/27 2861. 最大合金数1/28 365. 水壶…...
好用的学习与开发工具
1. 首推 UTools 官网地址 uTools官网 - 新一代效率工具平台 介绍 uTools 是一个极简、插件化的现代桌面软件,通过自由选配丰富的插件,打造得心应手的工具集合。 通过快捷键(默认 alt space )就可以快速呼出这个搜索框。你可…...
(自用)learnOpenGL学习总结-高级OpenGL-立方体贴图
ok终于来到了立方体贴图了,在这里面我们可以加入好看的天空包围盒,这样的画我们的背景就不再是黑色的了! 首先,立方体贴图和前面的sampler2D贴图一样,不过是6个2D组成的立方体而已。 那么为什么要把6个组合在一起呢&…...
【计算机网络】——TCP协议
📑前言 本文主要是【计算机网络】——传输层TCP协议的文章,如果有什么需要改进的地方还请大佬指出⛺️ 🎬作者简介:大家好,我是青衿🥇 ☁️博客首页:CSDN主页放风讲故事 🌄每日一句…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
接口自动化测试:HttpRunner基础
相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具,支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议,涵盖接口测试、性能测试、数字体验监测等测试类型…...
LRU 缓存机制详解与实现(Java版) + 力扣解决
📌 LRU 缓存机制详解与实现(Java版) 一、📖 问题背景 在日常开发中,我们经常会使用 缓存(Cache) 来提升性能。但由于内存有限,缓存不可能无限增长,于是需要策略决定&am…...
打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...
