4. Median of Two Sorted Arrays

• 題目思維
  • 要O(log(m+n))
  • 看到log，聯想到binary search
• Tricks
  • 一定要先設想case
  • nums1, nums2 = nums2, nums1 if len(nums1)>len(nums2)
  • 檢查while的條件 用還是and or
    • 1<i<m
    • 才不會nums1[i-1]時出問題
  • 由小至大注意l, r的更新，mid可能會有永遠到不了的地方
    • m從2開始慢慢增加
      • i的移動範圍是0~m，看往左往右到不到的了每個地方
      • 檢查到m=4其實就可以了，因為往後面檢查時基本上都會重複到m=2~4的子過程
    • 往左則r=i
    • 往右則l=i+1
  • 注意奇數偶數的處理
• edge case
  1. 偶數
     • m=0
     • m=1
       • n=1
       • else
     • m<n
       • i==0
       • i==m
       • else
     • m==n
       • i==0
       • i==m
       • else
  2. 奇數
     • m=0
     • m=1
     • m<n
       • i==0
       • i==m
       • else
  3. 兩個array同長的處理
     • 同長的時候若l,r 設計不好則mid = (l+r)//2會陷入無限迴圈
• 解法2 get_kth
  • 遞迴解
  • 奇數就return get_kth(k)
  • 偶數就return (get_kth(k) + get_kth(k-1))/2
  • 然後定義好get_kth
    • 令ia, ib是A, B的中間那個數(等於每次都從中間切分，就可以完成時間log的要求)
    • 從最小的組合開始測試跟猜想，因為大的組合減到後面等於小的
      • 所以從base case len(A)=0開始len(B)=1,2,3
      • 然後再從len(A)=1開始len(B)=1,2,3
      • 不用倒過來因為AB其實是相對的
    • 核心思想
      • 當k比ia+ib小的時候，代表kth主要在整體的左邊比較小的部分
        • 如果A[ia]>B[ib]，則A在ia右邊的元素都是太大的都可以刪掉，然後要尋找第k個不變
        • A[ia]<B[ib]跟上面只是相反而已，概念一模一樣
      • 當k≥ia+ib，代表kth主要在整體的右邊比較大的部分
        • 如果A[ia]>B[ib]，則B在ib左邊的元素（包含）都太小都可以刪掉，然後要尋找第k-ib-1個
      • 注意k與ia ib關係哪個要加等號，如果試到後來發現會一直卡在迴圈裡繞不出去，那就要改
        • k<ia+ib, k≥ia+ib會卡住
          • 增添base case len(A)==len(B)==1會出現recursion error

10.Regular Expression Matching

• DP解O(m*n)

  • dp[0][0]代表空字串的比對 =True
  • dp[i][j]代表累積至p第j個字母與s第i個字母的比對情況
    • 長的s與p是由短的結果累積起來的，把過程中短的都視為獨立的字串
      • eg, mississipi vs misspi, 過程中有m vs m, mis vs mis*s ....

• Trick

  • 用他給case去找條件狀況

  • 沒有的話就自己設定條件

  • 條件的寫法會影響解答的時空間效率

    elif chp=='*' and dp[i+1][j-1]:                    
                        dp[i+1][j+1] = True
    #會比下面快
    elif chp=='*':                    
                        dp[i+1][j+1] = dp[i+1][j-1]
    

• edge case

  • .* 遇到這個就會有不知道要比對多少數量的問題

32. Longest Valid Parentheses

• DP + stack
  • 如何設定dp的定義
  • 如何記憶(加上歷史資訊)很重要
  • stack 存放 left_(_index, 就可以計算距離
    • 用現在的index - stack中的left_(_index + 1 就可以獲得目前最長字串
• Edge Case
  • ()(()

41. First Missing Positive

• 換個角度想
  • answer range只會落在1~size+1之間
  • 把1~size的值換到對應的位置上
    • 1換到第一個nums[0], 2換到第二個nums[1] ...
    • 如果nums[i] ≠ i+1 那就是answer
• Trick
  • 先sort nums
  • 注意nums-1的邊界
  • nums[i], nums[num-1] = nums[nums-1], nums[i]
  • 最後如果都沒有要記得return size+1
• edge case
  • [2]只有一個元素沒得換的時候

76. Minimum Window Substring

• sliding window/ 2ptr /slow, fast
  • 用hashmap/ dict儲存指定目標
    • 目標的字母、計數
    • 另外用一個變數計算還有幾個字母未達成，搭配missing -= need[ch] > 0 即可計算
  • fast先向右獲得第一個valid window
    • while condition ⇒ slow向左獲得最小的window
    • 更新condition
  • 反覆上一步
• Trick

  • 用counter儲存dict

  • ans_l, ans_r 起始值設為0（遇到invalid input就會直接回傳""）

    • 所以在後來須加條件 if ans_r == 0 or r - l > ans_r - ans_l:

  • need[] 針對每一個字母都減

  • 但missing -= need[ch] > 0，只有當need[ch] > 0 時才去減missing，也就是只有當遇到指定字母才減去missing

  • 注意順序，反了就錯了

    missing -= need[ch] > 0
    need[ch] -= 1
    ...
    need[s[i]] += 1
    i += 1
    

  • 出去while以後還要更新一次need[], missing 和 l

85. Maximal Rectangle

• Brute Force O((N*M)^3)
  • for loop i, j 當左上角定位點
    • for loop p, q 當右下角定位點
      • for loop x, y 檢查i-p, j-q 中間的矩形有沒有都是1