深圳东莞网站建设,个人做网站怎么赚钱,做爰在线观看网站,网站制作素材网站本文为Python算法题集之一的代码示例
题目3#xff1a;无重复字符的最长子串
说明#xff1a;给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 a…本文为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): # 双循环遍历、集合查重iLenlen(s)iMaxsublen0for iIdx in range(iLen):for iJdx in range(iIdx1, 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): # 集合查重双指针iLenlen(s)iMaxsublen, ileft, iright 0, 0, 0set_substr set()while irightiLen:if s[iright] in set_substr:set_substr.remove(s[ileft])ileft 1else:set_substr.add(s[iright])iMaxsublen max(iMaxsublen, iright-ileft1)iright1return 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 ~
