Q1 兩數之和 Two Sum

給定一個整數陣列 nums 和一個整數目標值 target，請你在該陣列中找出 和為目標值 的那 兩個 整數，并回傳它們的陣列下標，
你可以假設每種輸入只會對應一個答案，但是，陣列中同一個元素不能使用兩遍，
你可以按任意順序回傳答案，

我一開始的解答用了雙回圈，時間復雜度為O(n2)，成功通過

def twoSum(nums,target):
    sol=[]
    if len(nums)<2:
        return sol
    for i in range(len(nums)):
        for j in range(i+1,len(nums)):
            if nums[i]+nums[j]==target:
                sol.append([i,j])
    return sol

之后看了別人的答案，他們用到了字典的方式，達到了O(n)的時間復雜度，dic[nums[i]]=i 這個不能寫在下面的if條件之上，原因是每一次遍歷不能因為target-nums[i]等于nums[i]而出現下標與自身相同的情況

def twoSum(nums,target):
	dic={}
    for i in range(len(nums)):
    
        #dic[nums[i]]=i 		# 這個不能寫在下面的if條件之上，原因是每一次遍歷不能因為
        						# target-nums[i]=nums[i]而出現下標與自身相同的情況
        				
        if target-nums[i] in dic:
            return [dic[target-nums[i]],i]
        dic[nums[i]]=i 			# 寫在if下面才是對的

在之后自己的改程序序中，我給if陳述句加了一個判斷，反而提高了運行的速率：

def twoSum(nums,target):
	dic={}
    for i in range(len(nums)):
            
	if target-nums[i] in dic and dic[target-nums[i]]!=i: 
		return [dic[target-nums[i]],i]
	dic[nums[i]]=i

Q2 兩數相加 Add Two Numbers（鏈表）

給你兩個 非空 的鏈表，表示兩個非負的整數，它們每位數字都是按照 逆序 的方式存盤的，并且每個節點只能存盤 一位 數字，
請你將兩個數相加，并以相同形式回傳一個表示和的鏈表，
你可以假設除了數字 0 之外，這兩個數都不會以 0 開頭，

這個是我的錯誤答案，在最后的判斷中，應該是判斷當前的l1與l2是否為空值，因為就算next值為空，也可以指向next節點，同時在宣告鏈表以后還需要宣告一個指代這個鏈表的節點，我理解為c語言中的head

# 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:
        c=0
        l=ListNode(0)
        l3=l 					# 很關鍵，宣告鏈表以后還需要再宣告一個指代這個鏈表頭的節點
        while l1 or l2:

            a=l1.val if l1 else 0
            b=l2.val if l2 else 0

            val = a + b + c
            
            c=val//10

            l3.next=ListNode(val%10)
            l3=l3.next
            
            if l1.next: # 錯誤
                l1=l1.next
            if l2.next: # 錯誤
                l2=l2.next
        if c>1:
            l3.next=ListNode(1)
        
        return l.next

以下是需要修改的地方

            if l1: # 若當前值不為空，則去下一個節點
                l1=l1.next
            if l2:
                l2=l2.next

鏈表是個很基礎的題型，以下是自己學習歸納的需要注意的地方：
1）先宣告鏈表頭節點
2）宣告一個指標指向鏈表頭節點
3）通過指標在while回圈中每一次指向自己的next屬性，來實作鏈表的遍歷
4）當現在的指標不為空時，就可以指向下一個節點

Q3 無重復字符的最長子串 Length of longest substrings

給定一個字串，請你找出其中不含有重復字符的 最長子串 的長度，

這道題我曾經寫出來過，但是用的方法是耗時70多ms，我覺得并不是最優解，這次再看別人的答案，比我的厲害特別多，我的思路是從字串開頭進行遍歷，每次與之前的元素做對比，從而獲得最優解的陣列得出陣列長度，但是這種思路非常有局限性，實作起來也很繁瑣，如果字串稍微復雜一點便難以實作，

