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