AMGE’s Blogger

零面. Hacker Rank (120 min) 5 題 Hacker Rank，難度約 2 題 Easy 2 題 Medium 1題 Hard， 第 1 題: 算 duplicate 個數，解法: Hash Table O(1) 第 2 題: Smallest window that contains all characters of string itself，解法: Sliding window O(n) 第 3 題: Sort 之後取前 n 大加總 (英文閱讀測驗? )，解法: std::sort O(n log n) 第 4 題: Minimum increment to make array unique，解法: sort O(n log n) 第 5 題: Connected component，解法: DFS O(|V| + |E|) 運氣算蠻好的，Hard 那題感覺實際只有到 Medium 而已，Medium 的也都算簡單， 全部寫完還有約 40 ~ 50 分鐘，網站測資都有過，不知道實際分數就是了 XD 一面. 遠端 第一場 1hr. 1 位考官 這關是純白版題，估計是怕有人 Hacker Rank 找代打 XD  題目是四則運算，輸入 3 + 5 * 4 的字串 (無括號)，輸出 23， 看到題目很直覺告訴考官是後序，但尷尬的是老早忘記細節怎麼做 ... 冏 於是考官請我先不要管後序，想先看看我撇開前中後序下會怎麼寫， 於是就先使用直覺的方法做出一個很醜的演算法， 接著考官又加入括號問我要怎麼做，原本想繼續用很醜的方法寫， 但寫一寫發現括號會遇到的問題比較麻煩，最後就回想後序做法，最後用後序完成 ~ 第二場 2hr. 1 位考官 (應該是技術長?) 這關就不再考算法了，先自我介紹之後針對履歷開始逐一詢問， 除了針對履歷外也詢問了很多 GoFreight 會用到的技能， 如: Python2/3 差異 (range, list/tuple, unicode ... 等)，Hash 碰撞如何處理，Browser 瀏覽網頁時整個 request 的流程 (load balancer, nginx ... 等)，js 放在 header / body 差異 ... 等等， 不得不說考的內容蠻詳細的，也會針對你提出的解法做進一步追問， 最後考官會接著

  零面. 作業   作業很簡單，寫一個計算日期A到日期B之間有多少天數的程式。 一面. 現場 先考筆試，筆試題目類型很廣 (如 Pointer, Sizeof, Structure padding, cache line, race condition ...)， 筆試寫完之後接著就是技術面談， 詢問我之前在聯發科做的一些題目，例如: 如何讓效能提升好幾倍? 然後接著有介紹一下公司在做甚麼 (主要是在做高頻交易，需要接交易所 API)， 另外也有介紹到公司有一些 team 是在做 FPGA 跟網卡 Driver ... 等，用來降低交易延遲。 技術面談完之後，接著就是 HR 進來詢問我有沒有什麼問題之類的， 但不得不說我對整場面試的經驗蠻差的，原因是: 1.  零面的作業我覺得題目很沒意義 ...  2. 考了筆試卻完全沒問筆試內容，這樣筆試是在寫好玩的嗎 ... 3. 本來 HR 是找我面資深，結果說是年資不夠改成非資深的缺，我頗無言的是資深的年資說要 8 年 ...，意味者在裡面的工程師要待 8 年才能升等，中間都沒其他職等? 而且詢問 HR他們想要的資深人員的條件是啥，但也說得不清不楚 ... 4. 詢問 HR 很多關於公司制度面的事情，但 HR 好像是新來的，都不太了解 以上除了第四點我都有跟 HR 反應，HR 表示我狀況比較特別 (痾 其實3年經驗的人應該很多吧...)，會再跟主官討論看看這樣。 結果: Offer Get，福利忘了但我記得不優 (應該是比照勞基法)，83 K * 14 ~ 18 (HR 說法是每年獎金至少會有 2 個月，所以可當成 16 來看)，另外薪資部分應該可以再談，但我確定沒要去這間就沒談了

