課程名稱：資料結構 CS203 A授課教師：林基成考試時間：2020-10-18 題目說明基本上和作業一及作業三一模一樣，但是都有簡化。 Midterm1： 為作業一的簡化，基本上都一樣，但是只需要完成 insert，不需要寫 erase。 Midterm2： 為作業三的簡化，基本上都一樣，但是 Case 被簡化了許多。 解題思路由於跟作業一模一樣，在此不再贅述。 修改內容在考試時已經都 0 errors。但是在紅黑樹的 fixUp() 中，忘記老師說只有什麼 Case 了，所以就把全部的 Case 都寫了，還有 insert 的部分 if (n->myval == val) return; 這一個判斷可能會有 myHead->myval == val 的情況導致沒有新增 node，修改後為 if (!n->isNil && n->myval == val) return; 即可避免這個問題。 裡面有三個資料夾： MidtermExam： 為題目的原始檔。 Midterm - original： 考試繳交的版本。 Midterm - ...

題目： LeetCode - 859. Buddy Strings 題目說明給兩個 String A, B，A 需要交換任意兩字元一次，求交換後的 A 是否等於 B。 解題思路先檢查兩者長度是否相等，若不相等則直接回傳 False。接著檢查，若兩者原本就已經相等，則判斷 A 內是否有重複的字元，因為 A 一定要交換一次，若 A 中沒有重複的字元則交換後會變為不相等，這裡使用 hashset 來判斷。最後遍歷兩者，將兩者字元不同的 index 儲存，最後判斷 diff 的大小是否為 2，若為 2 則判斷 A[diff[0]] 是否等於 B[diff[1]] 且 A[diff[1]] 是否等於 B[diff[0]] ( 此條件為檢查是否 A 元素互換後會等於 B ) 若都符合則回傳 True，否則回傳 False。 參考解法12345678910111213141516171819// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr) ...

課程名稱：線性代數 CS233 B授課教師：簡廷因發放時間：2020-10-05截止時間：2020-10-26 23:59:59 Get a filename F1 from parameter, and using STDOUT for output Sample input : case1.bmpSample output : This is the testing sentence and will convert into a QR-code like photo.Sample command : ./tinin.exe case1.bmp 題目說明給一個 bmp 檔案，由下而上，由左至右，每 8 個像素點代表一組二進位數字 ( 白為 0、黑為 1 )，表示為 Ascii Code，求解碼後的字串。 解題思路bmp 檔案其實就是以二進制檔案來表示圖片的儲存格式，以本次作業的測資來說，前 54 個 byte 為 bmp 的 header，紀錄一些圖片的基本訊息，如：長度、寬度 … 等等。接著就是像素點的訊息，3 個 byte 一組，分別代表一個像素點的 B、G、R，並且由圖片 ...

題目： LeetCode - 67. Add Binary 題目說明給兩個 String 代表兩個二進制表示法的數字，求兩數字的和的二進制表示法。 解題思路從兩數字的最後一位開始往前走，分別將數值加到 c 中，最後存到目前結果的前面。直到兩數都走完且 c 為 0 才停止。 參考解法12345678910111213141516class Solution {public: string addBinary(string a, string b) { string str; int i = a.length() - 1, j = b.length() - 1, c = 0; while(i >= 0 || j >= 0 || c) { if(i >= 0) c += a[i--] - '0'; if(j >= 0) c += b[j--] - '0'; str ...

課程名稱：資料結構 CS203 A授課教師：林基成發放時間：2020-09-29截止時間：2020-10-06 題目說明完成 Set 中使用到的紅黑樹中的部分函式。 解題思路這次作業的結構為內部為二元紅黑樹的 Set，由於 Code 內已有註解，在此不再贅述，只說大方向的做法。 插入元素: void insert(const value_type &val) 函式功能： 插入一個元素到 Set 中，若元素已經存在則不插入。 參考作法： 先判斷該值是否已經存在，若不存在則找到該值的 parent ( degree <= 1 )，並調整紅黑樹的平衡。 參考解法：1234567891011121314151617181920212223242526272829303132// Extends the container by inserting a new element,// effectively increasing the container size by one.void insert( const value_type &val ){ ...

題目： LeetCode - 41. First Missing Positive 題目說明給一個陣列，求從 1 開始的正整數哪個最先沒有出現在陣列中。 解題思路先使用 Index Sort 將陣列排序好後從頭開始尋找即可。 參考解法1234567891011class Solution {public: int firstMissingPositive(vector<int>& nums) { nums.insert(begin(nums), 0); for(int i = 0; i < nums.size(); ++i) while(nums[i] != i && nums[i] > 0 && nums[i] < nums.size() && nums[i] != nums[nums[i]]) swap(nums[i], nums[nums[i]]); for(int i = 1; i < n ...

題目： LeetCode - 139. Word Break 題目說明給一個陣列及一個字串，求字串能否由陣列中的字串組成。 解題思路使用動態規劃，dp[i] 代表前 i 個字符組成的字串可以被字典中的字串組成。先在 s 前面增加一個空格方便計算，使用一個迴圈遍歷字串，將目前遍歷到的字串分為兩個部分，若前面的部分及後面的部分都可以被組成則代表目前遍歷到的字串可以被組成。最後回傳 dp[n] 即可。 參考解法12345678910111213141516171819202122// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: bool wordBreak(string s, vector<string>& wordDict) { ...

題目： LeetCode - 713. Subarray Product Less Than K 題目說明給一個只含正整數的陣列及整數 k，求陣列中有幾個子陣列相乘的乘積小於 k。 解題思路由於題目有保證陣列大小會大於 0，所以需要先判斷若 k <= 1 則直接回傳 0，接著使用 Sliding window，遍歷陣列當作確定的右端點 r，左端點 l 從 0 開始，若乘積已經大於等於 k 則將乘積除以 nums[l] 並將 l 加一，此時符合條件的子陣列個數為 r - l + 1。 參考解法1234567891011121314151617181920212223// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: int numSubarrayProductLe ...

課程名稱：資料結構 CS203 A授課教師：林基成發放時間：2020-09-22截止時間：2020-09-29 題目說明完成 Priority_queue 中使用到的 heap 中的部分函式。 解題思路這次作業的結構主要是用陣列來模擬的二元樹，若樹節點比下面的樹節點的值都大為 max heap，若比下面的樹節點都小為 min heap，first 為陣列開頭的指標，pred 為比較的方法，若 perd 為 less 則為 max heap，若為 greater 則為 min heap。 下面是依照我寫的順序來排序的。 inline void pushHeapByIndex(RanIt first, ptrdiff_t hole, ptrdiff_t top, Ty& val, Pr pred) 函式功能： 從 hole 開始，找到 val 應該填入的正確位置。 參考作法： 定義 i 為當前 hole 的 parent，接著判斷若是 hole > top 且 pred(first[i], val)，表示 parent 的值需要往下移，最後更新使 hole = i 以及 ...

題目： LeetCode - 399. Evaluate Division 題目說明待編輯… 解題思路待編輯… 參考解法12345678910111213141516171819202122232425262728293031323334class Solution {public: vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) { int n = equations.size(); vector<double> ret; unordered_map<string, unordered_map<string, double>> _m; for(int i{} ...