簡介
這是分散式系統中很常用到的技巧，譬如你有個 redis cluster for caching, 就可以用 consistent hashing 來決定資料要放到哪個 redis instance, 優點是當增加或減少 redis node 時，可以最大化的減少資料的搬移
133. Clone Graph
題目
思路：
- 可以找到最小可重複動作嗎？
- 題目的 method 要傳入 first node, 回傳它的 clone
- 最小可重複動作可設定為：給定一個 node, 回傳 its clone
- DFS: 先寫 recursive case
- Base case: method 收到已 clone 過的 node
- Use a dict to record nodes been cloned.
- 須注意傳入 cloneGraph 的 node 有可能是 None
438. Find All Anagrams in a String
題目
思路：怎麼判斷兩個字串是不是 anagram?
- 可以把兩個字串都做排序，再看看是否相等，但這樣每次都要多花 O(n) 時間
- 可以計算每個字母出現的頻率，再看看兩個字串的計算結果是否相等。雖然單獨算也是要 O(n)，但假如搭配 sliding window 移動的時候一個個字母加入計算，就不會有額外的時間複雜度
409. Longest Palindrome
題目
思路
- 怎麼判斷一個 string 是否為 palindrome？
- (x) 做一個倒過來的 string 看看兩個是否相等
- 需要 O(n) 時間複雜度，太長了，因為你必須對所有的字串組合做測試
- (o) Palindrome 一定是由偶數個數的字母組成，頂多再加上一組奇數個數的字母
- (x) 做一個倒過來的 string 看看兩個是否相等
- 先用 dict 記錄每個 character 的個數，再利用計算完成的 dict 來算出答案
142. Linked List Cycle II
題目
思路：最直覺的作法就是從頭開始沿著 next 一直走，然後用一個 set 來存放走過的 node，如果再次走到已走過的 node 就是 cycle 起點
Isomorphic Strings
題目
這題看似不難，但第一次的做法錯了，第一次的程式碼如下，想法是用 mapping 組一個新字串 t2，假如跟 t 相同就 return True
Python 3 wrong solution:
1 | def isIsomorphic(self, s: str, t: str) -> bool: |