---
# System prepended metadata

title: 2025 年資訊科技產業專案設計作業 2

---

# 2025 年「資訊科技產業專案設計」作業 2
> 貢獻者: 周瑜 Zhou Yuuu, 伏爾泰 Voltaire

模擬面試影片 Leetcode .119
https://youtu.be/-65SRk0IXmQ

面試錄影 Leetcode .83
https://youtu.be/gX6slbtOdB8

## [Leetcode 83.](https://leetcode.com/problems/remove-duplicates-from-sorted-list/description/)
🟦 Interviewer : 周瑜 Zhou Yuuu

🟨 Interviewee : 伏爾泰 Voltaire


### 面試過程
🟦：您好，今天面試的題目是刪除一個已排序的 List 中重複的數字，我會給你一個已排序的 Linked list 的 head，然後要刪除掉重複的數字，然後回傳這個被刪除重複數字的 linked list。

🟨：是 singly linked list 還是 doubly linked list？

🟦：是 singly linked list。

🟨：刪除重複的意思是？以 1->2->2->3 為例，是要刪除成 1->2->3 還是 1->3？

🟦：先刪除到所有數字都只出現一次。

🟨：是遞增還是遞減的排序？

🟦：是遞增的排序。

🟨：數字是 integer, 32 bits 的型態嗎？

🟦：是。

🟨：實作的話首先定義 node 的型態。然後舉一個例子，第一個 1->2->2->3 要刪除成 1->2->3，然後再舉一個例子顯示 edge case 情況，假設說 1->1->1->2->3->3，在這個情況下，總共會有兩個要刪除，1 跟 3 要刪除，變成 1->2->3。然後有個 edge case 是這個 linked list 只有一個節點，就不用處理直接回傳。

🟨：那我還想問 head 是一個指標嗎？還是 node 的型態。

🟦：對，是一個指標。

🟨：好，那 head 就是一個指標指向第一個節點嗎。

🟨：接下來我講一下我的解法，我會走訪 linked list，用一個指標指向目前正在走訪的這個節點，然後我們比較這個節點的數值和下一個節點的數值，若一樣，就刪除掉下一個節點，將上一個節點的指標指向下一個節點，然後繼續比對，如果比對到不一樣，就會遞推到下一個，繼續比對，跟剛剛一樣的邏輯，一樣就刪掉。

🟦：OK，聽起來沒有問題

🟨：那這個程式碼首先會回傳一個 head，輸入的參數也是一個 head。

```c
struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (!head) return head;
    if (!head->next) return head;

    struct ListNode *curr = head, *dupli = NULL;
    while (curr != NULL && curr->next != NULL) {
        if (curr->val == curr->next->val) {
            dupli = curr->next;
            curr->next = curr->next->next;
            free(dupli);
        }
        else curr = curr->next;
    }

    return head;
}
```

🟦：這邊有個小問題，其實第二個 if 判斷，與迴圈的中止條件重疊，是不是其實不需要？

🟨：對，這行是不需要的。

🟦：接下來給你一個 follow-up，刪除重複的數字的時候，要把有重複的數字全部刪除。

🟨：我的思路是定義一個 boolean，標記 curr 節點是不是屬於重複的節點，以及一個 previous 節點。一旦比對下一個是一樣的，就把目前的 curr 節點標為 true，然後刪除的操作跟之前一樣，但是如果比對到下一個不一樣的話，要看標記是否為 true，若為 true，就要把這個 curr 節點刪掉，並把 prev 節點的指標指向 curr 的下一個。

```c
struct node *deleteDuplicate(struct node *head)
{
	if (!head) return head;

	bool is_curr_dupli = false;
	struct node *curr = head, *prev = head;
	for (; curr->next != NULL;) {
		if (curr->val == curr->next->val) {
			is_curr_dupli = true;
			struct node *dupli = curr->next;
			curr->next = curr->next->next;
                        free(dupli);
            if (is_curr_dupli && curr->next = NULL) {
	            prev = curr->next;
	            free(curr);
	            is_curr_dupli = false;
                }
        }
        else {
            if (is_curr_dupli) {
	            prev = curr->next;
	            struct node *delete = curr;
	            curr = curr->next;
	            free(delete);
	            is_curr_dupli = false;
            }
            else curr = curr->next;
        }
    }
    return head;
}
```