這位大神的答案十分的言簡意賅，他通過字典的方式存盤所有字符，直到找到下一個相同的字符，用最后字符的位置加1減去前一個字符的位置取得該不重復字符的長度（因為得包含相同字符中的一個所以要加1），但還是有些沒弄懂，得再吸收一下，

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        st = {}
        i, ans = 0, 0
        for j in range(len(s)):
            if s[j] in st:
                i = max(st[s[j]], i)
            ans = max(ans, j - i + 1)
            st[s[j]] = j + 1
        return ans;

Q4 尋找兩個正序陣列的中位數 Find Median Sorted Arrays

這道題如果想直接實作的話其實并不難，但作為一道Hard難度的題目，他將答案的時間復雜度限制在O(log(m+n))，

我之后再來填補這道題吧，現在確實看著有些繁瑣，

Q5 最長回文子串 Longest Palindrome

給你一個字串 s，找到 s 中最長的回文子串，

被整吐了，先是自己嘗試用暴力破解法失敗了，看了官方解釋的中心擴散法也失敗了，最后還是看著答案搞完的，自己歸納了幾個需要注意的點：

1. 我在這個方法中本來用了一個標志位judge來判斷長度的奇偶性從而進行分類討論，但是我對于回文序列的思路想錯了，不論是奇數字串還是偶數字串是都有可能有奇偶回文序列的，這個標志位應該是針對回文序列而不是針對原字串，這也導致了我的寫法無法得到正確的解
2. 其次，我的想法是將left和right變數變成與索引i相減和相加得到回文序列的起點和終點，雖然這樣可行，但是對于邊界的處理會很復雜，不如直接如答案中將left和right直接設定為起點和終點
3. 這個答案中的一個比較精妙的點是findCenter(s,left,right)這個函式的設計，因為并不知道這個字串中回文序列的奇偶性，當呼叫這個函式時，不僅可以讓奇偶同時被討論，而且對于答案互不影響，

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def findCenter(s,left,right):#放上面
            while left>=0 and right<len(s) and s[left]==s[right]:
                left-=1
                right+=1
            return left+1,right-1

        if len(s)<2:
            return s

        judge=0 if len(s)%2==0 else 1 #本來是用來判斷長度的奇偶性從而分類討論


        start,end=0,0
        maxLen=0
        lst=[]
        for i in range(len(s)):
            #if judge ==1:
            left1,right1= findCenter(s,i,i)
            if right1-left1>end-start:
                start,end=left1,right1
                # if right-left>maxLen:
                #     maxLen=right-left
                #     lst=[left,right]

            #else:
            left2,right2=findCenter(s,i,i+1)
            if right2-left2>end-start:
                start,end=left2,right2
                # if abs(right-left)>maxLen:
                #     maxLen=abs(right-left)
                #     lst=[left,right]


        sol=s[start:end+1]



        return sol

Q1-5 一些筆記

1. python中對串列進行賦值時，不能直接讓list1=list2，這只會讓他們地址相同而一起發生改變，要使用切片：list1[:]=list2[:]，
2. 串列的索引只能是整數，若在其中用到了除法運算式也需要是整除//，
3. 字串(Substring) 是原始字串的一個連續子集，
   子序列(Subsequence)是原始字串的一個子集，
4. 希望自己可以養成呼叫函式的習慣，事先將一些實作重復功能的函式單獨寫出來，可以使代碼易于修改并看上去更加美觀，之前在練習java的時候總是將不同功能分為不同的類，這種習慣反而在python中堅持的少了
5. 字典在python中用于查找串列與字串中的特定位置元素還是很好用的，多換換思維方式，不要總想著暴力地遍歷所有值，字典適用于單一的元素查找，適合找特定開頭和結尾的字串，如Q1和Q3，但如果是對于Q5這道回文序列就顯得不太實用了，