# 2020q3 Homework4 (quiz4)
contributed by < `fwfly` >

## 測驗 1
這個題目主要是在找兩組 bits 的差異．
透過題目給的範例知道，bit 如果不同輸出的 bit 為 1 相同則為 0
透過 xor 可以得到這樣的結果

1   (0  0  0  1)
4   (0  1  0  0)
       [ ]   [ ]
        |     |
        \_ 2 _/

所以答案是

int hammingDistance(int x, int y) {
    return __builtin_popcount(x ^ y);
}

### 延伸問題

## 測驗 2
:::warning
以下全部都是錯誤的推論跟假設，在實際測 leetcode 的時候才發現樹可以長成任意樣子，並不會像圖片一樣單純的做二元樹
解答部分可以跳到

https://hackmd.io/@fwfly/quiz4#%E6%AD%A3%E8%A7%A3
:::

### 理解
給一顆樹，找到 node 的第 k 個祖先的節點，回傳節點值，否則回傳 -1
AAA : 資料結構長什麼樣子？
BBB : 樹要怎麼長 ?
CCC : 怎麼比對 k 值

#### 限制:
需使用陣列方式處理

#### 觀察樹
這棵樹是有順序的，而且值是固定的( 由上到下 由左到右 1...n 長出 )．因此不用考慮值的問題．

樹的階層透過觀察可以看到，每個節點只有兩個分枝．
所以會有以下關係

          每層節點數
level 0  =   1     000001  # 第0層只有一個節點
level 1  =   2     000010  # 從 root 長出兩個分枝
level 2  =   4     000100  # 從第一層的兩個點在各長出兩個分枝
level 3  =   8     001000  # 從第二層得 4 個節點在各長出兩個分枝
level 4  =   16    010000  # ...以此類推
level 5  =   32    100000

所以如果用一個 int 的 bits (32 bits int) 來表示，樹可以長到 31層 (減掉 root )
(int 根據 compiler 不同可能會有不同的 size 長度)

#### 怎麼用矩陣表示一棵樹？
從上面的觀察可以知道
1. 每個節點都只有兩個分枝
2. 順序是由左到右
3. 值是固定不變

因為值固定不變且有順序，所以可以直接用矩陣本身的 index 表示
然後 idx 指到的值可以存 parent 的數值

比方說這樣

node = 7  [-1, 0, 0, 1, 1, 2, 2]

index 0 = -1 因為是 root 這沒問題
index 1, 2 這是從 root 長出來的分支所以 parent 為 0
index 3, 4 這是從 node 1 長出來的分支所以 parent 為 1
index 5, 6 這是從 node 2 長出來的分支所以 parent 為 2

也因為每次分支都是兩個而且有順序，所以如果繼續延伸下去就會是

