Python小白 Leetcode刷題歷程 No.1-No.5 兩數(shù)之和壤巷、兩數(shù)相加邑彪、無(wú)重復(fù)字符的最長(zhǎng)子串、尋找兩個(gè)有序數(shù)組的中位數(shù)胧华、最長(zhǎng)回文子串

寫在前面：

作為一個(gè)計(jì)算機(jī)院的大學(xué)生寄症，總覺得僅僅在學(xué)校粗略的學(xué)習(xí)計(jì)算機(jī)專業(yè)課是不夠的，尤其是假期大量的空檔期矩动，作為一個(gè)小白有巧，實(shí)習(xí)也莫得路子，又不想白白耗費(fèi)時(shí)間悲没。于是選擇了Leetcode這個(gè)平臺(tái)來刷題庫(kù)篮迎。編程我只學(xué)過基礎(chǔ)的C語(yǔ)言，現(xiàn)在在自學(xué)Python，所以用Python3.8刷題庫(kù)√鸪鳎現(xiàn)在我Python掌握的還不是很熟練享言，算法什么的也還沒學(xué)，就先不考慮算法上的優(yōu)化了渗鬼，單純以解題為目的览露，復(fù)雜程度什么的以后有時(shí)間再優(yōu)化。計(jì)劃順序五個(gè)題寫一篇日志譬胎，希望其他初學(xué)編程的人起到一些幫助差牛，寫算是對(duì)自己學(xué)習(xí)歷程的一個(gè)見證了吧。

有一起刷LeetCode的可以關(guān)注我一下堰乔，我會(huì)一直發(fā)LeetCode題庫(kù)Python3解法的偏化，也可以一起探討励翼。

覺得有用的話可以點(diǎn)贊關(guān)注下哦着降，謝謝大家！
········································································································································································
題解框架：

    1.題目儒士，難度
    2.題干,題目描述
    3.題解代碼（Python3（不是Python苟翻，是Python3））
    4.或許有用的知識(shí)點(diǎn)（不一定有）
    5.解題思路
    6.優(yōu)解代碼及分析（當(dāng)我發(fā)現(xiàn)有比我寫的好很多的代碼和思路我就會(huì)寫在這里）

········································································································································································

No.1.兩數(shù)之和

難度：簡(jiǎn)單
題目描述：

在這里插入圖片描述

題解代碼（Python3.8）

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)-1):  
            for j in range(i+1,len(nums)):
                if nums[i] + nums[j] == target:
                    return [i,j]

解題思路：
暴力方法韵卤，運(yùn)用兩個(gè)for循環(huán)遍歷數(shù)組完成表達(dá)式s[i] + s[j]的遍歷，因?yàn)榧臃ú挥脜^(qū)分s[i]和s[j]的順序崇猫，因此i屬于range(len(nums)-1)沈条，j屬于range(i+1,len(nums))，判斷是否有s[i] + s[j] = sum即可诅炉，因?yàn)橹恍枰祷豙i,j],所以只需要在兩個(gè)for循環(huán)內(nèi)return [i,j]即可跳出兩層for循環(huán)蜡歹。

No.2.兩數(shù)相加

難度：中等
題目描述：

在這里插入圖片描述

題解代碼（Python3.8）

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        def add(a,b,c):
            if not( a or b ):
                return ListNode(1) if c else None
            a = a if a else ListNode(0)
            b = b if b else ListNode(0)
            val = a.val + b.val + c
            c= val/10 if val>=10 else 0
            a.val = val%10
            a.next = add(a.next,b.next,int(c))
            return a
        return add(l1,l2,0)

或許有用的知識(shí)點(diǎn)：
ListNode的一些介紹：
變量值=List Node.val
指針指向下一節(jié)點(diǎn)=List Node.next

在這里插入圖片描述

解題思路：
這個(gè)其實(shí)可以類比加法器，兩個(gè)List Node中每一位相加涕烧，得到一個(gè)結(jié)果和一個(gè)進(jìn)位月而，結(jié)果存在L1中該位上，進(jìn)位加在L1..next上议纯。我們可以把這一過程定義為函數(shù)add父款，然后對(duì)add進(jìn)行遞歸即可。

