前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【打卡贴】(No.003)从零开始刷LeetCode

【打卡贴】(No.003)从零开始刷LeetCode

作者头像
PM小王
发布2019-07-01 15:31:36
2800
发布2019-07-01 15:31:36
举报
文章被收录于专栏:程序员小王

NO.3无重复字符的最长子串

原题:

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

示例 1:

代码语言:javascript
复制
输入: "abcabcbb"输出: 3
解释: 无重复字符的最长子串是 "abc",
     其长度为 3。

示例 2:

代码语言:javascript
复制
输入: "bbbbb"输出: 1
解释: 无重复字符的最长子串是 "b",
     其长度为 1。

示例 3:

代码语言:javascript
复制
输入: "pwwkew"输出: 3
解释: 无重复字符的最长子串是 "wke",
     其长度为 3。
     请注意,答案必须是一个子串,
     "pwke" 是一个子序列 而不是子串。

昨天上课老师刚好在讲字符串,没有听课偷偷把这个题给刷了,快下课的时候已经在写第二种方法了,废话不说直接上解析。

解析:

首先想到就是简单粗暴的逐个检查所有的子字符串,看它是否不含有重复的字符。不用想执行效率很低。

代码语言:javascript
复制
ef Substring(s):
    if s == '':
        return 0
    if len(s) == 1:
        return 1
    record = 0
    for i, char in enumerate(s):
        li1 = set()
        for st in s[i:]:
            if st not in li1:
                li1.add(st)
                if len(li1) > record:
                    record = len(li1)
            else:
                break
    return record

第二种方法解题思路:

借助一个辅助键值对来存储某个元素最后一次出现的下标。用一个整形变量存储当前无重复字符的子串开始的下标。

代码语言:javascript
复制
def Substring(s):
    max_len = 0
# 判断传入的字符串是否为空
   if s is None or len(s) == 0:
       return max_len
# 定义一个字典,
#存储不重复的字符和字符所在的下标
   str_dict = {}
 # 存储每次循环中最长的子串长度
   one_max = 0
# 记录最近重复字符所在的位置+1
   start = 0
   for i in range(len(s)):
# 判断当前字符是否在字典中和当前字符的下标
#是否大于等于最近重复字符的所在位置
    if s[i] in str_dict and str_dict[s[i]] >= start:
# 记录当前字符的值+1
        start = str_dict[s[i]] + 1
# 在此次循环中,最大的不重复子串的长度
    one_max = i - start + 1
 # 把当前位置覆盖字典中的位置
    str_dict[s[i]] = i
# 比较此次循环的最大不重复子串长度
#和历史循环最大不重复子串长度
    max_len = max(max_len, one_max)
   return max_len

中秋假期的第一天释放了自己的天性在床上瘫了一天,所以更新比较晚,今天的文章开赞赏了,嘻嘻,希望明天午饭加个鸡腿。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-09-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员小王 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档