# Leetcode刷題學習筆記--Blind Curated 75

[Best practice questions](https://www.techinterviewhandbook.org/best-practice-questions/)
[blind-75-leetcode-questions](https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions)
| Question | Difficulty | Note |
| -------- | -------- | -------- |
|1. [Two Sum](https://leetcode.com/problems/two-sum/)| Easy| hash map
2. [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/):+1: |Medium| Slinding-Window + HashMap，遇到相同的char且位置大於left，則跳到相同char的下一個位置。
3. [Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/submissions/)|Medium| DP : dp[i][j] 從i到j是否為palindromic string
4. [Container With Most Water](https://leetcode.com/problems/container-with-most-water/) |Medium| two-pointers
5. [3Sum](https://leetcode.com/problems/3sum/) |Medium| three-points
6. [Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/) |Medium| fast slow pointers
7. [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/) |Easy| stack
8. [Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/) |Easy| 使用dummy node和two pointers
9. [Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/solution/) |Hard| 兩兩list合併，O(NlogK), K : size of lists, N : max length of list
10. [Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/) |Medium| 觀察rotated array，當nums[mid] > nums[right] 為左半邊有序，否則為右半邊有序。
11. [Combination Sum IV](https://leetcode.com/problems/combination-sum-iv/)|Medium| DP : dp[i] 加到i的數目 = sum(i - sum[j]);
12. [Rotate Image](https://leetcode.com/problems/rotate-image/submissions/) |Medium| 有space O(1)的做法。
13. [Group Anagrams](https://leetcode.com/problems/group-anagrams/) |Medium| 把排序過的string當成unordered_map的key
14. [Maximum Subarray](https://leetcode.com/problems/maximum-subarray/) |Medium| DP，dp[i] = max(dp[i - 1] + nums[i], nums[i]);
15. [Spiral Matrix](https://leetcode.com/problems/spiral-matrix/):+1: |Medium| 右->下->左->上
16. [Jump Game](https://leetcode.com/problems/jump-game/submissions/) |Medium| maxidx = max(maxidx, i + nums[i]);
17. [Merge Intervals](https://leetcode.com/problems/merge-intervals/) |Medium| 排序然後一個一個合併
18. [Insert Interval](https://leetcode.com/problems/insert-interval/) :+1: |Medium| 判斷是否overlap然後合併。
19. [Unique Paths](https://leetcode.com/problems/unique-paths/submissions/) |Medium| DP
20. [Climbing Stairs](https://leetcode.com/problems/climbing-stairs/) |Easy| DP
21. [Set Matrix Zeroes](https://leetcode.com/problems/set-matrix-zeroes/) |Medium| 使用cleanRow0, cleanColumn0, matrix[y][0]和matrix[0][x]來記錄要清除的row和column。
22. [Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/):+1: |Hard| Slinding window
23. [Word Search](https://leetcode.com/problems/word-search/) |Medium| Backtracking，標記已使用過的char
24. [Decode Ways](https://leetcode.com/problems/decode-ways/):+1: |Medium| DP
25. [Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/) |Medium| DFS: 使用(max, min)每次往下都更新必較的範圍。
26. [Same Tree](https://leetcode.com/problems/same-tree/) |Easy| DFS
27. [Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/submissions/) |Medium| 使用queue來記錄每一層的node
28. [Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/) |Easy | post-order traversal
29. [Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/) |Medium | preorder第一個是root, 找出root在inorder中，root左邊是left, root右邊是right
30. [Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/) |Easy | Greedy，每次都記錄遇過的最小值。
31. [Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/):+1: |Hard | post-order : 先知道child之後才可以判斷parent
32. [Valid Palindrome](https://leetcode.com/problems/valid-palindrome/) |Easy | 使用two pointer，isalnum(), tolower()
33. [Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/):+1: |Medium | 使用unordered_map，判斷有沒有前後的數字，然後把它接起來。
34. [Clone Graph](https://leetcode.com/problems/clone-graph/) |Medium |[解答](/XfUiK191STCsppXWkgjbXQ#133-Clone-Graph)，使用map記住新舊node的對應|
35. [Word Break](https://leetcode.com/problems/word-break/) |Medium | DP
36. [Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/) |Easy | fast-slow pointers
37. [Reorder List](https://leetcode.com/problems/reorder-list/) |Medium | 用Stack紀錄ListNode，然後串接起來。
38. [Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/) |Medium | DP, 最大值有可是最小值x負值變成最大值。
39. [Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/submissions/) |Medium | 比較nums[mid]和nums[right]來判斷是左半還是右半。
40. [Reverse Bits](https://leetcode.com/problems/reverse-bits/) :+1: |Easy | 有O(1)的解法
41. [Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/) |Easy | n = n & (n - 1);
42. [House Robber](https://leetcode.com/problems/house-robber/) |Medium | DP: dp[i] = max(take, notake);
43. [Number of Islands](https://leetcode.com/problems/number-of-islands/) |Medium | DFS
44. [Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/) |Easy | recursive
45. [Course Schedule](https://leetcode.com/problems/course-schedule/) :+1: |Medium | 統計每個課程需要修的次數和修了之後那些可以減少
46. [Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/) |Medium | 使用unordered_map<char, node *>
47. [Design Add and Search Words Data Structure](https://leetcode.com/problems/design-add-and-search-words-data-structure/) |Medium | 使用trie，search時遇到'.'就連帶尋找全部的可能
48. [Word Search II](https://leetcode.com/problems/word-search-ii/) :+1: |Hard | Trie + Recursive
49. [House Robber II](https://leetcode.com/problems/house-robber-ii/) |Medium | DP : 多傳一個變數來判斷是否rob 1
50. [Contains Duplicate](https://leetcode.com/problems/contains-duplicate/) |Easy | 使用set來判斷
51. [Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/) |Easy | Recursive, preorder traversal
52. [Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/) |Medium | inoder transversal 就可以達到由小到大的值。
53. [Lowest Common Ancestor of a Binary Search Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/) |Easy| 利用BST的特性，看看p, q和root->val的關係。
54. [Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/) |Medium | 列出forward和backward vector
55. [Valid Anagram](https://leetcode.com/problems/valid-anagram/) |Easy | 使用vector統計
56. [Meeting Rooms](https://leetcode.com/problems/meeting-rooms) |Easy|:see_no_evil:
57. [Meeting Rooms II](https://leetcode.com/problems/meeting-rooms-ii/) |Medium |使用priority_queue來記錄最快結束的room :see_no_evil:``|
58. [Graph Valid Tree](https://leetcode.com/problems/graph-valid-tree/) |Medium | Union Find |
59. [Missing Number](https://leetcode.com/problems/missing-number/) |Easy | 先把總和算出來再減掉全部數值
60. [Alien Dictionary](https://leetcode.com/problems/alien-dictionary) |Hard|:see_no_evil:
61. [Encode and Decode Strings](https://leetcode.com/problems/encode-and-decode-strings) |Medium|:see_no_evil:
62. [Find Median from Data Stream](https://leetcode.com/problems/find-median-from-data-stream/):+1: |Hard | 1 2 3 [4] 5 6 7</br> -----> <------ minheap</br>maxheap
64. [Serialize and Deserialize Binary Tree](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/) |Hard | istringstream</br>ostringstream</br> roo->val left-tree right-tree|
65. [Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/) |Medium | DP
66. [Coin Change](https://leetcode.com/problems/coin-change/) |Medium | dp[i] = min(dp[i], dp[i - c]); c 為 coin[j]
67. [Number of Connected Components in an Undirected Graph](https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/) |Medium| Union Find :see_no_evil: |
68. [Counting Bits](https://leetcode.com/problems/counting-bits/) |Easy | 利用以前的結果
69. [Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/) |Medium | 使用map或是bucket sort都可以達到。
70. [Sum of Two Integers](https://leetcode.com/problems/sum-of-two-integers/):+1: |Medium | Recursive，getSum(a ^ b, ((unsigned int)(a & b)) << 1);
71. [Pacific Atlantic Water Flow](https://leetcode.com/problems/pacific-atlantic-water-flow/) |Medium |使用BFS分別找出可以流向pacific和atlantic的點 |
72. [Longest Repeating Character Replacement](https://leetcode.com/problems/longest-repeating-character-replacement/) :+1: |Medium | Slinding window, 如果已經找到一個答案window的大小就不用小於這個答案。
73. [Non-overlapping Intervals](https://leetcode.com/problems/non-overlapping-intervals/):+1: |Medium | 排序，two-pointers，刪掉結束數字最大那個。
74. [Subtree of Another Tree](https://leetcode.com/problems/subtree-of-another-tree/):+1: |Easy | preorder traversal, 把tree serialize然後比較字串。
75. [Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/) |Medium | DP : dp[i][j] 從i到j是palindromic substring

###### tags: `leetcode` `刷題`