[-1, 0, 0, 1, 1, 2, 2, 3, 3]
[-1, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4]
[-1, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
....etc

將每一組相同數字拆開來就可以這樣看

[3,    3]  # 可以看成是 node 3 的兩個分支
 i7    i8  # node 3 的 child 就會是 7 跟 8

這樣做的方式可以用查表的方法很快找出 parent 是誰
比方說已經建好一個 array 叫 array_tree
要找 node 12 的 parent 就可以直接使用像這樣

    int array_tree[] = {-1, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5};
    int parent = array_tree[12]; // parent = 5  

###  AAA 跟 BBB
從迴圈的部分可以看出，資料結構不是用 linked list 長成樹狀．
而是利用查表格的方式來達到快速查表

    int max_level = 32 - __builtin_clz(n) + 1;
    for (int i = 0; i < n; i++) {
        obj->parent[i] = malloc(max_level * sizeof(int));
        for (int j = 0; j < max_level; j++)
            obj->parent[i][j] = -1;

### AAA
這個表格是個二維陣列，所以 AAA 會是指向整數的指標的指標(int **)
用`指向整數的指標` 去建立 array 存 level
用 `指向整數的指標的指標` 來存跟 parent 相關的 index .
以題目來說會是有 3 層 7 個 node, 所以會建立說這樣的結果

-1, -1, -1,
0, -1, -1,
0, -1, -1,
1, 0, -1,
1, 0, -1,
2, 0, -1,
2, 0, -1,

橫向是 level 縱向是跟 parent 相關的 index
### 怎麼設定 parent ? (BBB)
這邊的理解是直接從答案回推．

parent[i][j] 可以看成是在問`第 i 個 node 的第 j 層的 parent 是誰？`

obj->parent[i][j] = obj->parent[i][j -1] == -1? -1 : obj->parent[obj->parent[i][j - 1]][j - 1];

這行程式碼主要的意思是如果`上一層 (j-1) 的 parent`不是 -1( -1 表示 root )，就直接從表中紀錄 parent 的 index．

### 正解
先理解題目

[7,[-1,0,0,1,1,2,2]

後面的 array 分別表示每個節點的 parent 是誰

[-1,0,0,1,1,2,2]

index  parent  
  0      -1  # 因為是 root
  1       0  # 表示是 root 的分支
  2       0  
  3       1
  4       1
  5       2
  6       2

所以長出來就會如題目那樣
但是在跑題目時可能會遇到以下狀況

[-1,0,0,1,2,0,1,3,6,1] # root  有3個分支
[-1,0,1,2,3,4,5,6,7,8,9] # 長成一條線

### 直接建立整張表格
參考至這篇解說
https://leetcode.com/problems/kth-ancestor-of-a-tree-node/discuss/686268/Explanation-with-c%2B%2B-sample-code

如果不知道怎麼解決，先用暴力解，再來做修正
所以如果有 10 個點，要找出來第 k 個祖先，可以直接建立 10*10 的表
來做查表
比方說

[-1,0,0,1,2,0,1,3,6,1]

-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
0, -1, -1, -1, -1, -1, -1, -1, -1, -1,
0, -1, -1, -1, -1, -1, -1, -1, -1, -1,
1, 0, -1, -1, -1, -1, -1, -1, -1, -1,
2, 0, -1, -1, -1, -1, -1, -1, -1, -1,
0, -1, -1, -1, -1, -1, -1, -1, -1, -1,
1, 0, -1, -1, -1, -1, -1, -1, -1, -1,
3, 1, 0, -1, -1, -1, -1, -1, -1, -1,
6, 1, 0, -1, -1, -1, -1, -1, -1, -1,
1, 0, -1, -1, -1, -1, -1, -1, -1, -1,

當然這樣子 leetcode 是不會通過的，雖然速度可以達到 O(1)
但是空間卻是佔用了 n^2 ，而且從上面可以看到其實除了一直線以外，大部分的空間都是存 -1

### 解決空間問題
解說上提供一個想法：
任何一個第 k 個 parent 都可以用 [2^i]th parent 去表示
第 1 個 parent, 則會是 第 2^0 parent
第 3 個 parent, 則會是 第 2^1 個 parent 的第一個 parent
第 4 個 parent, 則會是 第 2^2 個 parent
...
第 9 個 parent, 則會是 第 2^3 個 parent 的第一個 parent
.....以此類推

換句話說表格不再記錄每個 parent, 而是紀錄第 1,2,4,8,16....etc
個 parent
然後節點數最多只有 5 * 10^4 , 2^16 > 5 * 10^4
換句話說這個 array 最多只會需要 n*16 的大小，而且後面的數字可以依照 n 的大小去做改變

### AAA
AAA 還是需要用一個二維陣列去儲存，所以 AAA 就會是 **parent

### BBB
在找出 [i][j] 個 parent 時，要先確認 [i][j-1] 是否為 -1
由於第 2^(j-1) 個 parent 已經是 -1 (root) ，所以第 2^j 的 parent 理所當然也就是 -1．
因此這邊是判斷之前的 parent 是不是 root

### CCC
這邊可以把 k 用 bitwise 的方式來看
把前面所說的 [2^i]th parent 跟 bitwise 放在一起看就會得到下面的式子

3 = 0011 -> 2^1 + 1
4 = 0100 -> 2^2 
5 = 0101 -> 2^2 + 1
6 = 0110 -> 2^2 + 2^1
...
9 = 1001 -> 2^3 + 1
...

從上面可以看得出來只要 bit 為 1 就需要去找出 parent 的數字
所以這時候 i 就會變成 mask 用 & 的方式來判斷 k 的第 i 個 bit 是否為 1 .
如果是則 node = node 的第 2^i 個 parent
重複以上動作直到 i 跑完 max_level, 就可以找到第 k 個 parent