Beginner - HackMD

--- tags: Leetcode title: Beginner author: NCL --- # Weekly Meeting Google meet: [Here](https://meet.google.com/mok-ruez-eht) # Team's Timeline #### Goal: complete 75 problems [Blind 75 LeetCode Questions](https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions) # Totally solved problem: 14 #### Candidate * Array: * Product of Array Except Self * Maximum Product Subarray * Find Minimum in Rotated Sorted Array * Search in Rotated Sorted Array * Binary: * * Counting Bits * Dynamic Programming: * Longest Common Subsequence * Word Break Problem * House Robber II * Unique Paths * Jump Game * Graph: * Clone Graph * Course Schedule * Pacific Atlantic Water Flow * Number of Islands * Longest Consecutive Sequence * Alien Dictionary (Leetcode Premium) * Graph Valid Tree (Leetcode Premium) * Number of Connected Components in an Undirected Graph (Leetcode Premium) * Interval: * Insert Interval * Merge Intervals * Non-overlapping Intervals * Meeting Rooms (Leetcode Premium) * Meeting Rooms II (Leetcode Premium) * Linked List: * Reverse a Linked List * Merge K Sorted Lists * Matrix:  * String: * Minimum Window Substring * Valid Anagram * Group Anagrams * Longest Palindromic Substring * Encode and Decode Strings (Leetcode Premium) * Tree: * Serialize and Deserialize Binary Tree * Kth Smallest Element in a BST * Implement Trie (Prefix Tree) * Add and Search Word * Heap: * Merge K Sorted Lists * Top K Frequent Elements * Find Median from Data Stream ![](https://i.imgur.com/rtNP4qt.gif =30%x) ## Feb 2023 ### Starter week (2/20 - 2/24): * Array: * Best Time to Buy and Sell Stock (Chou) * [Contains Duplicate](https://docs.google.com/presentation/d/1ODahtkWeTOQatq2qa1Ua9CwVAwVk9mGapSnAi9nXmv8/edit?usp=sharing) (Sean) * [Maximum Subarray](https://docs.google.com/presentation/d/1VtEe0TmWg3SCmctJc7s4ikNJlaogvZwKMb4FouW1eLM/edit?usp=sharing) (Shao) ### 2nd week (2/25 - 3/3): * Array: * 3 Sum (Shao) * [Container With Most Water](https://docs.google.com/presentation/d/1IAwXKcf8DJH_kyAj0Q4CAPpwnAYk3rwgEXXizSgLCl0/edit?usp=sharing) (Sean) * Two Sum (Chou) ## Mar 2023 ### 3rd week (3/4 - 3/10): * Matrix: * Word Search (Chou) * [Rotate Image](https://docs.google.com/presentation/d/1m88skiEB2Vh5jF9qROJ1DBXfU6QHQCpQ2QntCCe-YqE/edit?usp=sharing) (Sean) * Set Matrix Zeroes (Shao) * [Spiral Matrix](https://docs.google.com/presentation/d/1ZhJWcw3NloLT_9LnqDqjFVevK8pGec5T/edit?usp=sharing&ouid=110234842560907932508&rtpof=true&sd=true) (Maggie) ### 4th week (3/11 - 3/17): Friday 18:00 * Linked List: * Merge Two Sorted Lists (Chou) * Remove Nth Node From End Of List(Shao) * [Reorder List](https://docs.google.com/presentation/d/12SMiKjhajJQ7NkiCIE1TrkL2Nd8kdbtdm-CNk5rWWgw/edit?usp=sharing) (Sean) * [Detect Cycle in a Linked List](https://docs.google.com/presentation/d/1ZjxPvlM5ZTwhB5FqudvXfNGmOmUWFJ9Y/edit?usp=sharing&ouid=110234842560907932508&rtpof=true&sd=true) (Maggie) ### 5th week (3/18 - 3/24): break; ### 6th week (3/25 - 3/31): 暫定3/29晚8 * Tree: * Invert/Flip Binary Tree (Chou) * [Validate Binary Search Tree](https://docs.google.com/presentation/d/1TY9gNYtsNpfzd7sW-jlxCu5GWfaMraJEsnLAfD836Go/edit?usp=sharing) (Sean) * Same Tree (Shao) * [Binary Tree Level Order Traversal](https://docs.google.com/presentation/d/1Znavckud2lN6v4V_qvszfHfFANLoaVbc/edit?usp=sharing&ouid=110234842560907932508&rtpof=true&sd=true) (Maggie) * Subtree of Another Tree(Han) ## Apr 2023 ### 7th week (4/1 - 4/7): 暫定 4/7 下午4點 ``` break; ``` ### 8th week (4/8 - 4/14): 4/14 14:00 UTC+8 * Dynamic Programming: * Decode Ways (Chou) * [Combination Sum](https://docs.google.com/presentation/d/1CHBmFWwjZxLtouqhNq3DyQlI1dKqs3XIUPFRnX4PjYI/edit?usp=sharing) (Sean) * [Coin Change](https://docs.google.com/presentation/d/1Znk6UyrmKiZqQQ7vmc2X8tKqES1KBzRw/edit?usp=sharing&ouid=110234842560907932508&rtpof=true&sd=true) (Maggie) * Longest Increasing Subsequence (Shao) * Climbing Stairs (Shiuan) * [House Robber (Han)](https://docs.google.com/presentation/d/1l7oIgzslOY4WlUzJMatAuI0Z9U9kE7f6tNeiTegejsM/edit#slide=id.g2105c826b1a_0_204) ### 9th week (4/15 - 4/21): * Tree * Word Search II (Chou) * Binary Tree Maximum Path Sum (Shao) * [Lowest Common Ancestor of BST](https://docs.google.com/presentation/d/1dQ0tflHsNVhV9sykFqDHGuFgoUlrNMNDNqBuSM4LeVs/edit?usp=sharing) (Sean) * [Kth Smallest Element in a BST](https://docs.google.com/presentation/d/1ZxsIXL3Rlu4sT0H7W5zYP7Fm37On4xuR/edit?usp=sharing&ouid=110234842560907932508&rtpof=true&sd=true) (Maggie) * Maximum Depth of Binary Tree (Shiuan) * [Construct Binary Tree from Preorder and Inorder Traversal](https://docs.google.com/presentation/d/10lNTKuroQOJozIU_9DPGkpv5gfTBoW4uBrk7p4woDb0/edit#slide=id.p)(Han) ### 10th week (4/22 - 4/28): break; ## May 2023 ### 11th week (4/29 - 5/5): break; ### 12th week (5/6 - 5/12): * String * [Longest Substring Without Repeating Characters](https://docs.google.com/presentation/d/1wJUbq1f7HkwUwU3pOlLoIE-RRCIW6I3R06nKKWkH144/edit#slide=id.p)(Han) * Valid Palindrome(Shiuan) * Valid Anagram(Shao) * [Palindromic Substrings](https://docs.google.com/presentation/d/1J6vdefVYmSFceGSut7Y6qo8Q7GKNEz1uRLYhaPWWo40/edit?usp=sharing) (Sean) * [Longest Repeating Character Replacement](https://docs.google.com/presentation/d/1__RxDmMWJ7JIW-hfdWX4h7T4uCYNvjr0/edit?usp=sharing&ouid=110234842560907932508&rtpof=true&sd=true)(Maggie) * Valid Parentheses (Chou) ### 13th week (5/15 - 5/19): * Binary * [Missing Number](https://docs.google.com/presentation/d/1aXSBM04AMBH-zHQQHM12l9JtyWYLun8b/edit?usp=sharing&ouid=110234842560907932508&rtpof=true&sd=true) (Maggie) * Sum of Two Integers (Chou) * Reverse Bits (Shao) * Number of 1 Bits (Shiuan) * [Counting Bits](https://docs.google.com/presentation/d/1I1vlgAk8X-Gm8B4a2-RBb6Cu3tStS-P4BLB9uTQGP0M/edit?usp=sharing) (Sean) * 畢業 (Han) 88有空常來:>by超超哭哭超哥最愛畢業生<3! 幫我內推拜託惹大學長 ### 14th week (5/22 - 5/26): ## Jun 2023 ### 15th week (5/27 - 6/2): ### 16th week (6/3 - 6/9): ### 17th week (6/10 - 6/16): ### 18th week (6/17 - 6/23): ### 19th week (6/24 - 6/30): # Before practice (2/24) ## Using VS code extension Reference: [Here](https://blog.csdn.net/engineerxin/article/details/99875113) [optional](https://www.wongwonggoods.com/python/vscode-leetcode-extension/) Ubuntu 20.04 LTS Install node.js in your computer ``` sudo apt-get install nodejs ``` ``` sudo apt-get install npm ``` Check path ``` which nodejs ``` Result: ``` /usr/bin/nodejs ``` (Add this path to your extension's setting) Install Leetcode extension in VS code environment You can sign in by cookie (See [optional](https://www.wongwonggoods.com/python/vscode-leetcode-extension/)) ### See also: git clone: [同步遠端分支筆記](https://zlargon.gitbooks.io/git-tutorial/content/remote/sync.html) ## Table ### Provide by Shao | 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 | 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 | 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 # Reference ## Some other useful notes [HackMD-Leetcode刷題學習筆記–心得統整](https://hackmd.io/@meyr543/r1skFcvgY)