# 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²)，因為仍需遍歷所有元素。 🟦：很好。您對更新順序的說明也很清楚。這樣的解法既節省記憶體，又維持正確性。今天的面試到此結束，謝謝。