All in One LeetCode

#	Name	Difficulty	Note
1	Two Sum	Easy	HashMap 紀錄出現過的
2	Add Two Numbers	Medium	單純實作，注意進位與 head
3	Longest Substring Without Repeating Characters	Medium	HashMap 紀錄每個字元上次出現的位置，遇到重複的長度就從該字元上次出現的位置開始算。
4	Median of Two Sorted Arrays	Hard	可轉成binary search，設 median 為 k，每次在兩個array 中找第 k / 2 個數，將第 k / 2 較小的一邊的 1~k / 2 梯除掉(k 必不在其中)，直到兩者皆為空。
5	Longest Palindromic Substring	Medium	枚舉以每個字元為中心與每個字元與右邊相鄰字元為中心像左右兩邊展開。ex: "ababc", "a"-> "bab" -> "ababc"
6	ZigZag Conversion	Medium	感覺不是很值得寫，先不寫。
7	Reverse Integer	Easy	注意overflow！可用 214748364 (INT_MAX / 10) 來判斷累加的數字是否會溢位。
8	String to Integer (atoi)	Easy	繁瑣題，注意overflow , edge case ex: 0-1, +-2 ...之類的情況，沒啥特別技巧。
9	Palindrome Number	Easy	反轉數字後看兩者是否一樣，可用Reverse Integer的方法來反轉，若反轉過程中溢位則不可能是回文。
10	Regular Expression Matching	Hard	DP or recursive，將 '*' 匹配 0 , 1 , 多次分開討論。
11	Container With Most Water	Medium	Two Pointer，從兩端遍歷，每次高度較小的一邊往前移動。
12	Integer to Roman	Medium	太冗了，先不寫。
13	Roman to Integer	Easy	太冗了，沒啥意思，看看就好。
14	Longest Common Prefix	Easy	暴力法，逐個比較。
15	3Sum	Medium	Two pointer，先 sorting 然後固定一數後，就變成 2 sum 的問題。
16	3Sum Closest	Medium	與  3Sum 同做法。
17	Letter Combinations of a Phone Number	Medium	可以多寫寫看 iterative 的寫法。
18	4Sum	Medium	與 3Sum , 3Sum Closest 同作法，可以推廣到 nSum。
19	Remove Nth Node From End of List	Medium	Two Pointer, 概念: 找倒數第 n 個等價於找第 len - n + 1 個，因此可以讓 first pointer 先走 n - 1步，之後兩個同時走，等 first 走到底，second 剛好就走到第 len - (n - 1) = len - n + 1個。實際實作方便會多一個 dummy head 且為了方便刪除會找第 len - n + 1的前一個，因此實作時 first pointer 可以先走 n + 1步。
20	Valid Parentheses	Easy	Stack。左括號都放進去stack，遇到右括號就 pop (匹配)，不能匹配則為 invaild。
21	Merge Two Sorted Lists	Easy	實作題。
22	Generate Parentheses	Medium	DFS backtracking，若左括弧個數 < 右括弧個數即可剪枝。
23	Merge k Sorted Lists	Hard	Priority queue or merge sort method.
24	Swap Nodes in Pairs	Medium	實作題。可多練習
25	Reverse Nodes in k-Group	Hard	recursive 實作題。
26	Remove Duplicates from Sorted Array	Easy	遍歷，將不重複的元素覆蓋到 array 前方。
27	Remove Element	Easy	與Remove Duplicates from Sorted Array概念一樣。
28	Implement strStr()	Easy	暴力法。
29	Divide Two Integers	Medium	bitwise operation，每次 left shift  將 除數*2 來求解。
30	Substring with Concatenation of All Words	Hard	暴力法，HashMap 紀錄word出現次數。
31	Next Permutation	Medium	需多看，不是非常容易想到。
32	Longest Valid Parentheses	Hard	stack or Two pointer。
33	Search in Rotated Sorted Array	Medium	如果 nums[mid] < nums[right] 表示 mid ~ right 是 sorted，反之 表示 left ~ mid 是 sorted，每次在 sorted 的一邊進行 binary search。
34	Find First and Last Position of Element in Sorted Array	Medium	Binary search，可以用 STL 裡的 lower_bound 和 upper_bound實作。
35	Search Insert Position	Easy	直接 binary search。
36	Valid Sudoku	Medium	row, col, box 三個二維陣列分別紀錄每行每列每個九宮格中1~9的使用情況，並遍歷整個 board來判斷。
37	Sudoku Solver	Hard	DFS + prune。
38	Count and Say	Easy	看看就好，不大值得寫。
39	Combination Sum	Medium	確保每個解都是按照順序列舉的就能避免重複的解。
40	Combination Sum II	Medium	類似 39題 Combination Sum。
41	First Missing Positive	Hard	O(n) time,O(1) space 的解不容易想到，將元素 i 放在第 i - 1的位置。
42	Trapping Rain Water	Hard	經典題，一定要會！
43	Multiply Strings	Medium	一般乘法方式實作即可，注意進位。
44	Wildcard Matching	Hard	dp[i][j] = dp[i - 1][j - 1] && ((s[i - 1] == p[j - 1]) || p[j - 1] == '?' || dp[i - 1][j] && p[j - 1] == '*' ('*'可以匹配任意字串，因此這裡'*'匹配 s[i])          || dp[i][j - 1] && p[j - 1] == '*' ('*'可以匹配認識字串，因此這裡'*'匹配 空字串)
45	Jump Game II	Hard	Greedy，當遍歷到當前跳躍範圍之外時，jump 數加一，並將當前跳躍範圍更新成下一步跳躍範圍，在過程中不斷更新下一步跳躍可以到達的範圍。
46	Permutations	Medium	直接 DFS 列舉。
47	Permutations II	Medium	直接 DFS 列舉，將數列排序好之後列舉前檢查當前元素是否與前一個 元素相同且前一個元素並未在此次列舉中使用 => 避免重複解。
48	Rotate Image	Medium	先轉置在將對稱的行兩兩交換。
49	Group Anagrams	Medium	先 sort 將同字元組成的 string 變成一樣，在用 HashMap 分類。
50	Pow(x, n)	Medium	recursive， 將指數部份拆分。ex: 5^4 = (5^2)^2 = 25 ^ 2
51	N-Queens	Hard	對角線 index 可用 row + col 和 row - col + (n - 1) 表示。
52	N-Queens II	Hard	與 51 N-Queens 一樣解法。
53	Maximum Subarray	Easy	O(n)，從頭掃到尾前面的和小於0的話就從當前位置開始重算。  O(nlogn)，類似 binary search，不斷分成左右兩半去找個別的 maximum，  然後跟從 mid 向左右擴展的 subarray 比較大小。
54	Spiral Matrix	Medium	當成走迷宮問題，撞牆或是遇到已經走過得路就換方向。
55	Jump Game	Medium	Greedy，不斷更新目前可以到達的最遠範圍，並判斷當前位置是否在可到達範圍內，若否直接返回 false。
56	Merge Intervals	Medium	區間題先sort!!，按左端點升序排序後，從頭遍歷，只要前一個區間與當前區間 non-overlap，就將前一個區間加入解答，反之則合併。(因為已經按左端點升序排序，因此若前一個區間與當前區間 non-overlap 則也不可能與接下來的區間overlap。)
57	Insert Interval	Hard	因為已經排序好，所以可以直接找到正確位置插入後在用Merge Intervals的方法。或是直接從頭遍歷，如果 overlap 則合併，若否則看該區間在要插入的區間左邊還右邊，將之分為左右兩個array，最後再與 merge 完的中間區間合併。
58	Length of Last Word	Easy	從尾到頭遍歷，若 len 已經大於 0 且遇到空白表示已經遍歷完最後一個 word。
59	Spiral Matrix II	Medium	和 Spiral Matrix 基本上一樣。
60	Permutation Sequence	Medium	DFS會TLE，正解蠻巧妙的不容易想到。
61	Rotate List	Medium	先找 list 的 len，之後 len % k 就是實際要 rotate 的次數，再把 tail 接到 head 後從 tail 走 len - k 步就是新的 tail。
62	Unique Paths	Medium	dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
63	Unique Paths II	Medium	基本上和Unique Paths一樣，只多需要判斷上方與左方是否為 obstacle。
64	Minimum Path Sum	Medium	基本上和Unique Paths做法差不多，每次選擇左方與上方權中較小者與當前位置累加即可。
65	Valid Number	Hard	題目寫的太複雜了，先不寫。
66	Plus One	Easy	照一般加法方式去實作即可，注意進位。
67	Add Binary	Easy	照一般加法方式實作即可，注意進位。
68	Text Justification	Hard	太麻煩了先不寫
69	Sqrt(x)	Easy	其實不容易想到，可用 binary search 在 1 ~ x 之中找 x 的平方根，或是套用牛頓法。
70	Climbing Stairs	Easy	基本DP，dp[i] = dp[i - 1] + dp[i - 2]。
71	Simplify Path	Medium	Stack，利用 stack 紀錄之前出現的目錄，並在遇到".."時 pop()。
72	Edit Distance	Hard	DP，dp[i][j] 表示從 word1[0 : i - 1] 轉換成 word2[0 : j - 1] 所需的 operation 數。  dp[i][j] = min dp[i -1][j -1]  + 1 replace operation or 0 operation if word[i -1] == word[j -1]                                dp[i -1][j]     + 1 delete operation                                dp[i][j -1]     + 1 insert operation
73	Set Matrix Zeroes	Medium	因為要求 O(1) space，可以利用第一行和第一列來紀錄，因此要  先找第一列和第一行是否有 0 ，更新 array 時第一行和第一列也要最後更新(因為存放紀錄)。
74	Search a 2D Matrix	Medium	兩種解法: 1. 做兩次 binary search ，第一次找到 target 所在的 row，第二次在該 row 上找 target。 2. 將整個 2D array 視為一個 sorted 的 1D array，index 需要特別設計，可以用 mid  / col 表示第幾列 ，mid % col 表示第幾行。
75	Sort Colors	Medium	O(n) space: counting sort  O(1) space: two pointer
76	Minimum Window Substring	Hard	爬行法，非常值得多多練習。
77	Combinations	Medium	1. recursive，注意可以剪枝只須列舉到 n - (k - cur.size()) + 1 即可。 2. 數學解，C(n,k) = C(n - 1, k - 1) + C(n - 1, k)。
78	Subsets	Medium	1. 用 77 Combinations 的作法，列舉所有長度。 2. bitwise operation，共有(1~n)， 2^n 種子集，列舉所有子集 i 然後用 i & 1 << j 來判斷第 j 個元素是否在此子集 i 中。
79	Word Search	Medium	DFS 走迷宮。
80	Remove Duplicates from Sorted Array II	Medium	需要O(1) space，紀錄目前覆蓋位置，從頭覆蓋原本的array。
81	Search in Rotated Sorted Array II	Medium	類似 33  Search in Rotated Sorted Array ，注意排除重複元素， 若 nums[mid] == nums[right] 則比較 nums[mid] 和 nums[right - 1]。
82	Remove Duplicates from Sorted List II	Medium	實作題，可多練習。
83	Remove Duplicates from Sorted List	Easy	實作題，可多練習。
84	Largest Rectangle in Histogram	Hard	Monotonic Stack，不大容易想到，可多練習。
85	Maximal Rectangle	Hard	Monotonic Stack，利用Largest Rectangle in Histogram不大容易想到，可多練習。 DP 解
86	Partition List	Medium	Linked-list 實作題，可多練習。
87	Scramble String	Hard	DFS，蠻難想到的我覺得。
88	Merge Sorted Array	Easy	Merge sort 合併技巧，從尾端開始合併。
89	Gray Code	Medium	題目太麻煩了，要先了解啥是格雷螞QQ，先不寫。
90	Subsets II	Medium	類似 Subsets 關鍵在於如何過濾重複的解。
91	Decode Ways	Medium	DP，費氏數列的變形，需多考慮當前數字是否可以和前一個 數字組合。
92	Reverse Linked List II	Medium	可多練習。
93	Restore IP Addresses	Medium	DFS 找可能的斷點並剪枝。
94	Binary Tree Inorder Traversal	Medium	必會，recursive與iterative都要會。 有空可以多看 Morris Traversal 可以在 O(1) space 下完成。
95	Unique Binary Search Trees II	Medium	divide and conquer，不斷遞迴列舉當前root所有可能的左子樹與右子樹。
96	Unique Binary Search Trees	Medium	卡特蘭數，也可以用遞迴結構去推出遞迴式。可多看看。
97	Interleaving String	Hard	DP，dp[i][j] means that if s1[0:i-1] and s2[0:j-1] can form s2[0:i + j - 1] or not。
98	Validate Binary Search Tree	Medium	inorder 可以排序!，中序走訪後看看是不是有序的即可知道是否合法。
99	Recover Binary Search Tree	Hard	inorder 可以排序!，中序走訪後找到順序錯的兩個node交換即可。
100	Same Tree	Easy	兩棵樹同時 traverse，判斷有沒有哪個node不一樣。
101	Symmetric Tree	Easy	DFS，t1->left->val == t1->right->val && t1->right->val == t2->left->val。 。
102	Binary Tree Level Order Traversal	Medium	BFS。
103	Binary Tree Zigzag Level Order Traversal	Medium	BFS，遇到奇數層就將結果翻轉後在存入。
104	Maximum Depth of Binary Tree	Easy	直接做 traversal ，dfs 或是 bfs 並紀錄經過的 node 個數即可。
105	Construct Binary Tree from Preorder and Inorder Traversal	Medium	前序決定root，中序決定左右子樹。
106	Construct Binary Tree from Inorder and Postorder Traversal	Medium	後序決定root，中序決定左右子樹。
107	Binary Tree Level Order Traversal II	Easy	BFS，輸出前再 reverse。
108	Convert Sorted Array to Binary Search Tree	Easy	類似 binary search 的技巧，每次選取中間的值作為 root，然後將左右邊剩下的值繼續遍歷，在左右邊的 sub array 中找出左子樹與右子樹的 root。
109	Convert Sorted List to Binary Search Tree	Medium	類似Convert Sorted Array to Binary Search Tree，一樣使用 binary search 的技巧，注意linked-list的操作即可。
110	Balanced Binary Tree	Easy	這題基本上就直接採用 DFS，buttom up 的方式從 leaf node 開始回傳當前度，並同時判斷左右子樹高度差是否大於 1 。
111	Minimum Depth of Binary Tree	Easy	這題也是直接 DFS 或是 BFS 搜索即可，要注意的是 leaf node 表示左右皆無子點的 node，因此 [1, 2] 的答案是 2 不是 1，因為 root 1 本身有子點 2 並不算是 leaf node。
112	Path Sum	Easy	這題也是直接 DFS 或 BFS 即可，tree 相關的題目 BFS與 DFS 真的很重要阿！
113	Path Sum II	Medium	注意儲存解的方式。
114	Flatten Binary Tree to Linked List	Medium	用 右子點->左子點->父節點 的順序遍歷
115	Distinct Subsequences	Hard	經典DP 題，值得多練習。 dp[i][j] means the number of subsequences formed form s[0:i-1] that equals to t[0:j-1] dp[i][j] = dp[i - 1][j], if s[i - 1] != t[j - 1] dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1], if s[i - 1] == t[j - 1]
116	Populating Next Right Pointers in Each Node	Medium	Inorder traverse. root->left->next = root->right; root->right->next = (root->next)? root->next->left : nullptr;
117	Populating Next Right Pointers in Each Node II	Medium	traverse 的時候必須是 root->right->left 才能確保在找左右子樹的next時 跟當前 root 同 level 且在當前 root 右邊的 node 的 next 皆已設定完畢。
118	Pascal's Triangle	Easy	這題就是要我們求帕斯卡三角形，基本上就是用 DP，當前 row 的 col i 會等於上一個 row 的 col i - 1 + col i
119	Pascal's Triangle II	Easy	我們可以宣告一個大小為最後一個 row 行數的 vector 來存放當前結果， 因此 res[j] = res[j] + res[j - 1]; res[0] = 1，從最後一個 col 往回填，因為由前往後填會把下一個 col 需要知道的 information 給蓋掉！(res[j] = res[j] + res[j - 1])。                  //當前 row 上一個 row 的 col[j] + 上一個 row 的 col[j - 1]
120	Triangle	Medium	res[j] = ((j == 0)? res[j] : min(res[j], res[j - 1])) + triangle[i][j]; 由右至左遍歷！！
121	Best Time to Buy and Sell Stock	Easy	從頭遍歷，不斷更新左邊最小的值 left_min，並解計算根據當前的 left_min 計算目前的價差，並更新目前的 最大價差。
122	Best Time to Buy and Sell Stock II	Easy	這題就是 greedy 的方式，從左至右遍歷，只要當前價格比前一個時間點還高就賣，然後將價差累加起來即可。
123	Best Time to Buy and Sell Stock III	Hard	不大容易想到，值得多多練習。
124	Binary Tree Maximum Path Sum	Hard	這題直接用遞迴從左右子樹分別找出左右子樹的最大值，然後再看看當前的 node 的 val 是否大於 0， 若大於 0 則加上當前 node 的 val。
125	Valid Palindrome	Easy	這題就直接同時從頭與從尾端依序比較第一個與第n個字元是否相等，一直遍歷到中間的字元為止，這期間只要用不符合 的情況就可以直接 return false了。另外因為字串中還是有可能會包含不需要考慮的字元要記得過濾掉(ex: 空格)。
126	Word Ladder	Hard	用 BFS 找 shortest path，bidirectional BFS的技巧可以學習一下。
127	Word Ladder	Hard	用 BFS 找 shortest path，bidirectional BFS的技巧可以學習一下。
128	Longest Consecutive Sequence	Hard	1.O(nlogn) 先 sort 再依序遍歷，至少這個解法一定要會! 2.O(n) 先用 unordered_set 存起來，再依序遍歷，遇到每個左邊界就從這開始遍歷直到 連續數字都遍歷完，持續到結束。
129	Sum Root to Leaf Numbers	Medium	DFS，照題目定義累加即可。(實作不需要額外的array)
130	Surrounded Regions	Medium	BFS，小 trick ，從邊界的 "O" 當起始點做 BFS。
131	Palindrome Partitioning	Medium	DFS 直接列舉。
132	Palindrome Partitioning II	Hard	求 131.的分割數最少的方式。先用一個二維陣列 valid[i][j] 表示 s[i~j] 是否為迴文， 接著用 dp[i] 表示 s[0 ~ i] 的最小分割數，若s[0~i] 為迴文=> dp[i] = 0 否則 dp[i] = min(dp[i], dp[j] + 1) if (s[j+1~i] 為迴文)，j < i。
133	Clone Graph	Medium	直接 DFS or BFS 做 graph traverse，注意 deep copy 跟 shadow copy的區別。
134	Gas Station	Medium	"如果以 i 為起點, 到第 j 點時汽油不夠 => 表示 i~j 都不可能存在起點"，因為以 i~j 中的點作為起點的話只要走到 j 汽油就會不夠 只要 total 的 gas[i] - cost[i] >= 0，就保證至少會有一個解。
135	Candy	Hard	但仔細想一下之後就發現其實只要用 Greedy 的方式掃兩次整個array就好，第一次從 頭開始，第一個小孩直接先給 1 顆，之後的人每個都只要往前看如果 rating 比前一個人高就給它多一顆，之後在從尾往頭 做一次一樣的事就行了!
136	Single Number	Easy	Bitwise operation ，蠻 tricky 的 值得學習一下! 對兩個相同數字做 XOR 運算會得到 0 因為 1 xor 1 = 0，因此我們就只需要把所有個數字都 xor 起來，這樣最後的結果就會留下不重複的那個數字，因為重複的數字的每個位元都會出現 2 的倍數，只有不重複的數字的每個位元 會出現奇數次。
137	Single Number II	Medium	Bitwise operation，概念蠻值得學習的。關鍵都在於說題目限制除了答案以外 的每個數字皆會出現剛好3次，因此我們可以用 shift 的操作來累加每一個位數，然後對 3 取餘數，只要single number 含有該位數 則該位數就不會是3的倍數就會被留下來。
138	Copy List with Random Pointer	Medium	實作題，deep copy 跟 shallow copy 概念要搞清楚。
139	Word Break	Medium	dp題蠻重要的，用 dp[i] 表示 s[0 : i - 1] 是否可以 break，而 dp[ i ] 可以看成如果 s[j, i - j] 在 wordList 中，則只要 s[0 : j - 1] 可以 break 則 s[0 : i - 1] 就可以 break，因此 dp[i] = dp[j] && s[j, i-j]可以break，for j < i，i = 0~s.size()。
140	Word Break II	Hard	這題是 139 題的進階題，差別在於說需要列舉出所有可能的解，因此概念一樣但是必須採用 DFS + memorize的方式，每次將當前字串分為 s[0:j ] 與 s[j: i-j]，j < i and i = 1~s.size()，並固定右半邊然後遞迴解左半邊的所有可能組合，之後再合併。
141	Linked List Cycle	Easy	Two pointers，利用快慢指針判斷cycle，一定要會!
142	Linked List Cycle II	Medium	Floyd cycle detection algorithm，一定要會!
143	Reorder List	Medium	Two pointers找到中間點再reverse後半段，然後照題目描述交錯插入即可。 實作題一定要會!
144	Binary Tree Preorder Traversal	Medium	Tree traverse 一定要會!
145	Binary Tree Postorder Traversal	Medium	Tree traverse 一定要會!
146	LRU Cache	Medium	利用 list 儲存資料，linked-list 新增/刪除 node 都只需要 O(1) time，唯一有問題的是 linked-list 在搜索的時候需要 O(n) time，因此利用 unordered_map 來儲存 key <--> list node 記憶體位置的mapping， 就可以直接搜尋到需要刪除/更新的 node 達到所有 operation 都是 O(1) time。
147	Insertion Sort List	Medium	linked list 實作題，可多練習。
148	Sort List	Medium	linked list (merge sort) 實作題，可多練習。
149
150	Evaluate Reverse Polish Notation	Medium	經典 stack 題，一定要會!