EX:
n = 3,
[
"((()))", "(()())", "(())()", "()(())", "()()()" ]
2020年6月26日 星期五
LeetCode 22. Generate Parentheses [Medium] [C++] 解題筆記
這題給定 n 組括弧，要我們求出 n 組括弧所能形成的所有合法組合。
2020年6月23日 星期二
LeetCode 21. Merge Two Sorted Lists [Easy] [C++] 解題筆記
這題給定兩個排序好的 Linked List，要我們將兩個 list 拼接成一個排序好的 list。
EX:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
LeetCode 20. Valid Parentheses [Easy] [C++] 解題筆記
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
EX:
Input: "()[]{}"
Output: true
Input: "([)]"Output: false
LeetCode 19. Remove Nth Node From End of List [Medium] [C++] 解題筆記
Given a linked list, remove the n-th node from the end of list and return its head.
EX:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
2020年6月22日 星期一
LeetCode 17. Letter Combinations of a Phone Number [Medium] [C++] 解題筆記
給定一個由 2-9組成的字串 s，其中 2-9 分別可以對應到幾個特定字母如下圖:
題目要求我們找出 s 可以對應到的所有字母組合。
EX:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].2020年6月21日 星期日
LeetCode 18. 4Sum [Medium] [C++] 解題筆記
這題給定一個 array，和一個 target value，要我們在其中找出四個數字且其和為 target value 的所有
組合。並要求不可以有重複的解。
EX:
nums = [1, 0, -1, 0, -2, 2] , target = 0.
Ans: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
LeetCode 16. 3Sum Closest [Medium] [C++] 解題筆記
這題給定一個 array 和一個 target value，要我們在 array 中找三個數其和最接近 target value。並且題目保證只有唯一一組解。
EX:
nums = [-1,2,1,-4], target = 1
Ans: 2, Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
LeetCode 15. 3Sum [Medium] [C++] 解題筆記
這題給定一個 array，要我們在其中找出三個數字且其和為 0 的所有組合。
EX:
nums = [-1, 0, 1, 2, -1, -4]
[Ans: [-1, 0, 1], [-1, -1, 2] ]
2020年6月20日 星期六
LeetCode 14. Longest Common Prefix [Easy] [C++] 解題筆記
這題給我們一些字串，要我們找出這些字串的最長 prefix string。
EX:
Input: ["flower","flow","flight"]
Output: "fl" Input: ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.
LeetCode 13. Roman to Integer [Easy] [C++] 解題筆記
這題題目太冗了，可以直接參考 LeetCode 13. Roman to Integer。簡而言之就是給我們一個羅馬數字表示的字串，要我們轉換成對應的整數值。
Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000
EX:
Input: "III" Output: 3
Input: "IV" Output: 4
Input: "IX" Output: 9
Input: "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3.
Input: "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
LeetCode 11. Container With Most Water [Medium] [C++] 解題筆記
這題題目解釋太複雜，直接看下圖，簡而言之，這題要我們找兩條 bar 其組成的容器容積最大。
EX:
Input: [1,8,6,2,5,4,8,3,7] Output: 49
LeetCode 10. Regular Expression Matching [Hard] [C++] 解題筆記
這題給定一個 string (s) 與一個 pattern (p) ，要求我們實作支援 ' . ' 與 ' * ' 操作的正規表示法。
'.' Matches any single character. '*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
scould be empty and contains only lowercase lettersa-z.pcould be empty and contains only lowercase lettersa-z, and characters like.or*.
2020年6月18日 星期四
LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal [Medium] [C++] 解題筆記
這題給我們一個 binary tree 的中序和前序排序，要我們反推出整個 tree 的結構，其中 tree 的每個node 皆不重複。
EX:
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]3 / \ Ans: 9 20 / \ 15 7
2020年6月17日 星期三
LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal [Medium] [C++] 解題筆記
這題給我們一個 binary tree 的中序和後序排序，要我們反推出整個 tree 的結構，其中 tree 的每個node 皆不重複。
EX:
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]Ans: 3
/ \ 9 20 / \ 15 7
LeetCode 9. Palindrome Number [Easy] [C++] 解題筆記
這題要我們判斷一個整數是否是回文。
EX:
Input: 121
Output: trueInput: -121 Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
LeetCode 8. String to Integer (atoi) [Medium] [C++] 解題筆記
這題要我們實作一個將 string 換成 integer 的函數，類似 atoi 的功能。
EX:
Input: " -42"
Output: -42 Explanation: The first non-whitespace character is '-', which is the minus sign. Then take as many numerical digits as possible, which gets 42.
2020年6月16日 星期二
LeetCode 7. Reverse Integer [Easy] [C++] 解題筆記
題目: Given a 32-bit signed integer x , reverse digits of an integer.
EX:
Input: 123 Output: 321
LeetCode 5. Longest Palindromic Substring [Medium] [C++] 解題筆記
這題給定一個字串 s ，要我們找到 s 的最長回文子串。
EX:
Input: "babad"
Output: "bab" Note: "aba" is also a valid answer.
2020年6月15日 星期一
LeetCode 4. Median of Two Sorted Arrays [Hard] [C++] 解題筆記
這題給定兩個排序好的 array nums1 和 nums2，其長度分別為 m, n，要求我們在 O(log(m+n)) 的時間複雜度限制內找出這兩個 array 合併後的中位數。
EX:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
2020年6月14日 星期日
LeetCode 99. Recover Binary Search Tree [Hard] [C++] 解題筆記
這題給我們一個錯的 binary tree (tree 的某兩個 node 被交換了導致該 tree 不符合 binary tree 的性質)，要求我們修正這個 tree 並不改變其結構。
EX:
Input: [3,1,4,null,null,2]
3 / \ 1 4 / 2 Output: [2,1,4,null,null,3] 2 / \ 1 4 / 3
Morris Traversal [Algorithm] 演算法筆記
問題:
Morris Traversal 主要解決的是 binary tree traversal 的問題，講到 binary tree traversal，一般人直覺就會想到可以做 preorder, inorder, postorder traversal 求解，但是上述方法一般的實作方式(recursive or iterative + stack) 其 空間複雜度皆為 O(n)，原因是我們必須要紀錄尚未走訪的 node，例如在 inorder traversal 中，我們先照著 左子樹-> root ->右子樹的順序遍歷，如果不用 stack 紀錄 root，當我們走訪完左子樹之後就無法回到 root 繼續走訪。那要怎摸在不使用 stack (額外空間) 的情況下完成 traversal 呢？ Morris Traversal 正是為此而生，它可以在 O(1) space 情況下同樣達到 O(n) 時間複雜度完成 traversal。
2020年6月13日 星期六
LeetCode 100. Same Tree [Easy] [C++] 解題筆記
給我們兩個 binary tree，要我們判斷兩者是不是一樣的。
EX:
Input: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
Output: false
LeetCode 98. Validate Binary Search Tree [Medium] [C++] 解題筆記
這題要我們判斷一個 binary tree 是不是 binary search tree。
EX:
5
/ \ 1 4 / \ 3 6 Input: [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.
LeetCode 95. Unique Binary Search Trees II [Medium] [C++] 解題筆記
這題給我們一個數字 n 要我們列舉出所有 1 ... n 的數可以形成的 unique binary search tree.
EX:
Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3LeetCode 96. Unique Binary Search Trees [Medium] [C++] 解題筆記
這題要我們求數字 1~n 可以形成的 unique binary tree 的個數。
EX:
Input: 3
Output: 5
Explanation: Given n = 3, there are a total of 5 unique BST's: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
LeetCode 94. Binary Tree Inorder Traversal [Medium] [C++] 解題筆記
這題要我們找一個 Tree 的中序排序。
EX:
Input: [1,null,2,3]
1 \ 2 / 3 Output: [1,3,2]
LeetCode 93. Restore IP Addresses [Medium] [C++] 解題筆記
這題給定一個只由數字組成的 string s，要我們求 s 可能形成的所有合法的 IP address。
EX:
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]2020年6月12日 星期五
LeetCode 206. Reverse Linked List [Easy] [C++] 解題筆記
這題要求我們反轉一個 Single Linked List.
EX:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULLLeetCode 91. Decode Ways [Medium] [C++] 解題筆記
這題給定一個都是數字的非空字串 s，每個數字可以對應到一個 A~Z 的字母，要我們求共有多少種解碼方式。
EX:
'A' -> 1
'B' -> 2 ... 'Z' -> 26input:
"226"
Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
LeetCode 90. Subsets II [Medium] [C++] 解題筆記
這題算是 78. Subsets 的延伸題，一樣給定一個 array，其中數字可能重複，要我們求 array 中所有數字可以組成的不重複子集。
EX:
Input: [1,2,2]
Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
2020年6月10日 星期三
LeetCode 88. Merge Sorted Array [Easy] [C++] 解題筆記
這題給定兩個在第 m 與第 n 個元素前已經排序好的陣列 nums1, nums2，要我們將兩個陣列合併到 nums1 中並排序好。(nums1 保證有足夠的空間存放 m + n)。
EX:
nums1 = [4, 5, 6, 0, 0, 0]
nums2 = [1, 2, 3]
Ans: nums1 = [1, 2, 3, 4, 5, 6]
LeetCode 87. Scramble String [Hard] [C++] 解題筆記
這題給定兩個長度相等的的字串 s1, s2，要我們判斷 s1 是不是 s2 的 scrambled string，所謂 scrambled string 是指說將 string 用 binary tree 的方式切割，若透過 swap 某些 non-leaf node 的兩個子節點的位置可以使 s1 變成 s2 的話就說 s1 is a scrambled string of s2.
EX:
s1:
great / \ gr eat / \ / \ g r e at / \ a t
s2:
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a tAns: True, 可以透過交換 s1 中 gr 的兩個子節點來將 s1 轉成 s2。
LeetCode 97. Interleaving String [Hard] [C++] 解題筆記
這題給定三個字串 s1 , s2 , s3，要我們判斷 s3 是否可由 s1, s2 "交錯" 組合出來。
EX:
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Ans: True
2020年6月9日 星期二
LeetCode 3. Longest Substring Without Repeating Characters [Medium] [C++] 解題筆記
這題給定一個字串，要我們找出字元不重複的最常子串(longest substring)的長度。
EX:
Input: "abcabcbb"
Ans: 3
LeetCode 2. Add Two Numbers [Medium] [C++] 解題筆記
這題給我們兩個 Linked List，並保證最後一個 node 值都不為 0，要求我們將兩個 list 的reverse order 當成兩個數字相加。
EX:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8 , 342 + 465 = 807LeetCode 1. Two Sum [Easy] [C++] 解題筆記
LeetCode 第一題一定要寫一下拉，這題給定一個 array 與一個 target value 要求我們從 array 中找到兩個數字和為 target，並保證一定且唯一存在一個解 。
EX:
nums = [2, 7, 11, 15], target = 9
Ans: [0, 1] , nums[0] + nums[1] = 9
2020年6月7日 星期日
LeetCode 85. Maximal Rectangle [Hard] [C++] 解題筆記
這題給定一個 2D array ，裡面只包含 "1" 或 "0" ，要我們求由 "1" 組成的最大矩形面積。
EX:
[
["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ]
Ans: 6
2020年6月6日 星期六
LeetCode 83. Remove Duplicates from Sorted List [Easy] [C++] 解題筆記
這題給定一個 Linked List ，要求我們刪除裡面重複出現的數字。
EX:
Input: 1->1->2->3->3
Ans: 1->2->3想法:
這雖然是一題 easy 的題目，但還蠻有意思的很值得練習，雖然要寫出來不難，但要寫得
簡潔也是需要一定程度的練習，尤其對指標的理解需要夠清晰。
LeetCode 79. Word Search [Medium] [C++] 解題筆記
這題定一個二維陣列，每個位置包含一個字母，並給一個 target string word，要求檢查在 array 中的字母往左右或是上下相連是否可以組成 word。
EX:
board =
[ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ]
word = "ABCCED", return true.
LeetCode 86. Partition List [Medium] [C++] 解題筆記
這題給定一個 Linked List 與一個 target value x，要求我們把 list 中小於 x 的 node 都排到大於等於 x的 node 前面去，小於 x 與大於等於 x 的 node 之間的相對順序要維持原樣。
EX:
head = 1->4->3->2->5->2, x = 3
Ans: 1->2->2->4->3->5
LeetCode 78. Subsets [Medium] [C++] 解題筆記
這題給定一個 array，其中所有數字不重複，要我們求 array 中所有數字可以組成的不重複子集。
EX:
nums = [1,2,3]
Ans: [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
LeetCode 77. Combinations [Medium] [C++] 解題筆記
這題是基本的組合題目，一定要會！
題目很簡單就是給你兩個數 n 與 k 要你求 n 取 k 的所有組合 C(n, k) 。
EX:
n = 5, k = 4
Ans: [ [[1,2,3,4],[1,2,3,5],[1,2,4,5],[1,3,4,5],[2,3,4,5]] ]
2020年6月5日 星期五
LeetCode 81. Search in Rotated Sorted Array II [Medium] [C++] 解題筆記
這題是 33. Search in Rotated Sorted Array 的 follow up，一樣給定一個 array ，這個 array 是排序好的但是不是從頭開始排序，而是從某個 index 開始排序，但 array 中的數字可能重複，要求我們在此 array 中搜索特定數字。
EX:
nums = [1,1,3,1], target = 3
Ans: true
2020年6月2日 星期二
LeetCode 33. Search in Rotated Sorted Array [Medium] [C++] 解題筆記
這題給定一個 array ，這個 array 是排序好的但是不是從頭開始排序，而是從某個 index 開始排序，且 array 中的數字不重複，要求我們在此 array 中搜索特定數字。
EX:
nums = [
4,5,6,7,0,1,2], target = 0Ans: 4
訂閱：
文章 (Atom)