寫(xiě)在前邊：

小詹一直覺(jué)得自己編程能力不強(qiáng)，想在網(wǎng)上刷題，又怕不能堅(jiān)持。不知道有木有和小伙伴和小詹一樣想找個(gè)人一起刷題呢？歡迎和小詹一起定期刷leetcode，每周一周五更新一題，每一題都吃透，歡迎一題多解，尋找最優(yōu)解！歡迎小伙伴們把自己的思路在留言區(qū)分享出來(lái)噢

前期回顧：【記錄帖】（No.002）從零打卡刷Leetcode

【歡迎關(guān)注個(gè)人微信公眾號(hào)【小詹學(xué)python】】

上一期有留一個(gè)小bug讓小伙伴們找，不知道多少人自己找到了啊？愛(ài)學(xué)習(xí)的人肯定自己去嘗試了，肯定發(fā)現(xiàn)leetcode上運(yùn)行結(jié)果發(fā)現(xiàn)輸出不是預(yù)期的[7, 0, 8]，而是像下邊這樣：

Finished in 36 ms [7, 0.6999999999999993, 8.07, 1] 復(fù)制代碼

一個(gè)不合預(yù)期的地方是出現(xiàn)了小數(shù)，還有一個(gè)則是鏈表長(zhǎng)度不合預(yù)期。其實(shí)，這個(gè)是除法導(dǎo)致的，這里的除法保留了小數(shù)部分，導(dǎo)致進(jìn)位標(biāo)志carry不是我們需要的整型0或者1了，所以出現(xiàn)了小數(shù)，另一方面進(jìn)位的錯(cuò)誤也導(dǎo)致在最高位的時(shí)候再次進(jìn)了一位，即鏈表中多出了個(gè)1。修改方法很簡(jiǎn)單，只需要在兩處carry位置進(jìn)行類型轉(zhuǎn)換，具體如下。或者注意''/''和“//”的區(qū)別，后者所除的結(jié)果僅保留商（整型），前者即存在小數(shù)。

carry = int(p.next.val / 10) #int()強(qiáng)制轉(zhuǎn)換為整型 復(fù)制代碼

上期沒(méi)找出原因的小伙伴可以去改過(guò)來(lái)試試看噢~

No.3 Longest Substring without Repeating Characters

原題：

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

題目大意：給出一個(gè)字符串，找到最長(zhǎng)的沒(méi)有重復(fù)字符的子字符串，并返回該子字符串的長(zhǎng)度。

例如：

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. 復(fù)制代碼

可能是前邊的題目都大同小異，難度也接近。也有可能是人的思維有慣性，小詹又是利用循環(huán)嵌套遍歷所有情況進(jìn)行判斷的，這種簡(jiǎn)單粗暴可以實(shí)現(xiàn)，但是效率很低。大體思路是：第一層循環(huán)從字符串的最左側(cè)到最右側(cè)第二個(gè)，即for i in range(0,len(s)-1)，第二層循環(huán)則從第一層緊跟著的一個(gè)到最后一個(gè)字符。即for j in range(i+1,len(s));之后通過(guò)找出所有不重復(fù)的子字符串，比較長(zhǎng)度得到最大長(zhǎng)度的子字符串。代碼如下：（需要注意當(dāng)字符串長(zhǎng)度為0或1的特殊情況）

def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""max_len = 0 #用這個(gè)值記錄我們要返回的最長(zhǎng)子字符串長(zhǎng)度#當(dāng)原字符串長(zhǎng)度為0或1的特殊情況if (len(s) == 1 or len(s) == 0):max_len = len(s)#開(kāi)始遍歷每一個(gè)子字符串，并進(jìn)行長(zhǎng)度比較，得到最長(zhǎng)的那個(gè)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 = jleft = i#這里小詹本想返回對(duì)應(yīng)子字符串的左右索引值，之后發(fā)現(xiàn)題目沒(méi)有要求max_len = right-leftbreakelif j == len(s) - 1:if max_len < j - i + 1:max_len = j - i + 1return max_len 復(fù)制代碼

結(jié)果當(dāng)然是可以通過(guò)的啦，然而時(shí)間效率方面很差很差，如圖：

然而，我們不能滿足于這種最低效率的實(shí)現(xiàn)結(jié)果。下邊提出一個(gè)炒雞牛逼的方法，非原創(chuàng)，小詹花了很久才搞明白其思路，其利用到了字典的方法。什么是字典？請(qǐng)自行補(bǔ)充知識(shí)噢（公眾號(hào)有語(yǔ)法綜述）。先放代碼后再解釋：

def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""#創(chuàng)建一個(gè)空字典，其存放的形式是“單字符:出現(xiàn)位置的索引”indexDict = {}#存放記錄最大長(zhǎng)度和當(dāng)前循環(huán)下的長(zhǎng)度maxLength = currMax = 0for i in range(len(s)):#這里是關(guān)鍵，小詹看了挺久的，小伙伴們比我強(qiáng)，應(yīng)該比較快#這里是當(dāng)s[i]沒(méi)有在之前出現(xiàn)過(guò)，則當(dāng)前長(zhǎng)度currMax自動(dòng)加一#當(dāng)出現(xiàn)了重復(fù)字符，則比較當(dāng)前找到的子字符串長(zhǎng)度和歷史最大長(zhǎng)度#重點(diǎn)是這里i - indexDict[s[i]] - 1 的含義；代碼后舉例具體講解if s[i] in indexDict and i - indexDict[s[i]] - 1 <= currMax:if maxLength < currMax:maxLength = currMaxcurrMax = i - indexDict[s[i]] - 1currMax = currMax + 1 indexDict[s[i]] = i return maxLength if currMax < maxLength else currMax 復(fù)制代碼

代碼里對(duì)應(yīng)位置加入了注釋，理解起來(lái)應(yīng)該好很多了，這里舉例說(shuō)明下為什么【i - indexDict[s[i]] - 1】代表了當(dāng)前找到子字符串的長(zhǎng)度。

比如字符串'abcdadd'，代碼運(yùn)行過(guò)程中一直迭代到i=3【對(duì)應(yīng)字符d】時(shí)，都不滿足s[i] in indexDict ,不執(zhí)行條件語(yǔ)句，而是currMax依次加一，并且將字符信息以{s[i]:i}的形式存放在字典中。當(dāng)繼續(xù)迭代i=4時(shí)，進(jìn)入條件語(yǔ)句，這里主要解釋【i - indexDict[s[i]] - 1】，檢測(cè)到了重復(fù)字符'a'，之前該字符出現(xiàn)位置為i=0處即【indexDict[s[i]] =0】這時(shí)候當(dāng)前檢測(cè)到的無(wú)重復(fù)字符子串為'abcd'，長(zhǎng)度為【4-indexDict[s[i]] -1 = 4】。其他同此例。

往期推薦(關(guān)注微信公眾號(hào)【小詹學(xué)python】)

Python系列之——在北京當(dāng)房奴的日子~

反爬蟲(chóng)和反反爬蟲(chóng)（下篇）

?

總結(jié)

以上是生活随笔為你收集整理的拿什么拯救你，我的面试之——从零打卡刷Leetcode（No.003）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。