【记录帖】(No.003)从零打卡刷Leetcode


写在前边:

小詹一直觉得自己编程能力不强,想在网上刷题,又怕不能坚持。不知道有木有和小伙伴和小詹一样想找个人一起刷题呢?欢迎和小詹一起定期刷leetcode,每周一周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!欢迎小伙伴们把自己的思路在留言区分享出来噢


前期回顾:

【记录帖】(No.002)从零打卡刷Leetcode

【记录帖】(No.001)从零打卡刷Leetcode

上一期有留一个小bug让小伙伴们找,不知道多少人自己找到了啊?爱学习的人肯定自己去尝试了,肯定发现leetcode上运行结果发现输出不是预期的[7, 0, 8],而是像下边这样:

Finished in 36 ms
[7, 0.6999999999999993, 8.07, 1]

一个不合预期的地方是出现了小数,还有一个则是链表长度不合预期。其实,这个是除法导致的,这里的除法保留了小数部分,导致进位标志carry不是我们需要的整型0或者1了,所以出现了小数,另一方面进位的错误也导致在最高位的时候再次进了一位,即链表中多出了个1。修改方法很简单,只需要在两处carry位置进行类型转换,具体如下。或者注意''/''和“//”的区别,后者所除的结果仅保留商(整型),前者即存在小数。

carry = int(p.next.val / 10)  #int()强制转换为整型

上期没找出原因的小伙伴可以去改过来试试看噢~

No.3 Longest Substring without Repeating Characters

原题:

Given a string, find the length of the longest substring without repeating characters.

题目大意:给出一个字符串,找到最长的没有重复字符的子字符串,并返回该子字符串的长度。

例如:

Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

可能是前边的题目都大同小异,难度也接近。也有可能是人的思维有惯性,小詹又是利用循环嵌套遍历所有情况进行判断的,这种简单粗暴可以实现,但是效率很低。大体思路是:第一层循环从字符串的最左侧到最右侧第二个,即for i in range(0,len(s)-1),第二层循环则从第一层紧跟着的一个到最后一个字符。即for j in range(i+1,len(s));之后通过找出所有不重复的子字符串,比较长度得到最大长度的子字符串。代码如下:(需要注意当字符串长度为0或1的特殊情况)

def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_len = 0 #用这个值记录我们要返回的最长子字符串长度
        #当原字符串长度为0或1的特殊情况
        if (len(s) == 1 or len(s) == 0):
            max_len = len(s)
        #开始遍历每一个子字符串,并进行长度比较,得到最长的那个
        for i in range(0,len(s)-1):
            for j in range(i+1, len(s)):
                if s[j] in s[i:j]:
                    if j-i > max_len:
                        right = j
                        left = i
                        #这里小詹本想返回对应子字符串的左右索引值,之后发现题目没有要求
                        max_len = right-left
                    break
                elif j == len(s) - 1:
                    if max_len < j - i + 1:
                        max_len = j - i + 1
        return max_len

结果当然是可以通过的啦,然而时间效率方面很差很差,如图:

然而,我们不能满足于这种最低效率的实现结果。下边提出一个炒鸡牛逼的方法,非原创,小詹花了很久才搞明白其思路,其利用到了字典的方法。什么是字典?请自行补充知识噢(公众号有语法综述)。先放代码后再解释:

def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        #创建一个空字典,其存放的形式是“单字符:出现位置的索引”
        indexDict = {}
        #存放记录最大长度和当前循环下的长度
        maxLength = currMax = 0
        for i in range(len(s)):
            #这里是关键,小詹看了挺久的,小伙伴们比我强,应该比较快
            #这里是当s[i]没有在之前出现过,则当前长度currMax自动加一
            #当出现了重复字符,则比较当前找到的子字符串长度和历史最大长度
            #重点是这里i - indexDict[s[i]] - 1 的含义;代码后举例具体讲解
            if s[i] in indexDict and i - indexDict[s[i]] - 1 <= currMax:
                if maxLength < currMax:
                    maxLength = currMax
                currMax = i - indexDict[s[i]] - 1
            currMax = currMax + 1                
            indexDict[s[i]] = i 
        return maxLength if currMax < maxLength else currMax

代码里对应位置加入了注释,理解起来应该好很多了,这里举例说明下为什么【i - indexDict[s[i]] - 1】代表了当前找到子字符串的长度。

比如字符串'abcdadd',代码运行过程中一直迭代到i=3【对应字符d】时,都不满足s[i] in indexDict ,不执行条件语句,而是currMax依次加一,并且将字符信息以{s[i]:i}的形式存放在字典中。当继续迭代i=4时,进入条件语句,这里主要解释【i - indexDict[s[i]] - 1】,检测到了重复字符'a',之前该字符出现位置为i=0处即【indexDict[s[i]] =0】这时候当前检测到的无重复字符子串为'abcd',长度为【4-indexDict[s[i]] -1 = 4】。其他同此例。

往期推荐

Python系列之——在北京当房奴的日子~

反爬虫和反反爬虫(下篇)

本文分享自微信公众号 - 小詹学Python(xiaoxiaozhantongxue)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-06-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏怀英的自我修炼

考研英语-1-导学

英二图表作文要重视。总体而言,英语一会比英语二难点。不过就写作而言,英语二会比英语一有难度,毕竟图表作文并不好写。

12410
来自专栏钱塘大数据

中国互联网协会发布:《2018中国互联网发展报告》

在2018中国互联网大会闭幕论坛上,中国互联网协会正式发布《中国互联网发展报告2018》(以下简称《报告》)。《中国互联网发展报告》是由中国互联网协会与中国互联...

13750
来自专栏前端桃园

知识体系解决迷茫的你

最近在星球里群里都有小伙伴说道自己对未来的路比较迷茫,一旦闲下来就不知道自己改干啥,今天我这篇文章就是让你觉得一天给你 25 个小时你都不够用,觉得睡觉都是浪费...

22540
来自专栏腾讯高校合作

【倒计时7天】2018教育部-腾讯公司产学合作协同育人项目申请即将截止!

16220
来自专栏微信公众号:小白课代表

不只是软件,在线也可以免费下载百度文库了。

不管是学生,还是职场员工,下载各种文档几乎是不可避免的,各种XXX.docx,XXX.pptx更是家常便饭,人们最常用的就是百度文库,豆丁文库,道客巴巴这些下载...

44830
来自专栏钱塘大数据

理工男图解零维到十维空间,烧脑已过度,受不了啦!

让我们从一个点开始,和我们几何意义上的点一样,它没有大小、没有维度。它只是被想象出来的、作为标志一个位置的点。它什么也没有,空间、时间通通不存在,这就是零维度。

35230
来自专栏Ken的杂谈

【系统设置】CentOS 修改机器名

18430
来自专栏haifeiWu与他朋友们的专栏

复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

30940
来自专栏腾讯社交用户体验设计

ISUX Xcube智能一键生成H5

51620
来自专栏FSociety

SQL中GROUP BY用法示例

GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

5.2K20

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励