从零打卡刷Leetcode

资源干货第一时间送达!

写在前边:

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

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

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

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

No.3 Longest Substring without Repeating Characters

原题:

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

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

例如:

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

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

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

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

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180601G0A89U00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券