2023 年「資訊科技產業專案設計」課程第 1 次作業

--- title: 2023 年資訊科技產業專案設計作業一 tags: INF02023 --- # 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/)」課程第 1 次作業 > 貢獻者: 東尼-Tonny > [模擬面試錄影-1](https://www.youtube.com/watch?v=wjSqYJdnXFM) > [模擬面試錄影-2](https://www.youtube.com/watch?v=LwsIlnniceo) > [模擬面試錄影-3](https://www.youtube.com/watch?v=I2CrDO7NTS8) ## [217. Contains Duplicate](https://leetcode.com/problems/contains-duplicate/) > [模擬面試錄影](https://www.youtube.com/watch?v=wjSqYJdnXFM) ### 題目敘述給定一個整數陣列 nums，如果陣列中至少有一個值重複出現，則回傳True；如果每個陣列元素都是唯一的，那麼就回傳False。 ### 程式碼解說 - [ ] 方法一: ***暴力求解*** 從陣列起點元素開始存取, 對陣列中每個元素互相兩兩比較。使用到兩個`for`迴圈實作外層迴圈從第`0`個元素開始，存取第`i`個陣列元素，至第`n-1`個元素停止。內層迴圈從`i+1`個元素開始，存取第`j`個元素，至第`n`個元素停止。迴圈內部對陣列的第`i`和`j`個元素做比較，如果相等，則代表有元素重複出現在陣列過。由於對陣列做了兩層的存取，第一層迴圈存取了`n`次，第二層迴圈存取了`n`次，共存取了 $n^2$ 次。時間複雜度為：$O(n^2)$，`n`為陣列的大小。 ```cpp class Solution { public: bool containsDuplicate(vector<int>& nums) { int n= nums.size(); for(int i= 0; i< n-1; i++){ for(int j= i+1; j< n; j++){ if(nums[i]== nums[j]){ return true; } } } return false; } }; ``` - [ ] 方法二: ***先對陣列做排序，再存取陣列*** 因為我們的目標是要找到重複出現過的陣列元素，對陣列做排序後，所有元素都會以升序排列排好，而重複出現過的陣列元素會排在一起。這樣就只需要對陣列做一次`for`迴圈存取，對相鄰的陣列元素做比較，即可知道是否有元素重複出現。方法二只需要對陣列做一次存取，但由於需要對陣列排序，時間複雜度為`O(nlogn)` ```cpp class Solution { public: bool containsDuplicate(vector<int>& nums) { sort(nums.begin(), nums.end()); int n= nums.size(); for(int i= 0; i< n-1; i++){ if(nums[i]== nums[i+1]){ return true; } } return false; } }; ``` ## [118. Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/) > [模擬面試錄影](https://www.youtube.com/watch?v=LwsIlnniceo) ### 題目敘述給定一個整數numRows，回傳Pascal's triangle的前numRows行的內容。在Pascal's triangle中，每個數字都是其正上方兩個數字的和，如下所示： ![](https://hackmd.io/_uploads/SJXhOkLJp.gif) ### 程式碼解說 - [ ] 方法一: ***遞迴求解*** 在巴斯卡三角形中，每個元素值都是該元素正上方兩個元素的和。可以用遞迴的方式把三角形建立出來。遞迴初始狀態為`numRow== 1`時，回傳`[[1]]`。當`numRow`為其他值時，就重複呼叫遞迴函式`generate(numRows-1)`，並且利用「每個元素值都是該元素正上方兩個元素的和」這個特性，將每一行的值算出來。由於要重複呼叫數次遞迴函式，並且重複計算先前的元素數次，這並不是有效率的做法。 ```cpp class Solution { public: vector<vector<int>> generate(int numRows) { if (numRows== 0){ return {}; } if (numRows== 1){ return {{1}}; } vector<vector<int>> previousRow= generate(numRows-1); vector<int> newRow(numRows, 1); for(int i= 1; i< numRows-1; i++){ newRow[i]= previousRow.back()[i-1]+ previousRow.back()[i]; } previousRow.push_back(newRow); return previousRow; } }; ``` - [ ] 方法二: ***Dynamic Programming作法*** 為了避免重複呼叫遞迴函式做重複的計算，可以建立一個二維陣列存放先前計算過的結果。當需要用到先前計算結果時，以查表的方式代替遞迴呼叫。並且利用巴斯卡三角形的特性：每個元素值都是該元素正上方兩個元素的和。對二維陣列而言，就是把第`i-1`列、第`j-1`行的元素和第`i-1`列、第`j`行的元素相加，即可得到第`i`列、第`j`行的結果。這個做法比起方法一的遞迴呼叫更有效率，因為不用重複計算那些已經算過的數值，但是需要多一些空間存放二維陣列。 ```cpp class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> result(numRows); for(int i= 0; i< numRows; i++){ result[i].resize(i+1, 1); for(int j= 1; j< i; j++){ result[i][j]= result[i-1][j-1]+ result[i-1][j]; } } return result; }; }; ``` ## [143. Reorder List](https://leetcode.com/problems/reorder-list/) > [模擬面試錄影](https://www.youtube.com/watch?v=I2CrDO7NTS8) ### 題目敘述給定一個單向鏈結串列的起點。這個鏈結串列可以表示成 `L0 → L1 → … → Ln - 1 → Ln` 將鏈結串列重新排列為以下形式： `L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …` 你不能修改串列節點中的值，只能更改節點本身。 ### 程式碼解說 - [ ] 方法一: ***暴力解*** 從起點開始存取每個節點，一路存取至倒數第二個節點，並依照題目規則，對節點重新做連接。這個做法使用遞迴呼叫，重複存取節點，因此在效率上不太好。 ```cpp class Solution { public: void reorderList(ListNode* head) { if(head== NULL || head->next== NULL || head->next->next== NULL){// if linked-list only have 0, 1 or 2 Node,we don't need to reorder it return; } // Find the penultimateNode;start from head and traverse list. ListNode* penultimateNode= head; // Find the penultimateNode;start from head and traverse list. while(penultimateNode->next->next !=NULL){ //start traversing list. Exit the loop when the next two node is empty penultimateNode= penultimateNode->next; } //Link the penultimateNode with the second element //L1-> Ln-> L2 -> Ln-1 penultimateNode->next->next= head->next; // Ln-> L2 head->next= penultimateNode->next;// L1-> Ln // link the penultimate Node to the last penultimateNode->next= NULL ; //do the steps recursively reorderList(head->next->next); } }; ``` - [ ] 方法二: ***龜兔賽跑演算法*** 改用另一個想法：把串列從正中間拆開，形成兩個串列，將第二個串列連接的順序翻轉，接著將串列合併起來。這個做法用到兩個指標`tmp`和`half`。`tmp`這個指標每次存取時都向前走兩步，`half`則是只向前走一步，當存取結束後兩個指標會分別指向串列最後一個節點及中間那個節點。從`L0`開始到`half`是前半部的串列，而`half`到`tmp`是後半部的串列。將後半部串列連接順序翻轉，並與前半部合併即可。 ```cpp class Solution { public: void reorderList(ListNode* head) { // base case : linkedlist is empty if (head== NULL) return; // finding the middle with the help of two pointer approach ListNode *tmp = head, *half = head, *prev = NULL; while (tmp->next && tmp->next->next) { tmp = tmp->next->next; half = half->next; } // adding one bit in case of lists with even length if (tmp->next!= NULL) { half = half->next; } // Now reverse the second half while (half!= NULL) { tmp = half->next; half->next = prev; prev = half; half = tmp; } half = prev; // After reversing the second half, let's merge both the halfes while (head != NULL && half!= NULL) { tmp = head->next; prev = half->next; head->next = half; half->next = tmp; head = tmp; half = prev; } // Base case : closing when we had even length arrays if (head != NULL && head->next!= NULL){ head->next->next = NULL; } } } ``` --- ## 第二次作業-他評01 - [ ] 優點 * 對於這份作業非常的用心 * [25:53](https://youtu.be/wjSqYJdnXFM?si=nr7fnZ_jFAysm2oX&t=1553)面試官跟面試者都有大量的互動，並且很詳細的問答了整個時間複雜度的相關內容 ### 關於interviewee - [ ] 優點 * 有將原本leetcode的問題包裝成一個很實際的應用，在設計面試題目時有小巧思 - [ ] 可改進的地方 * [14:50](https://youtu.be/wjSqYJdnXFM?si=fk42AdNvtnCBPjEn&t=890): 可以考慮這邊要不要順便提問相關的時間複雜度，而非說這樣做的比較時間太長了 ### 關於interviewer - [ ] 優點 * 有跟面試官有很多的交流，並重複確認問題 * 在coding的過程都有適時地加上註解，讓人容易理解 - [ ] 可改進的地方 * [03:30](https://youtu.be/wjSqYJdnXFM?si=hggo97_LR1TTmkau&t=210)可以跟面試官先確認一下要要何種語言作答會比較恰當 ## 第二次作業 - 他評 02 ### interviewer - [ ] 優點 * 有將題目做包裝 * 有針對程式碼與複雜度分析做討論 - [ ] 可改進處 * [0:28](https://youtu.be/wjSqYJdnXFM?si=ct7kpoDUfSJ9hqPX&t=28): 建議將「你要面對的第一道題目」改成有一些問題想跟面試者討論，降低面試緊張氣氛。 ### interviewee - [ ] 優點 * 清楚的與面試官確認題意，確定雙方的理解沒有誤差。 - [ ] 可改進處 * [2:45](https://youtu.be/wjSqYJdnXFM?si=P1mrtoAvz9Kr5VxE&t=165), [16:57](https://youtu.be/wjSqYJdnXFM?si=T-fo-ZoeUIKueJLZ&t=1017), [22:49](https://youtu.be/wjSqYJdnXFM?si=5oMo0aywQ3zG7o_E&t=1369), [3:24](https://youtu.be/LwsIlnniceo?si=fgk87lPeqnuJV09K&t=204) etc.: 不用把文字打出來，或是簡短的作標記即可。 - [17:55](https://youtu.be/wjSqYJdnXFM?si=K1P1AstcHeKrW3LK&t=1075): 因為比較的方式已經顯而易見，可能直接用口述的方式會比較好。 - [26:18](https://youtu.be/wjSqYJdnXFM?si=cHidrfsoseAnGsZL&t=1578): 答非所問，也許直接回答因為使用的是比較排序法，而比較排序法的下界是 $O(n \log{n})$。如果有需要進一步帶到證明感覺會比較好。 ## 第二次作業 - 他評 03 ### 關於 interviewer - [ ] 優點 * 以文件的方式敘述題目，傳達更清楚，很好。 * 有將題目包裝過，包裝後能有效避免刷題怪。 - [ ] 可以改進的地方 * 「同學你好」，這稱呼似乎不太對。 * 「讓我來講解一下這題的目標」感覺就可以了，用到「面對」似乎太過嚴肅。 * 不用整個畫面都糊掉。 ### 關於 interviewee - [ ] 優點 * 有將想法化成文字註解。 * 寫的時候也有一邊說明。 * 有測試階段很棒。 - [ ] 可以改進的地方 * 測試階段說明i j 在陣列哪個元素的時候，可以用不同的指示符號。 * 不用整個畫面都糊掉。 ## 第二次作業 - 他評04 ### interviewer - [ ] 優點 * 有將題目去做包裝而非直接用leetcode原題 * [26:18](https://youtu.be/wjSqYJdnXFM?t=1578): 有去做follow up並且問 * 和面試者互動蠻多的 - [ ] 可改進處 * [15:10](https://youtu.be/wjSqYJdnXFM?t=910): 比較時間複雜度時，明確說明時間複雜度原本是多少那有沒有方法降低 ### interviewee - [ ] 優點 * 明確的敘述思考邏輯，在[9:53](https://youtu.be/wjSqYJdnXFM?t=593): 講解array裡的變動指不同index很明確易懂 * 時間複雜度的講解非常清楚 - [ ] 可改進處 * 不要整個打馬