## [Leetcode 119.](https://leetcode.com/problems/pascals-triangle-ii/description/)
🟦 Interviewer : 伏爾泰 Voltaire

🟨 Interviewee : 周瑜 Zhou Yuuu

---

### 面試過程
🟦：您好，我們現在開始面試。請您設想您現在加入了一個開發即時分析工具的團隊。我們的任務是要在前端圖表顯示二項分佈的係數。您的工作是實作一個函式，用於計算這些二項分佈的係數。

🟦：該函式需要輸入一個整數 N，並回傳第 N 列的二項分佈係數。

🟨：有的。想請問 N 的起始值是0還是1呢？

🟦： N 的起始值是0。

🟨：所以如果輸入N = 0時，輸出應該為內容只有一個數字1的一維陣列對嗎。

🟦： 沒錯

🟨：那我再舉幾個例子確認我的想法無誤。

```

n=2 [1,2,1]
n=3 [1,3,3,1]

```
🟦： 沒有問題，你可以開始撰寫程式了。

🟨：好的。那我先說明我初步的想法。我目前想到最直觀的方法是列出從 0 到 N 的所有列。由於每一列的元素是上一列相鄰兩個元素的總和，我可以使用一個二維陣列 來儲存所有的列。最後，再根據輸入的 N 值，回傳指定的那一列結果。

🟦：好的，聽起來邏輯沒有問題，就先從這裡開始嘗試吧。

#### Code 1

```cpp=
vector<int> getRow(int n) {
    vector<vector<int>> triangle;
    for(int i = 0; i < n + 1; i++){
        vector<int> row(i + 1);
        row[0] = 1;
        row[i] = 1;
        triangle.push_back(row);
    }
    for(int i = 1; i < n; i++){
        for(int j = 0; j < i; j++){
            triangle[i + 1][j + 1] = triangle[i][j + 1] + triangle[i][j];
        }
    }
    vector<int> output;
    for(int i = 0; i < n + 1; i++)
        output.push_back(triangle[n][i]);
    return output;
}
```

🟦：程式碼的邏輯看起來沒有問題。不過，我想進行一個延伸討論。您目前使用了二維陣列來儲存所有結果，以及一個 output 陣列來儲存最終結果。您是否有思考過優化空間複雜度，只使用一個大小為 N+1 的一維陣列來完成整個計算過程？

🟨：我確實有考慮過這一點。由於每一行只與其上一行相關，確實不需要儲存整個帕斯卡三角形。我們可以重複利用同一個大小為 N+1 的陣列。

🟨：在更新時，我認為必須從後面的數字往前更新 (倒序)。

🟦：請您進一步闡述為什麼必須從後方更新，以及如果從前面開始更新會導致覆蓋 (Overwrite) 問題的具體過程。

🟨：好的。如果我們從前向後更新，當我們計算當前列的某個數字時，它需要用到上一列中前方相鄰的數值。但若從前往後更新，前方的數值已經被當前列的計算結果所覆蓋。這樣一來，後續運算就會使用到被修改過的新值而不是上一列的舊值，導致結果錯誤。因此，我們必須從後往前更新，以確保每次使用的都是上一列未被覆蓋的值。

#### Code2

```cpp=
vector<int> getRow(int n) {
    vector<int> row(n + 1, 0);
    row[0] = 1;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j > 0; j--){
            row[j] = row[j] + row[j - 1];
        }
    }
    return row;
}
```
🟨：用n=3的例子來說明一維矩陣的更新。
```
n=0[1,0,0,0]
n=1[1,1,0,0]
n=2 [1,2,1,0]
n=3 [1,3,3,1]
```

🟨：這樣的優化能將空間複雜度從 O(N²) 降至 O(N)，時間複雜度仍為 O(N²)，因為仍需遍歷所有元素。

🟦：很好。您對更新順序的說明也很清楚。這樣的解法既節省記憶體，又維持正確性。今天的面試到此結束，謝謝。