task01,lc:2,4,5

2.兩數相加

思路：比較簡單的一般題，與字串相同的模擬加法即可，

具體代碼如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 類似這樣的需要生成新的listnode的題目使用啞結點會方便處理一些，
        # 就是在前面多加一個任意結點，最后回傳.next就可以
        # 其實ans和head可以理解為指向同一個鏈表的指標，所以針對head的改動也可以體現在ans上
        # ans用來輸出最后的listnode，head用來處理遍歷生成新的listnode
        ans = head = ListNode(0)
        digit = 0                              # 標記進位情況

        # 當l1與l2沒有遍歷完的時候，依次遍歷相加，并將和加入到結果中
        while l1 and l2:
            num = l1.val + l2.val + digit       # 計算l1和l2在該位數上的和
            head.next = ListNode(num % 10)      # 將兩者的和取個位數添加到結果head和ans中
            digit = num // 10                   # 標記進位情況，有進位則為1，無進位為0
            head, l1, l2 = head.next, l1.next, l2.next  # 所有鏈表后移達到遍歷效果


        # 當l1較長時執行該回圈
        while l1:
            num = l1.val + digit
            head.next = ListNode(num % 10)
            digit = num // 10
            head, l1 = head.next, l1.next

        # 當l2較長時執行該回圈
        while l2:
            num = l2.val + digit
            head.next = ListNode(num % 10)
            digit = num // 10
            head, l2 = head.next, l2.next
        # l1和l2均遍歷完畢，查看最高位是否還有進位，若有則加入
        if digit:
            head.next = ListNode(digit)
        
        # 回傳啞結點的next
        return ans.nex

時間復雜度O(max(m,n))，空間復雜度O(1)，

4.尋找兩個正序陣列的中位數

二分法中比較難的題目了，難點在二分中分界線的劃分和左右邊界的處理，
思路：需要在兩個陣列中找出兩個分界線，分界線左側的數字總和為(m+n) // 2（偶數時）或者(m+n)//2 +1(奇數時），兩者統一起來就是(m+n+1)//2.最終目的是找到使得兩個分界線左側的數字均小于右側的數字（如果有的話），詳細邊界見具體代碼：

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # 讓前者為短的，保證二分中的mid和mid-1不越界，（
        # 如果這里不作處理的話，二分那里就要分情況討論邊界）
        if len(nums1) > len(nums2):         
            nums1, nums2 = nums2, nums1
        n1, n2 = len(nums1), len(nums2)

        # +1是為了處理兩陣列長度之和奇偶不同的情況,half表示中位數左側的數字個數
        half = (n1 + n2 + 1) // 2

        """這里二分需要特殊理解一下，因為分界線是一個虛的（并不存在的界限，
        所以需要用真實的index表示）,mid代表界限的右側坐標，mid-1代表界限坐標的數字，
        因此right的初值也不一樣了，為n1而非n1-1，
        """
        left, right = 0, n1
        while left < right :
            mid1 = left + ((right - left) >> 1)
            mid2 = half - mid1
            if nums1[mid1] < nums2[mid2 - 1]:  # nums1右側小于nums2左側，所以mid要右移
                left = mid1 + 1
            else:
                right = mid1
        # mid1和mid2分別表示兩陣列中分界線右側的元素坐標
        mid1 = left
        mid2 = half - mid1 

        # 總個數為奇數的中位數，等于左側數字的max
        # 總個數為偶數的中位數，等于左側的max和右側min的均值
        # 這句正則運算式看不太懂的話看下面注釋掉的代碼，兩者等價
        max_left = max(nums1[mid1-1] if mid1 > 0 else float("-inf"), nums2[mid2-1] if mid2 > 0 else float("-inf") )

        # if mid1 > 0:
        #     left1 = nums1[mid1 - 1]
        # else:
        #     left1 = float('-inf')
        # if mid2 > 0:
        #     left2 = nums2[mid2 - 1]
        # else:
        #     left2 = float('-inf')
        # max_left = max(left1, left2)

        if (n1 + n2) % 2 == 1:
            return max_left
        min_right = min(nums1[mid1] if mid1 < n1 else float("inf"), nums2[mid2] if mid2 < n2 else float("inf"))
        return (max_left + min_right) / 2

時間復雜度O(log(m+n)),空間復雜度O(1)，

5.最長回文子串

主要是最開始可能不太了解中心拓展法這個方法，了解了后就非常簡單了，
其實本題最優解并非該方法，而是Manacher 演算法（但是非常復雜一般不要求掌握），
具體代碼如下:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expendFromCenter(index1, index2):
            # index1，index2分別表示左右兩個指標，
            while index1 >= 0 and index2 < n and s[index1] == s[index2]:
                index1 -=1
                index2 += 1
            return index1 + 1, index2 - 1

        n = len(s)
        start, end = 0, 0
        for i in range(1, n):
            left1, right1 = expendFromCenter(i, i)      # 長度為奇數的情況
            left2, right2 = expendFromCenter(i - 1, i)  # 長度為偶數的情況

            # 如果長度為奇數時更長，更新
            if right1 - left1 > end - start:
                start, end = left1, right1
            
            # 如果長度為偶數時更長，更新
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]

時間復雜度O(n2),空間復雜度O(1)，

解法一:dp解法
官方解法超時：下面給出我的解法

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]      # 初始化dp陣列
        max_len = -1
        ans = ''
        for i in range(n - 1, -1, -1):            # i逆向遍歷，因為計算i時的dp需要用到i+1的狀態
            dp[i][i] = True
            for j in range(i + 1, n):             # j正向遍歷
                if j - i == 1:                    # 長度為2時判斷是否為
                    dp[i][j] = s[i] == s[j]

                elif j - i > 1 and s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1]

                if dp[i][j] and j - i > max_len:   # 記錄此時的最長子串
                    max_len = j - i
                    ans = s[i: j + 1]
        if len(s) > 0 and not ans:                 # 特殊處理一下最長子串為1的情況，因為j是從i+1開始遍歷的    
            ans = s[0]
        return ans