零面. Codility 3 題 Codility，難度約 1 題 Easy 2 題 Medium， 久遠有點忘記題目了，但依稀記得 1 題有字串處理，另外 2 題算是 Greedy 吧， 時間給得很充裕，我寫完大約還有一半的時間。 一面. 現場 第一場 1hr. 部門 A (2 位考官) 先自我介紹, 接著詢問我做過的一些 Project，比如這 Project 為何使用 WebSocket / Protocol Buffer ? 等等之類的問題， 其中也會討論到如何 Debug，我遇過最難解的問題是啥? 最後如何解決之類的， 因為這部門主要是 C++ ，有接著詢問例如 std::vector 跟 std::list 的差別 ... 等基礎問題， 最後考官們會在介紹這個部門的風氣、工作內容是做甚麼，合作的部門有哪些這樣。 第二場 1hr. 部門 B ( 3 位考官) 跟第一場差不多。 最後 HR 近來表示二場考官對我的 Feedback 都很正面，應該會有二次面試這樣， 詢問我比較喜歡哪一個部門這樣，我表示要再想一下後回 EMAIL， 後來我回完 EMAIL 沒多久就收到二面邀請， 電話中表示這次考官的是 Manager，大約只要 30 min，可能會有技術問題這樣。 二面. 遠端 - 30 min 面試採遠端進行，原本以為會考一些技術問題，結果主管表示他對前面的考官有信心， 所以基本上這場面試只是主管想多跟我介紹一下部門在幹嘛這樣， 主管於面談中有告知會請 HR 跑後續流程這樣， 我覺得這主管算是我面試過最有誠意的 XD 三面. 電話 HR 面談 - 60 min HR 面試採電話進行，不得不說趨勢的 HR 真的很專業， 整個過程都是在針對你的履歷做一些詢問，例如做甚麼，怎麼團隊合作 ... 等， 而且提到一些專有名詞的時候，感覺 HR 也大概知道在幹嘛這樣。 另外 HR 也會介紹公司的制度、福利 ... 等等， 而且 HR 介紹也不是隨便幾句話這樣，講得很詳細，如: 工時、獎金如何分配 ... 等， 最後 HR 問我期望薪資，並表示會再跟上面討論這樣。 結果: Offer Get，福利我覺得算不錯 (工時 7.5 hr + 第一年特休 10 天 + 彈休 7 天 + 全薪病假)，因為最後確定去這家，所以薪水有保密不好說，只能說薪資超出我原本對趨勢的想像 XD

一面. Skype  第一關 1hr. 後端考官 A  先自我介紹, 接著主考官會針對你履歷中的經歷做詢問  (印象中有: 怎麼找 race condition, cookie / session, 解釋 Polymorphism ... 等) 最後就是 Synology 必考的程式題, 題目是矩陣向右旋轉 90 度 (要求 in-place) 由於 leetcode 寫過這題, 很快就寫出 transpose 再 reflect 的解法 因為時間剩蠻多的考官 A 就問有沒有其他寫法, 於是就提出 Rotate Groups of Four Cells 這解法, 但寫的過程不是很順, 因為卡在推 index QQ, 但最後考官 A 叫我不要管 index 寫概念就好, 最後考官會讓你發問你想問的問題 (如: 公司 / 部門 ... 等) 第二關 1hr. 後端考官 B 一樣先自我介紹, 接著主考官會針對你履歷中的經歷做詢問  (印象中有: Load Balancer 可能會遇到什麼問題, 很大的資料庫下有什麼辦法加速查詢, struct 跟 class 的差異 ... 等) 最後也是 Synology 必考的程式題, 題目是實作 linked list 的 class 實作過程中考官 B 會慢慢要你增加一些功能, 並詢問你的寫法 (印象中有: nullptr 跟 NULL 差異, const int * 跟 int * const ... 等) 一樣最後考官會讓你發問你想問的問題 二面. 現場 第一關 1hr. HR 基本上就是在認識你的背景, 如: 前份工作為何離職, 怎麼會想來 Synology, 未來想走的方向 ... 等 第一關 2hr. 後端考官 C (應該是主管) 一樣先自我介紹, 接著主考官會針對你履歷中的經歷做詢問  (印象中這關技術面問得比較少, 詢問內容比較 focus 在你的背景, 未來興趣 ... 這些) 不過最後也是 Synology 必考的程式題, 題目是 Validate Palindrome 寫完後會接著延伸是問如何找出 Longest Palindrome 我寫出 Expand Around Center 的解法後主管又做了一些變形引導你寫 DP 解 原本以為要結束了, 考官最後又多出了一題類似 Encode / Decode 題,

