AMGE’s Blogger

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....

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.3...

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 submissio...

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 f...

Leetcode 網址: https://leetcode.com/problems/longest-consecutive-sequence/ 題目說明: 給定一個沒有排列的陣列，找出最長的連續序列長度。 Follow up: 你能否在 O(n) 時間內完成呢? Example 1: Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4] . Therefore its length is 4. Example 2: Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9   解題說明: 由於題目要求的是 O(n) 時間，也就是說可以直接捨棄排序法了， 因為比較排序的排序法時間複雜度為 O( n log n) ~ 所以很直覺出題者應該是想要我們使用額外的空間來處理問題。 所以我們直接把 nums 轉成 unordered_map， 以範例 1 而言就是 m[100] = 1, m[4] = 1, m[200] = 1, ..., m[2] = 1， 由於 unordered_map 訪問的平均時間為 O(1)，所以轉換過成只需要 O(n)， 接著直接對這些 map 中存在的元素做 traverse 紀錄長度，就可以找出答案了 ~ 程式碼 class Solution { public: int traverse(unordered_map<int, int>& m, int index, int offset, int value) { if (m.find(index + offset) != m.end()) { m[index + offset] = traverse(m, index + offset, offset, value + 1); return m[index + offset]; } return value; } int longestConsecutive(vector...