動機

寫給自己的leetcode筆記

搜尋與走訪

一個是找有沒有，一個是記下所有符合條件的東西

但本質都一樣，都要讓狀態變化，去看對不對，而走訪就是把資料拆分成一定單位

怎麼拆分就是依據需要的狀態(題目需求)與本身是什麼資料結構(List, Tree, Graph)

搜尋範圍

讓搜尋範圍合理的改變(把不需要的劃掉，或是保留可能性)

  • 太小變大
  • 太大變小
  • 用完後變小 並保持住需要的屬性(order, 大小, 回文, 題目定的規則)

拆分的方式

  • List
    • traversal
      • 頭到尾 (可以看成時間，見188)
        • greedy (看class schedule 3)
          • 選大 (結果最大)
          • 選小 (保留可能性)
            • 找出限制，以此sort，而這個限制就是構成搜尋範圍的要素
      • 從中點走(一半)
        • binary search
        • divide and conquer
          • 從中點往外擴
      • 兩邊左右走
        • two pointer
      • sublist & range
        • sliding window
        • prefix sum
      • 有序
        • sort
        • heap
    • 多list合一
      • trie
      • merge
      • pointer as each list
      • mutual recursion
        • 把DP想成一個list(或是說做完動作後的狀態)，之後開始merge
        • 188. Best Time to Buy and Sell Stock IV
  • tree
    • 根與子樹
      • DFS
        • 前中後序 (greedy)
          • threading
        • DP & 記憶法
          • DP想成stream
        • Binary search tree
          • 大小
          • 數字範圍
      • BFS
    • level by level
      • BFS
      • DFS with other pointer
    • 左到右、右到左
      • DFS
      • Line sweeping
  • graph
    • 起點終點
      • DFS
      • BFS
    • 外到內，內到外
      • BFS
  • math & bit operation
    • xor
    • even & odd
    • random
      • 平均的出現
    • bit 與 bit之間是獨立的，如果不是當成list用就是一起用bit operation
    • 為了保持條件操作，進而平攤操作
      • 1172. Dinner Plate Stacks
  • 綜合技
    • 用別的資料結構描述其他變數
      • class schedule 3
    • 把資料encode在同一個資料結構上以合併走訪
      • Sort Items by Groups Respecting Dependencies
      • Prefix and Suffix Search