Leetcode 網址: https://leetcode.com/problems/next-permutation/ 題目說明: 題目的大致意思是給定一組數字，請將這組數字重新排列組合得到一個比原先數字大的排列， 假設給定的數字為 1 2 3，那麼 1 3 2 就是這個題目想要的答案， 假設給定的數字為 1 3 2，那麼 2 1 3 就是這個題目想要的答案。 Note: 題目要求空間複雜度為 O(1) 解題說明: 這題透過題目的敘述及觀察皆可以發現，我們要換的數字最好是越後面的位數越好， 假設我們找到可以透過替換第 8 位達成，那前面的第 1 ~ 7 位都不需要管它了， 因此我們要從後面去掃哪一個位數可以被替換， 假設今天要替換第 8 位數，我們只要有第 9 ~ n 位數中比第 8 位數大的數字即可， 至於要替換成哪個數字，想當然就是比第 8 位數大但卻是第9 ~ n 位數中最小的數字， 因此將以上的想法寫成程式即可，不過值得注意是替換完成之後不代表是正確答案， 例如: 1 3 2 透過以上算法得到會是 2 3 1，但實際上答案是 2 1 3， 因此我們再透過把後面的數字排序即可， 以上的時間複雜度為 O(n * n + n log n) = O(n * 2)， 另外以上的算法很直覺但少用了一些題目的特性，考慮題目特性後可以優化成 O(n)， 詳細優化的算法可以參考 這篇 程式碼 void nextPermutation(vector<int>& nums) { int index = nums.size() - 1; while (index > 0 && nums[index - 1] >= nums[index]) index--; if (index > 0) { int minIndex = index; for (int i = index; i < nums.size() && nums[i] > nums[index - 1]; i++) minIndex = i; swap(nums[index - 1], nums[minIndex]);

Leetcode 網址: https://leetcode.com/problems/remove-nth-node-from-end-of-list/ 題目說明: 給定一個 linked list 與整數 n，請刪除"倒數"第 n 個 node。 Follow up: 能否在只跑一個 for loop 的情況下達成呢? 解題說明: 原本不太清楚 for loop 的定義所以直接用 stack 去解， 解完後去參考答案發現出題者想要的是用 two pointer 來解決問題， 其解法概念大致如下: 利用 first pointer 先跑 n 次 (first pointer = first pointer -> next)， 那這樣跑過 n 次後的 first pointer 只要再跑 size - n 次即可到 null， 因此我們可以用 first pointer 跑到 null 的同時更新 second pointer， 那麼 second pointer 屆時會指到要被刪除的 node， 不過這樣會有一個問題是，我們這樣會無法找到要被刪除的 node 之前一個， 因此這題的核心是需要搭配一個 dummy head， 藉由這個 dummy head 可以讓 second pointer 指向要被刪除的 node 之前一個， 此外這樣也能順帶完美解決刪除 head 的罕見情況 XD。 程式碼 class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead = new ListNode(0, head); ListNode* firstNode = dummyHead, * secondNode = dummyHead; for (int i = 0; i < n + 1; i++) firstNode = firstNode->next; while (firstNode != NULL) { firstNode = firstNode->next; secondNod

Leetcode 網址: https://leetcode.com/problems/n-queens/ 題目說明: 知名的 n 皇后問題，請找出 n 皇后的所有解。 解題說明: 使用 DFS 去窮舉出所有 n 皇后的解。 程式碼 class Solution { public: int flag[9] = {0}; vector<vector<string>> answers; bool isValid(vector<string>& board, int row, int col) { for (int i = 0; i < 9 && flag[i]; i++) { if (flag[i] == col) return false; if (flag[i] + i == row + col) return false; if (row - i == col - flag[i]) return false; } return true; } vector<vector<string>> solveNQueens(int n) { vector<string> board(n, string(n, '.')); dfs(board, 0, n); return answers; } void dfs(vector<string>& board, int row, int n) { if (row == n) { answers.push_back(board); return; } for (int i = 0; i < n; i++) { if (!isValid(board, row, i + 1)) continue;