No.3.無(wú)重復(fù)字符的最長(zhǎng)子串

難度：中等
題目描述：

在這里插入圖片描述

題解代碼（Python3.8）

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        left = 0
        lookup = set()                                #定義為set形式去重
        max_len = 0
        cur_len = 0
        for i in range(len(s)):
            cur_len += 1
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:
                max_len = cur_len
            lookup.add(s[i])
        return max_len

或許有用的知識(shí)點(diǎn)：
set(list)函數(shù)可以將list中重復(fù)元素過濾痹扇，set是無(wú)序的铛漓，set.add(key)可以在set中添加元素，set.remove(key)可以在set中刪除元素鲫构。
滑動(dòng)窗口：其實(shí)就是一個(gè)隊(duì)列,比如例題中的 abcabcbb浓恶，進(jìn)入這個(gè)隊(duì)列（窗口）為 abc 滿足題目要求，當(dāng)再進(jìn)入 a结笨，隊(duì)列變成了 abca包晰，這時(shí)候不滿足要求湿镀。所以，我們要移動(dòng)這個(gè)隊(duì)列伐憾！我們只要把隊(duì)列的左邊的元素移出就行了勉痴，直到滿足題目要求！一直維持這樣的隊(duì)列树肃，找出隊(duì)列出現(xiàn)最長(zhǎng)的長(zhǎng)度時(shí)候蒸矛，求出解！

解題思路：
暴力方法胸嘴，先單列出len(s)=0和len(s)=1的情況雏掠，再對(duì)其他情況進(jìn)行循環(huán)求解。設(shè)置一個(gè)起始位置下標(biāo)j=0劣像，一重for循環(huán)遍歷i in range(1,len(s)),第二重for循環(huán)遍歷m in range(j,i)乡话。再把k置零，第二重循環(huán)中耳奕，每次s[m] != s[i] 則k++绑青，若k == i-j 則說明s[j]到s[i]無(wú)重復(fù)字符，將將其長(zhǎng)度與max1比較即可屋群。若出現(xiàn)s[m] == s[i]則令j=m+1闸婴，k置零。

NO.4.尋找兩個(gè)有序數(shù)組的中位數(shù)

難度：困難
題目描述:

在這里插入圖片描述

