AMGE’s Blogger

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