Leetcode 網址: https://leetcode.com/problems/3sum-closest/ 題目說明: 給定 n 個整數與一個 target，請從這 n 個整數中找出 3 個數字 a, b, c 使得 a + b + c 最接近 target。 Note: 你可以假設這 n 個整數中只有唯一解。 解題說明: 這題只是 3sum 的變形，所以參考 3sum 的解法 即可解決此題。 程式碼 class Solution { public: int threeSumClosest(vector<int>& nums, int target) { int minDiff = INT_MAX; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); i++) { int left = i + 1, right = nums.size() - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; minDiff = abs(minDiff) > abs(target - sum) ? target - sum : minDiff; if (sum > target) right--; else if (sum < target) left++; else break; } } return target - minDiff; } }; 結果 Runtime:  8 ms , faster than  91.21%  of C++ online submissions for  3Sum Closest. Memory Usage:  9.8 MB , less

Leetcode 網址: https://leetcode.com/problems/3sum/ 題目說明: 給定 n 個整數，triplets 定義為 3 個整數 a, b, c 能夠使得 a + b + c = 0， 請找出所有唯一的 triplets。 Note: [a, b, c] 與 [a, c, b] 視為同一組 triplets 解題說明: 首先我們將問題縮小，如果給定一個數字 a 要如何找出另外二個整數 b, c 使得 a + b + c = 0 呢? 直覺想法是暴力法，也就是枚舉剩下的數字，那麼其時間複雜度為 O (n * n) 接著進一步研究發現，如果給定的是已經排序的數字，那麼我們找出 b, c 的時間複雜度只要 O(n)， 時間複雜度只要 O(n) 的原因是數字已經排序過，所以我們可以利用 two pointer 去逼近答案， 有了以上想法之後就可以實現算法了，最終的解法其時間複雜度為: O(n log n) + O(n * n) = O(n * n)。 程式碼 class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<int> answer(3); vector<vector<int>> answers; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; int left = i + 1, right = nums.size() - 1; answer[0] = nums[i]; while (left < right) { int sum = nums[left] + nums[right] + nums[i];

Leetcode 網址: https://leetcode.com/problems/container-with-most-water/ 題目說明: 給定 n 個非負整數的高度 (直線)，請找出這 n 個直線能形成的最大存水面積。 解題說明: 如果不管時間複雜度，暴力法就是直接枚舉出所有可能 O (n * n) 就能解決此問題， Submit 果然如預期會 TLE，接著我們可以透過最大面積去減少不必要的計算， 原因是計算面積時， height[i] 跟 height[j] 是取最小， 例如: 假設最大面積現在是 n， 我們可以發現寬度至少要大於最大面積 n / height[i]，因此可以跳過一些不必要的計算， 藉由這個方式即可成功解決此題。 不過這個解法的 result 竟然只有贏 5.26% 的程式， 因此開始思考有沒有 O (n) or O(n log n) 解，最後發現我們可以使用二個 pointer 來解決此問題， 假設我們一開始取二個點 (最左與最右)，如果要找出比這個二個更大的面積要怎麼做? 我們可以直覺地發現要移動這二個點中比較矮的 (原因是寬度變小高度不變，那面積絕對不可能變大)， 因此透過以上想法即可得到出 O(n) 解。 程式碼 class Solution { public: int maxArea(vector<int>& height) { // 1. two pointer int maxAreaOfWater = 0, left = 0, right = height.size() - 1; while (right > left) { maxAreaOfWater = max(maxAreaOfWater, min(height[left], height[right]) * (right - left)); if (height[left] > height[right]) right--; else if (height[left] < height[right]) left++; else left++, right--;

Leetcode 網址: https://leetcode.com/problems/longest-palindromic-substring/ 題目說明: 給定一個字串 s，請找出該字串 s 中最長的回文子字串。 Example 1: Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2: Input: s = "cbbd" Output: "bb" Example 3: Input: s = "a" Output: "a" Example 4: Input: s = "ac" Output: "a" 解題說明: 該題有很多種解法，這邊主要介紹二種我比較喜歡的解法: 第一種是 Dynamic Programming， 假設我們有一個字串 S(l, r) 要判斷是否為回文， 因為回文的特性，所以 S(l - 1, r + 1) 勢必也要是回文，否則 S(l, r) 絕對不是回文。 例如: S(2, 5) 是否為回文必須要 S[2] == S[5] 而且 S(3, 4) 也是回文， 而 S(3, 4) 是否為回文則必須要 S[3] == S[4] ，而且 S(4, 3) 代表 right 小於 left，故不需理會。 透過以上，我們即可寫出一個 DP 的程式來解決這個問題，其空間跟時間複雜度皆為 O(n * n)。 第二種解法則是 Expand Around Center， 我們可以知道最長回文的長度不是奇數就是偶數 (這不是廢話嗎 XD)， 假設長度是奇數，那代表最長回文的正中間是一個字元， 假設長度是偶數，那代表最長回文的正中間是二個字元， 所以我們從字串中找出所有正中間的字元 (時間複雜度為 O(n))， 並藉由正中間字元的往外擴散去找回文 (時間複雜度為 O(n))， 透過以上，我們即可以寫出一個不需要額外空間的解法，其時間複雜度為 O(n * n)。 程式碼 (DP) class Solution { public: string longestPa

