---
tags: info2022-homework1
---
# 2022 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022)」作業 1
> 貢獻者：達摩 - Daruma
> [模擬面試錄影(漢)](https://youtu.be/OUIiq9H9kYI)
> [模擬面試錄影(英)](https://youtu.be/vtdFTbQCDmI)
## [509. Fibonacci Number](https://leetcode.com/problems/fibonacci-number/)
### 題目敘述
現在有一個費氏數列 $f$，定 $f_0 = 0$、$f_1 = 1$。
現在題目給一個非負整數 $n$，請算出 $f_n$ 的值。
### 程式碼解說
#### 使用 DP
用遞迴的方法來算答案的話重複的計算會算很多次，因此使用迭代的方式依序算出 $f_2$, $f_3$ 一直到算出 $f_n$ 來避免重複計算的問題。
```cpp!
int fib(int n) {
if (n <= 1)
return n;
vector<int> f(n + 1, 0);
f[1] = 1;
for (int i = 2; i <= n; ++i)
f[i] = f[i - 1] + f[i - 2];
return f[n];
}
```
#### 空間複雜度 $O(1)$
算 $f_i$ 的時候只需要知道 $f_{i - 1}, f_{i - 2}$，因此可以只用長度為 $3$ 的陣列來記錄。
```cpp!
int fib(int n) {
if (n <= 1)
return n;
array<int, 3> f{0, 0, 1};
for (int i = 2; i <= n; ++i) {
f[0] = f[1];
f[1] = f[2];
f[2] = f[0] + f[1];
}
return f[2];
}
```
#### 時間複雜度 $O(\log n)$
如果將 $f_i, f_{i + 1}$ 寫成 $\left[\begin{matrix}f_i \\ f_{i + 1}\end{matrix}\right]$，那要得到 $\left[\begin{matrix}f_{i + 1} \\ f_{i + 2}\end{matrix}\right]$ 的話，只需要乘上 $\left[ \begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right]$ 即可。
可以推得 $\left[ \begin{matrix} f_{n - 1} \\ f_n \end{matrix} \right] = \left[ \begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right]^n \left[ \begin{matrix} 1 \\ 0 \end{matrix} \right]$，而計算 $\left[ \begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right]^n$ 的時間複雜度是 $O(\log n)$。
### Follow Up: [收納的智慧](https://judge.csie.ncku.edu.tw/problems/129)
給定一個 $2 \times n$ 的收納盒，而你現在手邊有許多積木，積木的形狀都是長方形，並且有 $1 \times 2$ 和 $1 \times 1$ 兩種大小，請問要用積木把收納盒放滿有幾種可能的放法。
#### 使用 DP
定義 $dp_{i, 0}$ 為填滿 $2 \times i$ 的盒子的方法數，而 $dp_{i, 1}$ 為填滿 $2 \times (i - 1)$，並且第 $i$ 行「只」填其中一格的方法數。
要填滿第 $i$ 行有四種方法：
1. 使用一個 $2 \times 1$ 的積木
2. 使用兩個 $1 \times 1$ 的積木
3. 使用兩個 $1 \times 2$ 的積木
4. $1 \times 2$ 和 $1 \times 1$ 的積木各一個
從上面三種方法可以得知 $dp_{i, 0} = dp_{i - 1, 0} + dp_{i - 1, 0} + dp_{i - 2, 0} + 2 dp_{i - 1, 1}$。
而第 $i$ 行只填一格的方法則是用 $1 \times 1$ 或是 $1 \times 2$ 的積木，因此 $dp_{i, 1} = dp_{i - 1, 0} + dp_{i - 1, 1}$。
---
## [Circular Permutation in Binary Representation](https://leetcode.com/problems/circular-permutation-in-binary-representation/)
### 題目敘述
題目給兩個非負整數 $n$ 和 $start$，其中 $n$ 代表現在有個長度為 $2^n$ 的陣列 $[0, 1, 2, \dots, 2^n - 1]$。
請你重新排列此陣列，使得陣列的第一項為 $start$ 並且所有相鄰的數字在二進位表示中剛好只有一個位元不同。
注意第一項以及最後一項同樣視為相鄰。
### 程式碼解說
#### 方法一：先找出第一項為 $0$ 的解
先找出第一項為 $0$ 的解 $arr$ 之後，假設 $start$ 在 $arr$ 中的索引值為 $i$（索引值從 $0$ 開始），則把 $arr$ 的 $[i, 2^n)$ 以及 $[0, i)$ 對調之後就是題目要的答案。
假設現在有長度為 $4$ 的解 $[0, 1, 3, 2]$，如下圖，其中兩個數字中間有線代表這兩個數字只差一個位元。
```
0 - 1 - 3 - 2
|___________|
```
這時可以再複製一份長度為 $4$ 的解，並且將複製後的每個元素都加 $4$。
```
0 - 1 - 3 - 2
|___________|
4 - 5 - 7 - 6
|___________|
```
可以發現 $0, 4$、$1, 5$、$3, 7$ 和 $2, 6$ 中間會有邊，因為他們只差一個位元（就是 $4$），如下圖。
```
0 - 1 - 3 - 2
| | | |
4 - 5 - 7 - 6
```
因此就可以得到長度為 $8$ 的解 $[0, 1, 3, 2, 6, 7, 5, 4]$。
```cpp!
int* circularPermutation(int n, int start, int* returnSize){
*returnSize = (1 << n);
int *arr = malloc(sizeof(int) * (*returnSize));
arr[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = (1 << i); j < (2 << i); ++j)
arr[j] = arr[(2 << i) - j - 1];
for (int j = (1 << i); j < (2 << i); ++j)
arr[j] |= (1 << i);
}
int i;
for (i = 0; arr[i] != start; ++i)
;
int *result = malloc(sizeof(int) * (*returnSize));
for (int j = 0; j < (1 << n); ++j)
result[j] = arr[(i + j) & ((1 << n) - 1)];
free(arr);
return result;
}
```
#### 方法二：直接找出第一項為 $start$ 的解
在上個方法中，我們每次都是把陣列的後半的元素的 $2^i$ 這個位元設為 $1$，然而其實可以透過確認 $start$ 中的 $2^i$ 這個位元是否為 $1$ 來決定要設為 $1$ 的是前半還是後半的元素。
因為迴圈結束後第一項就會是 $start$，所以也不需要額外的記憶體空間來重新排列。
```cpp!
int* circularPermutation(int n, int start, int* returnSize)
{
*returnSize = (1 << n);
int *arr = malloc(sizeof(int) * (*returnSize));
arr[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = (1 << i); j < (2 << i); ++j)
arr[j] = arr[(2 << i) - j - 1];
int begin = (~start) & (1 << i);
for (int j = 0; j < (1 << i); ++j)
arr[begin + j] |= (1 << i);
}
return arr;
}
```
## [Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
### 題目敘述
給定一個鏈結串列，請將鏈結串列中的元素兩兩交換。
例如：
```
[1, 2, 3, 4] -> [2, 1, 4, 3]
[1, 2, 3] -> [2, 1, 3]
[] -> []
```
不可直接改鏈結串列的節點的值。
### 程式碼解說
#### 方法一：使用 Sentinel Node
為了方便操作，在 `head` 前面再多加一個節點，而 `for` 迴圈的指標就從多加的那個節點開始，如果此節點後面有兩個以上的節點，就交換那兩個節點，之後再將指標指向下下個節點，就可以重複一樣的過程，交換剩下的節點。
```cpp!
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *swapPairs(struct ListNode *head)
{
struct ListNode sentinel = {.next = head};
for (struct ListNode *p = &sentinel;
p->next != NULL && p->next->next != NULL;
p = p->next->next) {
struct ListNode *nxt = p->next;
p->next = nxt->next;
nxt->next = p->next->next;
p->next->next = nxt;
}
return sentinel.next;
}
```
#### 方法二：使用指標的指標
使用指標的指標來節省上個方法的 `sentinel` 所使用的空間。
```cpp!
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *swapPairs(struct ListNode *head)
{
for (struct ListNode **pp = &head;
(*pp) != NULL && (*pp)->next != NULL;
pp = &((*pp)->next->next)) {
struct ListNode *nxt = (*pp)->next;
(*pp)->next = nxt->next;
nxt->next = (*pp);
(*pp) = nxt;
}
return head;
}
```
### Follow Up: [Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/)
#### 題目敘述
給定一個鏈結串列，前一題是兩個為一組做反轉，這次變成 $k$ 個為一組來反轉，若是最後剩下的元素不到 $k$ 個，就不進行反轉。
#### 解法
這邊使用遞迴來解這題，`revK(pp, k)` 會反轉以 `*pp` 為開頭的 $k$ 個元素，並且遞迴的處理剩下的元素，直到剩下的元素小於 $k$ 個。
```cpp!
void revK(struct ListNode **pp, int k)
{
struct ListNode *end = *pp;
for (int i = 0; i < k; ++i) {
if (end == NULL)
return;
end = end->next;
}
struct ListNode *p, *nxt;
for (p = *pp; (*pp)->next != end;) {
nxt = (*pp)->next;
(*pp)->next = nxt->next;
nxt->next = p;
p = nxt;
}
revK(&(*pp)->next, k);
*pp = p;
}
struct ListNode *reverseKGroup(struct ListNode *head, int k)
{
revK(&head, k);
return head;
}
```
## 自我檢討
* 英語口說需加強，常常講到一半就會停下來想接下來要說的內容
* 程式碼撰寫時可以加一些註解方便理解
* 常因為打字太急而出現錯字，也因此需要多花時間修改
* 在解費氏數列的題目時，應該要先解釋自己的做法，之後再撰寫程式碼
## 同學互評
### Fibonacci Number
[06:22](https://youtu.be/vtdFTbQCDmI?t=382)
interviewee
- 可分析為何此陣列運算可達到 $O(lg(n))$
其他
interviewer
- 在時間允許情況下，可請面試者推導費波那契數一般式 $F_n$
## 同學互評 02
### Fibonacci Number
- [00:33](https://youtu.be/vtdFTbQCDmI?t=33)：建議可以在給範例的時候列出前 5~10 個費氏數列，原因是可能不是每個人都了解，列出能讓 interviewee 更清楚
- [00:57](https://youtu.be/vtdFTbQCDmI?t=57)：可能題目確實比較經典，所以沒有做 react，不過建議還是在實作前進行 approach，像是可以說一開始最 naive 的 recusive 解法，並說明該解法重複運算太多次，因此 dp 的方式存儲運算過的部分，進而降低複雜度
- [02:33](https://youtu.be/vtdFTbQCDmI?t=155)：這部分是原本用大小為 n 的陣列處理，由於每次運算只會用到前兩個，因此改為大小為 const 的陣列，這邊會讓我覺得你已經知道了這個方法比較好，但在演給我看，比較不自然的感覺，因此建議可以在這邊停一下如果 interviewer 要問優化時再進一步說明，或者在 approach 的部分直接講明思考過程，並直接實作較佳的解法
- [07:05](https://youtu.be/vtdFTbQCDmI?t=425)：interviewer 有詢問如何計算出時間複雜度，這點我覺得挺好，可以知道 interviewee 是不是確實了解
- [07:11](https://youtu.be/vtdFTbQCDmI?t=431)：這部分應該是 interviewee 而非 interviewer
- 有講述到 _O(logn)_ 的解法，或許也能時做出來，為以下 ([參考資料](https://leetcode.com/discuss/explore/april-leetcoding-challenge-2021/1159786/fibonacci-number-easy-solution-w-multiple-approaches-explained))
``` c=!=
int F[2][2] = {{1, 1}, {1, 0}}, M[2][2] = {{1, 1}, {1, 0}};
int fib(int n) {
if(n <= 1) return n;
power(F, n - 1);
return F[0][0];
}
void power(int F[2][2], int n){
if(n <= 1) return;
power(F, n / 2);
matrixMul(F, F);
if(n & 1)
matrixMul(F, M);
}
void matrixMul(int F[2][2], int M[2][2]){
int m00 = F[0][0] * M[0][0] + F[0][1] * M[1][0];
int m01 = F[0][0] * M[0][1] + F[0][1] * M[1][1];
int m10 = F[1][0] * M[0][0] + F[1][1] * M[1][0];
int m11 = F[1][0] * M[0][1] + F[1][1] * M[1][1];
F[0][0] = m00, F[0][1] = m01, F[1][0] = m10, F[1][1] = m11;
}
```
## 同學互評 03
### Interviewer
[0:00](https://youtu.be/OUIiq9H9kYI) 可以再跟面試者閒聊一下，讓彼此更多互動
### Interviewee
[8:15](https://youtu.be/OUIiq9H9kYI?t=484) 沒有解釋為甚麼%2的n次方
程式碼的部分會讓人看得很亂，因為把次方都寫成1>>n跟2>>n
我覺得可以在for迴圈中間宣告像是
```jsx
unsigned int len = 1 << i; //2 << i 就是 2*len
```
會讓程式碼可讀性更高，加上for迴圈變成兩半，看得不太舒服
[9:47](https://youtu.be/OUIiq9H9kYI?t=587) 在講解直接找到開頭就是start的解的部分，我第一次聽的時候沒聽懂，可能是我理解力差，但是我覺得跳過太多東西了，包括怎麼會有這個想法，以及透過檢查start的2^i的bit去決定前半後半，來讓開頭是start，兩個聽起來就會很跳，沒有解釋為甚麼這樣做，start就會是開頭，只是把解法講出來而已
### ****[Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)****
聲音很炸
### Interviewer
[14:13](https://youtu.be/OUIiq9H9kYI?t=853) 問的問題我覺得有點怪，因為p不管指向哪個我覺得差異只是實作方式，即使用兩個指標去操作我覺得問題也不大
[17:57](https://youtu.be/OUIiq9H9kYI?t=1077) 我覺得問題有點沒有必要，因為說node更改會增加記憶體空間，但整個code也只有用到2個node，如果要改進的話，挑這個地方我覺得有更好的選擇，但在看完後面後，才了解到因為是遞迴會用到很大量的空間，這時候我覺得才會是合理的修改
### Interviewee
在Follow up的部分，我是聽了下面的YT連結才了解
[https://youtu.be/1UOPsfP85V4](https://youtu.be/1UOPsfP85V4)
我覺得解釋部分可以再加強，包括畫圖的部分，在解釋想法時，圖上已經有之前畫過的線，變成你講的跟圖上的不一樣，看的就不是很明白，以及為甚麼要用遞迴，遞迴的作用是甚麼，我覺得都沒有很清楚的解釋到
## 同學互評 04
( [509. Fibonacci Number](https://leetcode.com/problems/fibonacci-number/) )
1. [02:54](https://youtu.be/vtdFTbQCDmI?t=174) “dp i minus 1” 為 `dpi-1`, 若要表示 `dpi_1` 的話能夠說 “dp i underscore 1” 或是為變數命名表示
1. [04:40](https://youtu.be/vtdFTbQCDmI?t=280) 函式回傳值為 `int` 在長度為 32 位元的情況下只能算到大約 Fib(47)，64 位元能夠到大約 Fib(93)。直接說效率不足不太好，這部分可能可以當作延伸問題
1. [06:23](https://youtu.be/vtdFTbQCDmI?t=383) $\begin{pmatrix}
1 & 1\\
1 & 0
\end{pmatrix}^{(n-1)}$ 的時間複雜度為 $O(n)$
解釋平方求冪之前假定時間複雜度為 $O(\lg{n})$ 會讓 interviewer 誤會你不知道自己在說什麼，當作interviewee 在背答案。這裡可以先說時間複雜度為 $O(n)$ 再提出最佳化至 $O(\lg{n})$ 的方案
1. [06:51](https://youtu.be/vtdFTbQCDmI?t=411) 這裡開始應該是 interviewee 回答，不過畫面顯示 interviewer
1. [08:04](https://youtu.be/vtdFTbQCDmI?t=484) 沒有完整解釋為什麼能夠最佳化時間複雜度至 $O(\lg{n})$
這裡能夠手寫數學式解或是直接畫 recurrence tree 解出時間複雜度
> 數學式：
$\begin{equation}
x^n = \begin{cases}
1 & \text{if}\ n = 0. \\
\lfloor x^{n/2}\rfloor^2 & \text{if n > 0, }\ n\ \text{is even}. \\
\lfloor x^{n/2}\rfloor^2 \cdot x & \text{if n > 0, }\ n\ \text{is odd}. \\
\end{cases}
\end{equation}$
可以看到每一步都會將 n 次式減半
假設時間複雜度為 $O(k)$
$\begin{equation}
\begin{split}
\dfrac{n}{2^k}\ &\leq\ &1 \\
n\ &\geq\ &2^k \\
\lg{n}\ &\geq\ &k \\
\end{split}
\end{equation}$
時間複雜度 $O(k) = O(\lg{n})$
> Recurrence Tree :
時間複雜度為二元樹的高度 $O(\lg{n})$
Sign in with Wallet
Connect another wallet