題目： LeetCode - 19. Remove Nth Node From End of List 題目說明給一個 List 和一個整數 n，要求刪除 List 的倒數第 n 個 node。 解題思路若想刪除倒數第 n 個 node，就需要倒數第 n + 1 個 node，可以使用兩個指針，先使兩個指針相隔 n + 1 個 node，之後兩者都往前走，直到前面的指針走到尾巴，此時後面的指針恰好為倒數第 n + 1 個 node，此時作串接及刪除的動作即可。 參考解法1234567891011121314class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode dummy(0, head); auto first = head, second = &dummy; for(int i = 0; i < n; ++i) first = first->next; whi ...

題目： LeetCode - 17. Letter Combinations of a Phone Number 題目說明給一個只包含數字的字串，表示按下手機鍵盤的號碼及順序，求所有可能出現的字串。 解題思路先依照鍵盤及數字建表，之後使用 DFS 列出所有有可能的組合即可。 參考解法1234567891011121314151617class Solution {public: vector<string> letterCombinations(string digits) { if(digits.empty()) return {}; vector<vector<char>> dict = {{'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', ...

題目： LeetCode - 4. Median of Two Sorted Arrays 題目說明給兩個由小到大排序的陣列，求兩陣列結合後的中位數。 解題思路透過 Merge Sort 將兩個陣列結合，之後找出中位數即可。 參考解法12345678910111213141516171819202122232425262728293031// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int n = nums1.size() + nums2.size() ...

題目： LeetCode - 1305. All Elements in Two Binary Search Trees 題目說明給兩個 Binary Search Tree，回傳一個包含兩個樹的所有值並且以小到大排序後的陣列。 解題思路由於 BST 的特性，我們可以先取 root 的左子樹，再取 root->val，最後取 root 的右子樹即可得到一個含有 BST 的所有值並排序後的陣列。對於本題來說，我們先取得兩個排序後的陣列，最後使用 Merge Sort 將兩個陣列合併即可得到最後的陣列。 參考解法123456789101112131415161718192021222324252627282930313233343536373839static auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {publ ...

題目： LeetCode - 763. Partition Labels 題目說明給一個只包含小寫英文字母的字串 S，求依照題目的要求分割的子串的長度。題目要求子串中若出現某個字母，則此子串須包含字串中的所有此字母，並且需切割出最多的子串。 解題思路使用一個陣列紀錄每個字母最後出現的 index，定義兩個整數 l, r，接著遍歷字串，r 每次更新為 r 及 lastIdx[S[i] - 'a'] 兩者的最大值，這樣可以確保此子串能包含所有出現過的字母，若是 i == r 表示已經可以切割了，長度及為 r - l + 1，接著更新 l 即可。 參考解法1234567891011121314class Solution {public: vector<int> partitionLabels(string S) { int n = S.size(), l = 0, r = 0; vector<int> v, lastIdx(26); for(int i = 0; i < n; ...

題目： LeetCode - 15. 3Sum 題目說明給一個陣列，求此陣列中所有三個元素值相加為 0 的組合。 解題思路為了增加效率，先對陣列進行排序，接著遍歷陣列，先選定一個最左邊的數字，接著往右找是否存在相加為此數的相反數的組合，若存在代表找到一組，接著檢查 l 的右邊及 r 的左邊的數是否相同，避免找到重複的組合。同時再過程中若是 nums[i] > 0 就可以不用再找了，因為我們是選定最左邊的數，且我們的陣列是排序過的，所以右邊不可能會有相加為此數的相反數的組合，同時要避免重複運算，所以若 nums[i] == nums[i - 1] 則直接 continue。 參考解法1234567891011121314151617181920212223242526272829303132333435363738// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); ...

題目： LeetCode - 459. Repeated Substring Pattern 題目說明給一個字串 s，求 s 是否為某個子串的數倍串接組成。 解題思路如果 s 滿足題目的條件，那麼將字串複製一次後，去除頭跟尾，一定能找到原本的字串。 參考解法123456789101112// fast IOstatic auto __ = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0;}();class Solution {public: bool repeatedSubstringPattern(string s) { return (s + s).find(s, 1) != s.size(); }};

題目： LeetCode - 220. Contains Duplicate III 題目說明給一個陣列，求對於陣列中的某個元素的左右各 k 個元素中是否存在兩者的差小於等於 t 的元素。 解題思路為了計算方便，我們先確定 j 的位置，之後再往前找 i，最簡單的方法為兩個迴圈，但是這樣會超時，所以必須使用二分搜尋，這裡我們使用 lower_bound() 這個函式達成二分搜尋的效果，使用 Multiset 紀錄前面 k 個元素，之後使用此函式找到第一個大於等於 nums[j] - t 的值，若有找到並且這個值會小於等於 nums[j] + t，表示兩者的差會小於等於 t，回傳 True。 參考解法123456789101112131415class Solution {public: bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { multiset<long> ms; for(int j = 0; j ...

題目： LeetCode - 949. Largest Time for Given Digits 題目說明給一個大小為 4 的陣列，求此陣列中的數字能組出的最大的 24 小時制的時間。 解題思路先將陣列由小到大排序，之後使用能組出全排列的函數 next_permutation() 將每種組合都嘗試一次即可。 參考解法1234567891011121314class Solution {public: string largestTimeFromDigits(vector<int>& A) { string str; sort(A.begin(), A.end()); do { int hour = A[0] * 10 + A[1], minute = A[2] * 10 + A[3]; if(!(hour < 24 && minute < 60)) continue; str ...

題目： LeetCode - 450. Delete Node in a BST 題目說明給一個 Binary Search Tree，和一個整數 key，如果找到 key 的節點就將其刪除。 解題思路由於 BST 有左子樹的值皆比根的值小，右子樹的值皆比根的值大的特性，所以我們先判斷當前 node 的值及 key 的大小，若 key 較大則往左邊走，否則往右邊走。若兩者的值相等代表要刪除當前的 node，若是當前的 node 只有一邊的子樹，那就直接接上即可，否則要從右子樹中找出最小的值頂替目前的 node 才能符合 BST 的特性。 參考解法12345678910111213141516171819202122232425class Solution {public: TreeNode* deleteNode(TreeNode* root, int key) { if(!root) return root; if(root->val < key) root->right = deleteNode(root- ...