Leetcode 網址: https://leetcode.com/problems/binary-tree-right-side-view/ 題目說明: 給定一個 Binary Tree，請由 Top 至 Bottom 出每一層中最右邊 Node 的值。 解題說明: 題目很清楚，就是一題 Level Order Traversal 的題目，所以直接用 queue 處理即可。 程式碼 class Solution { public: vector<int> rightSideView(TreeNode* root) { vector<int> ans; queue<TreeNode*> q; if (root) q.push(root); while (q.size() > 0) { TreeNode* rightNode = NULL; for (int i = 0, size = q.size(); i < size; i++, q.pop()) { rightNode = q.front(); if (rightNode->left) q.push(rightNode->left); if (rightNode->right) q.push(rightNode->right); } if (rightNode) ans.push_back(rightNode->val); } return ans; } }; 結果 Runtime:  0 ms , faster than  100.00%  of C++ online submissions for  Binary Tree Right Side View. Memory Usage:  11.8 MB , less than  29.31%  of C++ online submissions for  Bina

Leetcode 網址: https://leetcode.com/problems/insertion-sort-list/ 題目說明: 給定一個 Linked List，請使用 Insertion Sort 將這個 List 由小到大排序。 Example 1: Input: 4->2->1->3 Output: 1->2->3->4 程式碼 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* insertionSortList(ListNode* head) { auto dummyHead = new ListNode(INT_MIN, head); auto currentNode = dummyHead->next; while (currentNode != NULL) { auto nextNode = currentNode->next; for (auto n = dummyHead; n->next != currentNode; n = n->next) { auto tempNode = n->next; if (currentNode->val < tempNode->val) { n->next = currentNode; curr

Leetcode 網址: https://leetcode.com/problems/rotate-array/ 題目說明: 給定一個長度為 n 的序列，往右旋轉 k 次 (k 保證為非負整數)，請給出向右旋轉 k 次後的序列 Follow up: O(1) extra space Example 1: Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4] 解題說明: 如果不知道何謂向右旋轉的話可以先從範例1中了解向右旋轉的定義， 接著我直覺的想法是，直接先把 k 個數字 swap 到最前面，接著在處理剩下的序列即可， 以範例 1 為例即是， [1, 2, 3, 4, 5, 6, 7] => [5, 6, 7, 4, 1, 2, 3]， 觀察剩下的序列可以發現，[4, 1, 2, 3] 又是往右旋轉 k 次的問題， 因此寫出遞迴即可解決此問題。 程式碼 class Solution { public: void rotate(int* nums, int size, int k) { k = k % size; for (int i = 0; i < k; i++) swap(nums[i], nums[size - k + i]); if (k > 0) rotate(nums + k, size - k, k); } void rotate(vector<int>& nums, int k) { rotate(&nums[0], nums.size(), k); } }; 結果 Runtime:  0 ms , faster than  100.00%  of C++ online submissions for  Rotate Array. Me

