Leetcodes

題目連結：17. Letter Combinations of a Phone Number 我覺得這種 backtracking 或是 dfs 的題目都需要想清處 depth 的定義是什麼，想清楚就會好寫許多。 程式實做 class Solution { public: vector<string> letterCombinations(string digits) { if (digits.size() == 0) return {}; vector<string> phoneNumber = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; vector<string> combs; string current; backtracking(0, digits, current, phoneNumber, combs); return combs; } void backtracking(int index, string digits, string current, vector<string> phoneNumber, vector<string> &combs) { if (index >= digits.size()) { combs.push_back(current); return; } int i = digits[index] - '0'; for (char c : phoneNumber[i]) { current.push_back(c); backtracking(index + 1, digits, current, phoneNumber, combs); current.pop_back(); } } };

題目連結：206. Reverse Linked List 解題思路 這題還蠻直接的，把 Linked List 給掃過一遍，並且一個一個的把指標顛倒過來。 剛開始的時候我用了這個寫法： class Solution { public: ListNode* reverseList(ListNode* head) { if (!head) return head; ListNode *slow = head; ListNode *fast = head->next; while (fast != nullptr) { ListNode *nextNode = fast->next; fast->next = slow; slow = fast; fast = nextNode; } slow->next = nullptr; return slow; } }; 但這個寫法是錯誤的，因為 slow 從 head 開始的話，最一開始的 head 沒有指向 nullptr，所以需要把 slow 從 nullptr 開始會比較好。 我學到的是面對到 Edge Case 時，要特別小心注意才行。 程式碼 /** * 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* reverseList(ListNode* head) { ListNode *slow = nullptr; ListNode *fast = head; while (fast != nullptr) { ListNode *nextNode = fast->next; fast->next = slow; slow = fast; fast = nextNode; } return slow; } };

題目連結：136. Single Number 解題思路 這題是一個蠻神奇蠻剛好的一題，同時使用了 xor 與「出現兩次」這兩個元素，因為 同一個數字 xor 在一起會變成 0 這題就用這樣的特性解決 程式碼 class Solution { public: int singleNumber(vector<int>& nums) { int n = 0; for (int num : nums) n ^= num; return n; } };

題目連結：746. Min Cost Climbing Stairs 解題思路 這題利用 DP 的方式，「有了前兩天的資訊可以推測出今天」依此類推的得知最後的答案。 程式碼 class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); vector<int> dp(n, 0); dp[0] = cost[0]; dp[1] = cost[1]; for (int i = 2; i < n; i++) dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]; return min(dp[n - 1], dp[n - 2]); } };

題目連結：1004. Max Consecutive Ones III 解題思路 這題使用兩個 pointer left 與 right 來紀錄當前的 array 大小，像是： 0 1 2 3 4 5 6 7 8 9 ↑ ↑ l r 這個時候 left == 2, right == 6 長度的計算為 length = right - left + 1 也就是 6 - 2 + 1 == 5 如何表達 length == 0 這樣的設計會碰到的下一個問題是 假設 right == 6 如何表達 length == 0 的情況?? 會像是下面這個樣子： 0 1 2 3 4 5 6 7 8 9 ↑ ↑ r l 雖然是 left 不過卻在 right 的右邊，但這樣做的好處就在於我們計算長度的公式： ...

題目連結：1679. Max Number of K-Sum Pairs 解題思路 這一題跟 11. Container With Most Water 的感覺還蠻像的，都是先把兩的 pointer 放在兩端，並且根據不同的情況，用 greedy 的方式判斷下一步要做什麼。還有這個問題是配對到了就刪除掉，所以也不會有重複的問題。 程式碼 class Solution { public: int maxOperations(vector<int>& nums, int k) { int left = 0; int right = nums.size() - 1; int count = 0; sort(nums.begin(), nums.end()); while (left < right) { if (nums[left] + nums[right] == k) { count++; left++; right--; } else if (nums[left] + nums[right] < k) { left++; } else { right--; } } return count; } };

題目連結：345. Reverse Vowels of a String 解題思路 這題就很直覺得掃過兩遍，第一遍收集 Vowels，第二變把 Vowels 用相反的順序放回去，真有什麼好說的東西的話應該是寫個 helper function isVowels() 會方便一些。 程式碼 class Solution { private: bool isVowels(char c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; if (c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U') return true; return false; } public: string reverseVowels(string s) { int n = s.size(); queue<char> q; for (int i = 0; i < n; i++) if (isVowels(s[i])) q.push(s[i]); for (int i = n - 1; i >= 0; i--) if (isVowels(s[i])) { s[i] = q.front(); q.pop(); } return s; } };

題目連結：334. Increasing Triplet Subsequence 解題思路 這題我剛開始是朝著先找出 i 與 k 之後再檢查 j 是否存在，想了幾遍都覺得有些瑕疵，後來發現依照 i, j, k 的順序尋找會比較合理一些，可以用很 greedy 的方式去尋找。 如果再來一次的話，我應該會先列出以下兩種可能： 先找出最大最小的 i 與 k, 再找出中間的 j 依照順序尋找 i, j, k 評估之後挑選較有可能的順序，並且保持另一個方案的可能性。 程式碼 class Solution { public: bool increasingTriplet(vector<int>& nums) { if (nums.size() < 3) return false; int i = 0; int j = -1; for (int l = 1; l < nums.size(); l++) { if (nums[l] < nums[i]) { i = l; } else if (j > 0 && nums[l] > nums[j]) { return true; } else if (nums[l] > nums[i]) { j = l; } } return false; } };