譬如有兩個 list a 和 b，使用 a.extend(b) 和 a += b 有什麼相同或不同？有沒有什麼 general 的 best practice for using one rather than the other?

其實在這個情境下，這兩個用法幾乎一樣。它們都會直接 in-place 的修改 a，把 b 裡面的元素加到 a 的後面

• += 會呼叫 list 的 .__iadd__() 來做 in-place 的修改
  • 所以在這個情境下，b 可以是任何 iterable，譬如 [] += {} 會得到 []
  • 假如用 += 的是 immutable 的 type，Python 發現沒有 .__iadd__()，接著就會呼叫它的 .__add__()，此情況下 a += b 等同於 a = a + b

以下列出少數有差別的地方：

題目
思路

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 不斷更新嗎？

通常都會說 Python 的 set 內部是用 hash table 來實作，所以是 O(1)，但為什麼這樣就是 O(1)？

當要判斷某個元素是否在 set 裡面時，它的 __hash__() 會被用來得到 hash 值，可以把這個 hash 值視為 set 底層實作的 array 的 index，Python 接著會用這個 hash 值去那個 array 的對應位置找，然後發現 array 沒有這個位置，或是找到對應 value，而這個過程跟 set 裡的元素個數無關，所以是 O(1)

而這邊說的 O(1) 是平均時間複雜度，最壞情況時間複雜度是 O(n)，

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

題目
思路

1. 因為是 linked list，我們可以使用 curr 當指標，沿著 linked list 的頭往後走，一邊改變 curr.next 的指向，而過程中必須對前一個和下一個都有所掌握，因為 curr 必須指向前一個，然後它本身必須換到下一個
2. 所以我們會有三個變數：previous, curr, next
3. 當 curr 是 head 時，previous 會是 None，這兩個可以先設定好。目標是一直改變 curr 的指向，讓 curr 一直走到 linked list 盡頭，變成 None 為止，所以 while 條件就是 當有 curr 的時候就做

題目
這題看似不難，但第一次的做法錯了，第一次的程式碼如下，想法是用 mapping 組一個新字串 t2，假如跟 t 相同就 return True

Python 3 wrong solution:

1
2
3
4
5
6
7
8

def isIsomorphic(self, s: str, t: str) -> bool:
    d = {}
    for i in range(len(s)):
        d[s[i]] = t[i]
    t2 = ''
    for c in s:
        t2 += d[c]
    return t == t2

題目

1. 先想到的是有沒有辦法透過 bitwise operation 來判斷，發現無法
2. 看相鄰位置有沒有一樣的，最直覺就是用字串來判斷 => 可以利用 Python 的 built-in function bin 來把數字轉為 binary 字串

Python3 solution:

1
2
3
4
5
6

def hasAlternatingBits(self, n: int) -> bool:
    b_str = bin(n)[2:]  # 去掉前面的 '0b'
    for i in range(len(b_str) - 1):
        if b_str[i] == b_str[i + 1]:
            return False
    return True

題目

1. 因為只能用常數的額外空間，且 array 裡的數字除了目標之外都會有兩個，所以朝 bitwise operation 的方向想
2. 把 array 裡所有數字接連做 bitwise operation，假如有兩個一樣的數字，他們就會抵銷變為 0，即使不是連著做也一樣，所以最後的結果就是那個落單的數字
   • 可以想像所有數字都用二進位表示由上而下列在一起做計算，不管他們位置怎麼換結果都會一樣 (偶數個 1 會互相抵銷)

Python3 solution:

1
2
3
4
5

def singleNumber(self, nums: List[int]) -> int:
    r = 0
    for i in nums:
        r ^= i
    return r

題目
思路

1. 樹的問題用遞迴來解相對上比較直覺，所以先試試遞迴解
2. 拆解到最小單位來找 recursive case: 隨機取樹中一個點，判斷它是否 valid
3. 大部分情況都會有上下限。以左邊的點為例，上限就是父節點的值，下限就是它所在的右子樹的父節點的值，所以這個值必須由上到下一層層傳遞下來。反之，右邊的點的話，就變成上限必須一層層傳遞下來
4. 因為上下限必須用傳遞的，所以寫一個 function node_valid 接受上下限的參數