題目
思路：

1. 可以找到最小可重複動作嗎？
   • 題目的 method 要傳入 first node, 回傳它的 clone
   • 最小可重複動作可設定為：給定一個 node, 回傳 its clone
2. DFS: 先寫 recursive case
3. Base case: method 收到已 clone 過的 node
   • Use a dict to record nodes been cloned.
4. 須注意傳入 cloneGraph 的 node 有可能是 None

題目
思路：

• 要找的點是可到達的點的距離在 threshold 裡的那些點，所以要找的是最短距離，因為只要最短距離可以在 threshold 內，那它就是可到達的點
• 用 Floyd-Warshall’s algorithm 找到所有點之間的最小距離
  • k 是 i 到 j 之間的任意點。比較 i -> j 經過所有 k 的距離，最小的即為 i -> j 的最短距離。
  • Question:
    if the path is i -> 2 -> 1 -> j and the iteration consider k == 1 first. But the dist[i][1] not yet populated and still have value of float('inf'). It will have the actual value until k == 2.

題目
最直覺的作法就是先排序，取出最重的兩個撞擊後，把剩下的放回去，然後重複以上步驟：

1
2
3
4
5
6
7
8

def lastStoneWeight(self, stones: List[int]) -> int:
    while len(stones) > 1:
        stones.sort()
        s1 = stones.pop()
        s2 = stones.pop()
        if s1 != s2:
            stones.append(s1 - s2)
    return stones[0] if stones else 0

但這樣的時間複雜度為 O(n^2 * log n)，太大了，有沒有其他方法？

題目
這邊記錄自己答案的演變和檢討，有需要的也可以直接跳到最後的 O(1) space complexity 解答

一開始的思路：用遞增的 index 同時 go through 這兩個字串，按照裡面的 backspace hint build 出兩個新的字串再來看看是否相等

題目
思路：怎麼判斷兩個字串是不是 anagram?

• 可以把兩個字串都做排序，再看看是否相等，但這樣每次都要多花 O(n) 時間
• 可以計算每個字母出現的頻率，再看看兩個字串的計算結果是否相等。雖然單獨算也是要 O(n)，但假如搭配 sliding window 移動的時候一個個字母加入計算，就不會有額外的時間複雜度

題目
紀錄一下一開始的思路，檢討錯誤，再整理最後的答案。一開始的想法：

1. 這應該可以分解成最小可重複動作，用遞迴解看看
2. 覺得可以用原本的 method 當遞迴函式，把 image, color 照樣傳入，sr, sc 為該點的座標
3. 最小可重複動作：從當下這點擴散到周圍四個點

題目
思路

1. 樹的問題會先從遞迴來想比較直觀，首先找出最小可重複動作來作為 recursive case
2. 先假設我們可以用題目給的 method 直接當作遞迴的函式，也就是說我們遞迴函式的回傳，是 preorder 排序的 node values
3. 最小可重複動作：對於我這個 node 來說，回傳 preordered values

1
2
3
4
5
6
7

def preorder(self, root: 'Node') -> List[int]:
    if not root:
        return []
    result = [root.val]
    for child in root.children or []:
        result.extend(self.preorder(child))
    return result

題目
思路

1. 怎麼判斷一個 string 是否為 palindrome？
   • (x) 做一個倒過來的 string 看看兩個是否相等
     • 需要 O(n) 時間複雜度，太長了，因為你必須對所有的字串組合做測試
   • (o) Palindrome 一定是由偶數個數的字母組成，頂多再加上一組奇數個數的字母
2. 先用 dict 記錄每個 character 的個數，再利用計算完成的 dict 來算出答案

題目
思路

1. 最直覺的想法是從頭開始 traverse array，針對每一個 price 都去算一次那個位置之後的所有可能利潤，不過這樣會是兩個巢狀 for-loop，時間複雜度是 O(n^2)，太大了
2. 有沒有辦法只 traverse 一次 array 就好？
3. 利潤是由買價和賣價得出，知道最低買價和最高賣價就可以得出答案。有辦法設定這兩個變數，然後隨著 array traversal 不斷更新嗎？

題目
思路：最直覺的作法就是從頭開始沿著 next 一直走，然後用一個 set 來存放走過的 node，如果再次走到已走過的 node 就是 cycle 起點