題解代碼（Python3.8）

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        n=len(nums1)+len(nums2)       
        nums1=nums1+nums2
        nums1.sort()
        if n%2 != 0:
            num = nums1[(n-1)//2]
        else:
            num = (nums1[n//2]+nums1[(n//2)-1])/2
        return num

或許有用的知識(shí)點(diǎn)：
看到了復(fù)雜度為O(log(m+n))和有序數(shù)列谓晌，不難想到使用「二分查找」來解決掠拳。
這是408考試的原題癞揉，含金量還是比較高的纸肉。

解題思路：
按題目要求，復(fù)雜度應(yīng)為 O(log(m + n))喊熟，應(yīng)采用二分算法柏肪，當(dāng)時(shí)我還沒學(xué)過，就直接冒泡排序了芥牌。
這道題應(yīng)該是難在算法上烦味，我沒考慮算法，冒泡排序完按奇偶項(xiàng)取中位數(shù)即可壁拉。

優(yōu)解代碼及分析：
優(yōu)解代碼（Python3.8）

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m, n = len(nums1), len(nums2)

        # 這里為了保證nums1一定是長(zhǎng)度較小的數(shù)組
        if m > n:
            nums1, nums2, m, n = nums2, nums1, n, m

        # 題目給定數(shù)組不會(huì)同時(shí)為空谬俄，也就是m^2+n^2≠0，由于m≤n弃理，故只要n≠0即可
        if not n:
            raise ValueError("數(shù)組長(zhǎng)度不同時(shí)為零")

        i_min, i_max = 0, m
       
        # left集合元素?cái)?shù)量溃论，如果m+n是奇數(shù)，left比right多一個(gè)數(shù)據(jù)
        count_of_left = (m + n + 1) // 2  

        while i_min <= i_max:
            i = (i_min + i_max) // 2                # left有i個(gè)nums1的元素
            j = count_of_left - i                   # left有j個(gè)nums2的元素
            if i > 0 and nums1[i - 1] > nums2[j]:
                i_max = i - 1                       # i太大痘昌，要減少
            elif i < m and nums1[i] < nums2[j - 1]:
                i_min = i + 1                       # i太小钥勋，要增加
            else:
                if i == 0:
                    max_of_left = nums2[j - 1]
                elif j == 0:
                    max_of_left = nums1[i - 1]
                else:
                    max_of_left = max(nums1[i - 1], nums2[j - 1])

                if (m + n) % 2:
                    return float(max_of_left)               # 結(jié)果是浮點(diǎn)數(shù)

                if i == m:
                    min_of_right = nums2[j]
                elif j == n:
                    min_of_right = nums1[i]
                else:
                    min_of_right = min(nums1[i], nums2[j])

                return (max_of_left + min_of_right) / 2.0   # 結(jié)果為浮點(diǎn)數(shù)

分析：

在這里插入圖片描述

在這里插入圖片描述

No.5.最長(zhǎng)回文子串

難度：中等
題目描述：

在這里插入圖片描述

題解代碼（Python3.8）

class Solution:
    def longestPalindrome(self, s: str) -> str:
        l=len(s)
        if l==0:
            sm=""
        if l==1 or s[::]==s[::-1]:
            sm=s
        else:
            dm=1
            sm=s[0]
            l=len(s)
            for i in range(l-1):
                for j in range(i+1,l):
                    d=j-i+1
                    if d>dm:
                        if (i+j)%2 == 0:
                            if s[i: (i+j)//2 ] == s[j: (i+j)//2 :-1]:
                                sm=s[i:j+1]
                                dm=d
                        else:
                            if s[i: ((i+j)//2)+1 ] == s[j: (i+j)//2 :-1]:
                                sm=s[i:j+1] 
                                dm=d     
        return sm

或許有用的知識(shí)點(diǎn)：
切片操作：通常一個(gè)切片操作要提供三個(gè)參數(shù) [start_index: stop_index: step] ：
start_index是切片的起始位置
stop_index是切片的結(jié)束位置（不包括）
step可以不提供炬转，默認(rèn)值是1，步長(zhǎng)值不能為0算灸，不然會(huì)報(bào)錯(cuò)ValueError扼劈。

在這里插入圖片描述

在這里插入圖片描述

解題思路
對(duì)于沒有算法基礎(chǔ)的我來說荐吵，Python的切片功能極其好用，他為我減少了一階的復(fù)雜度赊瞬。我們先用兩個(gè)for循環(huán)遍歷所有的s[i]到s[j]區(qū)間捍靠，對(duì)其正向切片和反向切片，若值相同森逮，即為一個(gè)回文子串榨婆，與最長(zhǎng)回文子串比較長(zhǎng)度即可。

優(yōu)解代碼及分析：
優(yōu)解代碼（Python3.8）

class Solution:
    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        if size < 2:
            return s

        dp = [[False for _ in range(size)] for _ in range(size)]

        max_len = 1
        start = 0

        for i in range(size):
            dp[i][i] = True

        for j in range(1, size):
            for i in range(0, j):
                if s[i] == s[j]:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                else:
                    dp[i][j] = False

                if dp[i][j]:
                    cur_len = j - i + 1
                    if cur_len > max_len:
                        max_len = cur_len
                        start = i
        return s[start:start + max_len]

分析：
1褒侧、思考狀態(tài)
狀態(tài)先嘗試“題目問什么良风，就把什么設(shè)置為狀態(tài)”。然后考慮“狀態(tài)如何轉(zhuǎn)移”闷供，如果“狀態(tài)轉(zhuǎn)移方程”不容易得到烟央，嘗試修改定義，目的仍然是為了方便得到“狀態(tài)轉(zhuǎn)移方程”歪脏。
2疑俭、思考狀態(tài)轉(zhuǎn)移方程（核心、難點(diǎn)）
狀態(tài)轉(zhuǎn)移方程是非常重要的婿失，是動(dòng)態(tài)規(guī)劃的核心钞艇，也是難點(diǎn)，起到承上啟下的作用豪硅。
技巧是分類討論哩照。對(duì)狀態(tài)空間進(jìn)行分類，思考最優(yōu)子結(jié)構(gòu)到底是什么懒浮。即大問題的最優(yōu)解如何由小問題的最優(yōu)解得到飘弧。
歸納“狀態(tài)轉(zhuǎn)移方程”是一個(gè)很靈活的事情，得具體問題具體分析砚著，除了掌握經(jīng)典的動(dòng)態(tài)規(guī)劃問題以外次伶，還需要多做題。如果是針對(duì)面試稽穆，請(qǐng)自行把握難度冠王，我個(gè)人覺得掌握常見問題的動(dòng)態(tài)規(guī)劃解法，明白動(dòng)態(tài)規(guī)劃的本質(zhì)就是打表格秧骑，從一個(gè)小規(guī)模問題出發(fā)版确，逐步得到大問題的解扣囊，并記錄過程。動(dòng)態(tài)規(guī)劃依然是“空間換時(shí)間”思想的體現(xiàn)绒疗。
3侵歇、思考初始化
初始化是非常重要的，一步錯(cuò)吓蘑，步步錯(cuò)惕虑，初始化狀態(tài)一定要設(shè)置對(duì)，才可能得到正確的結(jié)果磨镶。
角度 1：直接從狀態(tài)的語(yǔ)義出發(fā)溃蔫；
角度 2：如果狀態(tài)的語(yǔ)義不好思考，就考慮“狀態(tài)轉(zhuǎn)移方程”的邊界需要什么樣初始化的條件琳猫；
角度 3：從“狀態(tài)轉(zhuǎn)移方程”方程的下標(biāo)看是否需要多設(shè)置一行伟叛、一列表示“哨兵”，這樣可以避免一些邊界的討論脐嫂，使得代碼變得比較短统刮。
4、思考輸出
有些時(shí)候是最后一個(gè)狀態(tài)账千，有些時(shí)候可能會(huì)綜合所有計(jì)算過的狀態(tài)侥蒙。
5、思考狀態(tài)壓縮
“狀態(tài)壓縮”會(huì)使得代碼難于理解匀奏，初學(xué)的時(shí)候可以不一步到位鞭衩。先把代碼寫正確，然后再思考狀態(tài)壓縮娃善。
狀態(tài)壓縮在有一種情況下是很有必要的论衍，那就是狀態(tài)空間非常龐大的時(shí)候（處理海量數(shù)據(jù)），此時(shí)空間不夠用会放，就必須狀態(tài)壓縮饲齐。
這道題比較煩人的是判斷回文子串。因此需要一種能夠快速判斷原字符串的所有子串是否是回文子串的方法咧最，于是想到了“動(dòng)態(tài)規(guī)劃”。
“動(dòng)態(tài)規(guī)劃”最關(guān)鍵的步驟是想清楚“狀態(tài)如何轉(zhuǎn)移”御雕，事實(shí)上矢沿，“回文”是天然具有“狀態(tài)轉(zhuǎn)移”性質(zhì)的：
一個(gè)回文去掉兩頭以后，剩下的部分依然是回文（這里暫不討論邊界）酸纲。
依然從回文串的定義展開討論：
1捣鲸、如果一個(gè)字符串的頭尾兩個(gè)字符都不相等，那么這個(gè)字符串一定不是回文串闽坡；
2栽惶、如果一個(gè)字符串的頭尾兩個(gè)字符相等愁溜，才有必要繼續(xù)判斷下去。
（1）如果里面的子串是回文外厂，整體就是回文串冕象；
（2）如果里面的子串不是回文串，整體就不是回文串汁蝶。
即在頭尾字符相等的情況下渐扮，里面子串的回文性質(zhì)據(jù)定了整個(gè)子串的回文性質(zhì)，這就是狀態(tài)轉(zhuǎn)移掖棉。因此可以把“狀態(tài)”定義為原字符串的一個(gè)子串是否為回文子串墓律。
第 1 步：定義狀態(tài)
dp[i][j] 表示子串 s[i, j] 是否為回文子串。
第 2 步：思考狀態(tài)轉(zhuǎn)移方程
這一步在做分類討論（根據(jù)頭尾字符是否相等）幔亥，根據(jù)上面的分析得到：
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
分析這個(gè)狀態(tài)轉(zhuǎn)移方程：
（1）“動(dòng)態(tài)規(guī)劃”事實(shí)上是在填一張二維表格耻讽，i 和 j 的關(guān)系是 i <= j ，因此帕棉，只需要填這張表的上半部分齐饮；
（2）看到 dp[i + 1][j - 1] 就得考慮邊界情況。
邊界條件是：表達(dá)式 [i + 1, j - 1] 不構(gòu)成區(qū)間笤昨，即長(zhǎng)度嚴(yán)格小于 2祖驱，即 j - 1 - (i + 1) + 1 < 2 ，整理得 j - i < 3瞒窒。
這個(gè)結(jié)論很顯然：當(dāng)子串 s[i, j] 的長(zhǎng)度等于 2 或者等于 3 的時(shí)候捺僻，我其實(shí)只需要判斷一下頭尾兩個(gè)字符是否相等就可以直接下結(jié)論了。
如果子串 s[i + 1, j - 1] 只有 1 個(gè)字符崇裁，即去掉兩頭匕坯，剩下中間部分只有 11 個(gè)字符，當(dāng)然是回文拔稳；
如果子串 s[i + 1, j - 1] 為空串葛峻，那么子串 s[i, j] 一定是回文子串。
因此巴比，在 s[i] == s[j] 成立和 j - i < 3 的前提下术奖，直接可以下結(jié)論，dp[i][j] = true轻绞，否則才執(zhí)行狀態(tài)轉(zhuǎn)移采记。
（這一段看暈的朋友，直接看代碼吧政勃。我寫暈了唧龄，車轱轆話來回說。）
第 3 步：考慮初始化
初始化的時(shí)候奸远，單個(gè)字符一定是回文串既棺，因此把對(duì)角線先初始化為 1讽挟，即 dp[i][i] = 1 。
事實(shí)上丸冕，初始化的部分都可以省去耽梅。因?yàn)橹挥幸粋€(gè)字符的時(shí)候一定是回文，dp[i][i] 根本不會(huì)被其它狀態(tài)值所參考晨仑。
第 4 步：考慮輸出
只要一得到 dp[i][j] = true褐墅，就記錄子串的長(zhǎng)度和起始位置，沒有必要截取洪己，因?yàn)榻厝∽址惨男阅芡椎剩涗洿藭r(shí)的回文子串的“起始位置”和“回文長(zhǎng)度”即可。
第 5 步：考慮狀態(tài)是否可以壓縮
因?yàn)樵谔畋淼倪^程中答捕，只參考了左下方的數(shù)值逝钥。事實(shí)上可以壓縮，但會(huì)增加一些判斷語(yǔ)句拱镐，增加代碼編寫和理解的難度艘款，丟失可讀性。在這里不做狀態(tài)壓縮沃琅。
下面是編碼的時(shí)候要注意的事項(xiàng)：總是先得到小子串的回文判定哗咆，然后大子串才能參考小子串的判斷結(jié)果。
思路是：
1益眉、在子串右邊界 j 逐漸擴(kuò)大的過程中晌柬，枚舉左邊界可能出現(xiàn)的位置；
2郭脂、左邊界枚舉的時(shí)候可以從小到大年碘，也可以從大到小。