Python3 无重复字符的最长子串的实现

题目:

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例:

示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。

思路:

这道题会很自然的想到暴力解法,就是按位递增依次检查子串是否重复,并记下目前最大的子串长度,如果重复就从下一位索引处的字符开始重新检查。下面是代码实现:

class Solution:
 def lengthOfLongestSubstring(self, s: str) -> int:
 # 最长子串的长度
 max_len = 0
 # 存放字符的字典
 char_dict = {}
 index = 0
 while s[index:].__len__() >= max_len:
  # 当前最长子串长度
  current_len = 0
  for item in s[index:]:
  old_index = char_dict.get(item)
  if old_index is not None:
   index = old_index + 1
   char_dict.clear()
   break
  char_dict[item] = index
  index += 1
  current_len += 1
  if current_len > max_len:
  max_len = current_len
 return max_len

开始只是想跑通,没想到超出了时间限制。看起来代码显得是有点啰嗦,但是思路应该是没有问题的,我们还是从遍历的角度来优化。

优化:

在上面的代码中,当遇到重复字符时,遍历的起始点就往后挪一位,但其实两个重复字符之间的部分是不会重复的,比如字符串fbacdadfeed,在第一次从 f 开始遍历遇到重复字符即第二个 a 的时候,下一次遍历不应该从 b 开始,而是应该从前一个重复字符的后一个字符即 c 开始。

确定思想,并多次优化后的代码如下:

class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
    char_dict = {}
    start, end, max_len = -1, 0, 0
    str_len = s.__len__()
    while end < str_len:
      char = s[end]
      if char in char_dict:
        old_index = char_dict[char]
        if old_index > start:
         start = old_index
      diff = end -start
      if diff > max_len:
        max_len = diff
      char_dict[char] = end
      end += 1
    return max_len;

这里使用了内置的.__len__()方法来获取字符串长度而不是len(),并且使用了多个看似多此一举的临时变量来存储值,比如char和diff,都是为了节省时间,蚊子小也是肉嘛。

结果也是 ok 的:

Python3 无重复字符的最长子串的实现

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

时间: 2019-10-08

用位图排序无重复数据集实例代码(C++版)

<Programming Pearls>(编程珠玑下载)第一章讲述了如何用位图排序无重复的数据集,整个思想很简洁,今天实践了下. 一.主要思想 位图排序的思想就是在内存中申请一块连续的空间作为位图,初始时将位图的每一位都置为0,然后依次读取待排序文件的整数,将整数所在的位设置为1,最后扫描位图,如果某一位为1,则说明这个数存在,输出到已排序文件.比如待排序的数据S={3,0,4,1,7,2,5},max(S)=7,我们可以设置一个八位的位图B,将位图的每一位初始为0,即B=[0,0,0,0,0

.net中string无重复数字的实现方法

复制代码 代码如下: //string strText = "1334677999";实现无重复        public static string qu(string lab)        {            string strResult = string.Empty;            for (int intIdx = 0; intIdx < lab.Length; intIdx++)            {                if (st

JS使用正则表达式除去字符串中重复字符的方法

本文实例讲述了JS使用正则表达式除去字符串中重复字符的方法.分享给大家供大家参考,具体如下: 这里演示一个简单的JavaScript正则表达式实例,将一串含有重复字符串中的多余字符滤除掉,请运行查看效果. 具体代码如下: <html> <head> <title>利用正则表达法除去字符串中的重复字符</title> </head> <body> <script language="javascript">

一个匹配重复字符正规表达式

前几天做邮件地址过滤,要求把连续重复多次的邮件地址删除,试了很多次,才试出了这个正规表达式. /([a-z0-9A-Z])\1{2,}/ 匹配3个或以上的重复字符,比如aaaa,bbb,cccc,000 /[a-z0-9A-Z]{3,}/ 匹配3个或以上的字符,比如abc,ab34

匹配5到10位无重复数字的正则表达式

对于有重复的5到10位数字可以使用\d{5,10} 这样的正则 无重复的5到10位数字我考虑了一下还不会,最然只好查网上. 有一个版本还不错,反正RegexBuddy测试通过了. 复制代码 代码如下: ^(?!\d*?(\d)\d*?\1)\d{5,10}$ 对于(?!---(--)---\1)这样的形式我还没有研究透,有时间我真要细细研究. 上一个php的例子: 复制代码 代码如下: <?php $str = '123456789'; $search = '/^(?!\d*?(\d)\d*?\

asp.net 无重复随机数代码

复制代码 代码如下: /// <summary> /// 产生无重复随机数 /// </summary> /// <param name="num">个数</param> /// <param name="minValue">最小数</param> /// <param name="maxValue">最大数</param> /// <retur

Python3如何解决字符编码问题详解

编码 因为计算机只能处理数字,如果要处理文本,就必须先把文本转换为数字才能处理.最早的计算机在设计时采用8个比特(bit)作为一个字节(byte),所以,一个字节能表示的最大的整数就是255(二进制11111111=十进制255),如果要表示更大的整数,就必须用更多的字节.比如两个字节可以表示的最大整数是65535,4个字节可以表示的最大整数是4294967295. 由于计算机是美国人发明的,因此,最早只有127个字母被编码到计算机里,也就是大小写英文字母.数字和一些符号,这个编码表被称为ASC

可用的ASP无重复数字随机函数, 数组实现, 并应用于随机显示记录集

经我们站长测试可用的ASP无重复数字随机函数, 数组实现, 并应用于随机显示记录集作用: 本函数适用于随机显示小数量的随机不重复数字 本函数适用于显示小数量的随机不重复记录集 为了不影响效率, 上限超过一千, 不建议使用本函数 shawl.qiu 2006-09-06  http://blog.csdn.net/btbtd 主内容: 函数及应用函数随机显示100条记录 linenum  复制代码 代码如下: <%       dim rs, rNum       dim temp       s

REPLICATE 以指定的次数重复字符表达式

使用REPLICATE(以指定的次数重复字符表达式)函数 REPLICATE函数用于以指定的次数重复字符表达式. 语法: REPLICATE (character_expression,integer_expression) 参数说明: character_expression:由字符数据组成的字母数字表达式. integer_expression:正整数,指定重复次数,如果该参数为负数,则返回空字符串. 示例: 使用REPLICACE函数,将指定的数据重复两次输出.程序运行结果如图1所示. 图

C#删除字符串中重复字符的方法

本文实例讲述了C#删除字符串中重复字符的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: #region 删除重复字符  string s = "sdfffffsrlkjesgljfdg03940864e5=_0R9DTGR98YUI\\|||'\\???fdf///";  Response.Write("<br/>String:" + s + "<br/>Result:");  IEnumerable