C++ 11 中新增了二個處理 lock 的 wrapper，分別是 std::lock_guard 以及 std::unique_lock， 我們首先來看 C++ 11 對 std::lock_guard 的實作:  template<class _Mutex> class lock_guard<_Mutex> { // specialization for a single mutex public: typedef _Mutex mutex_type; explicit lock_guard(_Mutex& _Mtx) : _MyMutex(_Mtx) { // construct and lock _MyMutex.lock(); } lock_guard(_Mutex& _Mtx, adopt_lock_t) : _MyMutex(_Mtx) { // construct but don't lock } ~lock_guard() _NOEXCEPT { // unlock _MyMutex.unlock(); } lock_guard(const lock_guard&) = delete; lock_guard& operator=(const lock_guard&) = delete; private: _Mutex& _MyMutex; }; 從程式碼中，可以看到其主要就是在建構子中上鎖，並於解構子中解鎖， 因此 lock_guard 是一個非常輕量的 wrapper，只提供於 block 自動上鎖與解鎖 (避免開發者忘記)  接著我們再來看 std::unique_lock，根據 cppreference 的描述: The class unique_lock is a general-purpose mutex ownership wrapper allowing deferred locking, time-constrained attempts at locking, recursive locking, transfer of lock ownership, and u

Leetcode 網址: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/ 題目說明: 給定一個長度為 n 的序列，序列內的第 i 個數字代表第 i 天股票 A 的價格， 投資人被允許這 n 天內最多執行 2 次完成的交易 (買進 + 賣出算一次完整的交易)， 請設計一個演算法找出最大的獲利。 Note: 交易所限制買進時，手上必須沒有股票。 Example 1: Input: prices = [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3. Example 2: Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again. 解題說明: 遇到這種題目一開始沒有想法的話就先將 input 變小， 例如思考長度為 n 的序列之最大獲利要如何從 n - 1 中的序列推出呢 ? 思考了之後可以發現長度為 n 的序列之最大獲利可以分成二個情況: 1. 最大獲利的交易是否包含第 n 天 ? 如果不包含那答案就跟 n - 1 序列的最大獲利相同 2. 最大的獲利交易包含第 n 天，那麼我們就從 n - 1 的序列中找出最便宜的價格買進，並於第 n 天賣出 有以上的想法就可以把這想法寫成演算法囉 ~ 程式碼 class Solution { pu

Leetcode 網址: https://leetcode.com/problems/edit-distance/ 題目說明: 給定二個字串 word1 以及 word2，請找出最少需要幾個操作才能將將 word1 轉換成 word2。 操作的定義有三種:    1. 新增字元 2. 刪除字元 3. 取代字元 Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') 解題說明: 遇到這種題目一開始沒有想法的話就先將 input 變小， 以範例 1 的而言，我們慢慢將 input 由小至大就可以推論出下表: 最後根據上表及推導中可以發現這題是個 Dynamic Programming 題型， 將推導的結果寫成演算法即可解決此題。 程式碼 class Solution { public: int minDistance(string word1, string word2) { int dp[word1.length() + 1][word2.length() + 1]; memset(&dp[0][0], 0, (word1.length() + 1) * (word2.length() + 1) * sizeof(int)); for (int i = 1; i <= word1.length(); i++) dp[i][0] = i; for (int i = 1; i <= word2.length(); i++) dp[0][i] = i; for (int i = 1; i <= word1.length(); i++) { for (int j = 1; j <= word2.length(); j++)

Leetcode 網址: https://leetcode.com/problems/minimum-window-substring/ 題目說明: 給定一個字串 s 以及一個字串序列 t， 請在字串 s 中找出包含所有 t 出現的字元所需要的最短字串長度。 備註: 題目保證最短字串長度會是 unique 的。 Example 1: Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Example 2: Input: s = "a", t = "a" Output: "a" 解題說明: 觀察題目敘述很直覺可以發現是 Sliding Window 的題目， 我們觀察 Example 看如何先找出單一個包含字串 t 的答案 (先不管最短) ~ 1. 訪問 A 發現 A 是需要的字元，由於是第一個出現的需要字元所以 start 紀錄成 0；需要字元剩餘 2 2. 訪問 D 發現 D 不是需要的字元，繼續往下走；需要字元剩餘 2 3. 訪問 O 發現 O 不是需要的字元，繼續往下走；需要字元剩餘 2 4.  訪問 B 發現 B 是需要的字元，由於還欠缺其他字元所以繼續往下走；需要字元剩餘 1 5. 訪問 E 發現 E 不是需要的字元，繼續往下走；需要字元剩餘 1 6. 訪問 C 發現 C 是需要的字元，找到所有字元所以記錄這個答案 ADOBEC 以上是找出非最短的算法，接著我們要思考如何從這組算法找出下一組答案 ~ 很直覺可以發現若找出一組比 ADOBEC 更短的答案，那勢必得捨去 A (也就是移除字串 ADO)， 所以捨去 ADO 之後將 Start 設成下一個需要的字元 B (index = 3)， 又由於我們只有捨棄 A，所以只要從 C 開始往後找找出下一個 A 就會是下一組可能更短的答案， 將以上的想法寫成 for loop 並判斷長度就可以找出答案了。 程式碼 class Solution { public: string minWindow(string s, string t) { int minStart = 0, minLength = 0;

Leetcode 網址: https://leetcode.com/problems/sliding-window-maximum/ 題目說明: 給定一個沒有排列長度為 n 的陣列與窗口大小 k ( 1 <=k <= n)， 每次窗口會往右移動一格，直到窗口大小超出陣列長度， 請找出移動過程中窗口範圍內的最大值。 解題說明: 這題最暴力法直接做就是每次從大小為 k 窗口中找最大元素， 由於 n 可能等於 n / 2，所以暴力法的時間複雜度為 O (n^2)。 接著再來思考比較好的做法就是 Max Heap， Max Heap 插入跟刪除的時間複雜度皆為 O (log n)， 由於插入跟刪除最多為 n 次，所以其時間複雜度可以壓到 O (n log n) ~ 後來解完題目後，看了下討論區有種 O (n) 的解法是用 double-ended queue， 其算法概念是每次新增元素到 queue 前，把那些沒有用的元素先 pop 掉， 例如: 4 3 2 1 7 來說，當我們要新增 7 的時候就把前面的 pop 掉， 原因是往右邊移動的話， 4 3 2 1 這幾個數字絕對不可能是最大值， 所以有以上想法後就可以解決此題啦! 程式碼 (Max Heap) class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> result; priority_queue<pair<int, int>> pq; for (int i = 0; i < nums.size(); i++) { while (i >= k && pq.size() > 0 && i - k >= pq.top().second) pq.pop(); pq.push(pair(nums[i], i)); if (i >= k - 1) result.push_back(pq.top().first);

Leetcode 網址: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/ 題目說明: 這題跟 153 一樣差別在於 153 保證不會有重複的元素，但 154 可能有重複的元素。 解題說明: 由於是否重複對於我們 153 的解法並無影響，所以直接套用 153 的程式即可解決此題。 程式碼 class Solution { public: int findMin(vector<int>& nums) { for (int i = 0, maxNum = INT_MIN; i < nums.size(); i++) { if (nums[i] >= maxNum) maxNum = nums[i]; else return nums[i]; } return nums[0]; } }; 結果 Runtime:  4 ms , faster than  98.88%  of C++ online submissions for  Find Minimum in Rotated Sorted Array II. Memory Usage:  12.2 MB , less than  96.69%  of C++ online submissions for  Find Minimum in Rotated Sorted Array II.

Leetcode 網址: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/ 題目說明: 給一個長度為 n 的已排序並 rotate 過 1 ~ n 次的陣列，請找出這個陣列中最小的數值。 Rotate 範例: 原始已排序陣列: [0,1,2,4,5,6,7] 經過 1 次 rotate => [7,0,1,2,3,4,5,6] 經過 2 次 rotate => [6,7,0,1,2,3,4,5] 經過 3 次 rotate => [5,6,7,0,1,2,3,4] ... 經過 7 次 rotate => [0,1,2,3,4,5,6,7] Example 1: Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times. Example 2: Input: nums = [4,5,6,7,0,1,2] Output: 0 Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times. Example 3: Input: nums = [11,13,15,17] Output: 11 Explanation: The original array was [11,13,15,17] and it was rotated 4 times.   解題說明: 觀察範例可以發現， rotate 1 次代表第 1 ~ 1 個元素會為第 n 大到第 n 大，第 2 個元素為最小 rotate 2 次代表第 1 ~ 2 個元素會為第 n - 1 大到第 n 大，第 3 個元素為最小 rotate 3 次代表第 1 ~ 3 個元素會為第 n - 2 大到第 n 大，第 4 個元素為最小 ... rotate n 次代表第 1 ~ n 個元素會為第 1 大到第 n 大，第 n 個元素為最小 以此邏輯即可以寫出非常簡單的算法囉 ~ 程式碼 class Solution { public: int findM