/Leetcode

My Leetcode's Solution

Primary LanguageJava

Leetcode

Some nonsense

Well, It's May 2018, I graduated last week, but I'm still seeking a job. I'm jobless right now .....

WOW, time is flying! It's May 2019, I have worked as a software engineer for Gemalto for around 1 year. Most of my work is to implement UI components for desktop App in Windows using WPF. I don't have lots of chances to touch data structure and algorithm .... I come back because I find out I have to keep familiar with data structures and algorithms and make sure I still have ability to solve algorithm problem quickly, because I never know when the next interview will come... I don't want to pass any opportunities. All I can do is to make sure I am fully prepared when the next chance is coming.

Trust The Process

Top interview problem

Question Done Date Code Note
1. Two Sum 2018/5/28 Here Two ways: 1. sorting + two pointers; 2. HashMap
2. Add Two Numbers 2018/6/1 Here two pointers, advacend bit
3. Longest Substring Without Repeating Characters 2018/6/4 Here Two pointers + Boolean array recording character appearing in s[slow:fast]
5. Longest Palindromic Substring 2018/6/6 Here Two pointers
6. ZigZag Conversion 2019/6/3 Java generate result strings level by level
8. String to Integer (atoi) 2018/6/6 Here Edge cases: 1. leading blanks; 2. '+' or '-'; 3. Integer overflow
10. Regular Expression Matching 2018/6/7 Here DP
11. Container With Most Water 2018/5/21 Here Two Pointer
13. Roman to Integer 2018/6/4 Here Math logic
14. Longest Common Prefix 2018/6/5 Here Pointer to specify index we're at + vertical iteration and comparation
15. 3Sum 2018/5/28 Here Classical Sorting + two pointers
17. Letter Combinations of a Phone Number 2018/6/6 Here Backtracking
19. Remove Nth Node From End of List 2018/6/1 Here two pointers
20. Valid Parentheses 2018/6/6 Stack
21. Merge Two Sorted Lists 2018/5/22 Here Two Pointer, Merge sort
22. Generate Parentheses 2018/6/6 Here Backtracking
23. Merge k Sorted Lists 2018/6/2 Here Priority Queue
26. Remove Duplicates from Sorted Array 2018/5/25 Here Two pointers
28. Implement strStr() 2018/6/5 Here Using java built-in substring() and equals()
31. Next Permutation 2019/5/27 Java find the element which is left of the last peak idx, then find the first element which is larger than nums[left] from the end. Swap them then reverse the array from the last peak to the end
33. Search in Rotated Sorted Array 2018/5/22 Here Binary Search
34. Search for a Range 2018/5/26 Here Binary search
38. Count and Say 2018/6/6 Here Operation of StringBuilder
41. First Missing Positive 2018/5/21 Here Using Index space
42. Trapping Rain Water 2019/6/6 Java 2-way iteration:the first round is from left to right; the second round is from right to left
44. Wildcard Matching 2018/6/7 Here DP
46. Permutations 2019/5/27 Java Backtracking: enumerate every possibilities at each index
48. Rotate Image 2018/5/27 Here Four pointer to denote four points on which we need to operate
49. Group Anagrams 2018/6/5 Here HashMap; Firstly sort the string
53. Maximum Subarray 2018/5/22 Here DP
54. Spiral Matrix 2018/5/26 Here Four pointers to denote boundaries
55. Jump Game 2018/5/21 Here DP
56. Merge Intervals 2018/5/21 Here Sorting + Greedy
60. Permutation Sequence 2019/5/27 Java given an array with 1 to n. After idx i, there are (n-i-1)! permutations. Then we can compute the number at idx i one by one ( k / (n-i-1)! )
62. Unique Paths 2018/5/28 Here Classical DP
66. Plus One 2018/5/28 Here Advanced bit
69. Sqrt(x) 2018/6/30 Here Binary Search
72. Edit Distance 2019/5/18 Here Classical DP
73. Set Matrix Zeroes 2018/5/25 Here Take use of original matrix space
75. Sort Colors 2018/5/26 Here Two pointer
76. Minimum Window Substring 2018/6/4 Here Same as above
78. Subsets 2018/5/25 Here Backtracking (general way to solve subsets problem)
79. Word Search 2018/5/22 Here DFS
84. Largest Rectangle in Histogram 2018/5/26 Here For each number, find longest range in which it's the minimum with the help of stack
87. Scramble String 2018/5/14 Java DFS: Suppose we are standing at index i. string A is scramble string of string B if:
  • isScramble(A[0,i], B[0,i]) && isScramble(A[i, end], B[i, end]
Or:
  • isScramble(A[0,i], B[end-i, end]) && isScramble(A[i, end], B[0, end-i]
90. Subsets II 2018/5/25 Here Sort + Backtracking
91. Decode Ways 2018/6/4 Here DP, edge cases, care about '0'
94. Binary Tree Inorder Traversal 2018/6/10 Here Do DFS on Binary Tree. Visit left subtree firstly, then visit root, finally visit right subtree
98. Validate Binary Search Tree 2018/6/10 Here From bottom to top. Firstly check left subtree, then check right subtree, finally check root.
101. Symmetric Tree 2018/6/11 Here
  • Recursion.
  • isMirror(left.right, right.left) && isMirror(left.left, right.right) && left.val == right.val
102. Binary Tree Level Order Traversal 2018/6/10 Here Using Queue to do BFS
103. Binary Tree Zigzag Level Order Traversal 2018/6/8 Here Queue + boolean flag
104. Maximum Depth of Binary Tree 2018/6/11 Here BFS using Queue
105. Construct Binary Tree from Preorder and Inorder Traversal 2018/5/28 Here logic behind preorder and inorder
108. Convert Sorted Array to Binary Search Tree 2018/6/11 Here Recursion + Property of BALANCED BST
116. Populating Next Right Pointers in Each Node 2018/6/11 Here
  • Iteration. Do BFS
  • Recursion. connect Left Subtree, then connect right subtree, finally connect right boundary of left subtree with left boundary of right subtree.
121. Best Time to Buy and Sell Stock 2018/5/29 Here DP
122. Best Time to Buy and Sell Stock II 2018/5/29 Here DP
123. Best Time to Buy and Sell Stock III 2018/5/31 Here DP
124. Binary Tree Maximum Path Sum 2018/6/11 Here
  • DP on Tree.
  • Recursive function returns local maximum of path sum which passed through root.
  • We passed a global variable in recursive function, where we possibly update global maximum.
125. Valid Palindrome 2018/6/4 Here Two pointers, one is moving forward while the other is moving backward
127. Word Ladder 2018/6/14 Here Change one character in string to build a new string. BFS
128. Longest Consecutive Sequence 2018/5/21 Here HashMap
130. Surrounded Regions 2018/6/13 Here DFS + Mark out node which's not killed
131. Palindrome Partitioning 2018/6/12 Here DP for checking and finding Palindrome string. Backtracking for partitioning palindrome string.
134. Gas Station 2018/7/12 Here Greedy. We need to find the peak of fuel "need" (the need of i is cost[i]-gas[i]). If we can run around a circuit successfully, the start point should be the next index of "need" peek. But if at the end the accumulated need is larger than 0, we cannot complete a circuit.
136. Single Number 2018/7/11 Here XOR
137. Single Number II 2018/7/12 Here Bitwise + State Machine
138. Copy List with Random Pointer 2018/6/2 Here Firstly, copy label and put new generated node right behind original node; Then copy random pointer; Finally, extract copied nodes and reset original list
139. Word Break 2018/7/12 Here DP: DP[i] denotes whether we can break s[0:i-1]
140. Word Break II 2019/6/6 Java
  • Used DP to find if we can break words. DP[i] stores all index j such that s.substring(j,i) exists in wordDict
  • Generated result strings using DFS
141. Linked List Cycle 2018/6/1 Here Two pointers, one moves forward by 2 steps while the other moves forward by 1 step.
146. LRU Cache 2019/5/15 Java
  • Bidirection linked list as container
  • Using hashMap to store key : node of linked list
  • the tail of linked list will be removed when cache is full
  • new coming value will go into the head of the list
  • The most recent visit value will be extracted from the list and put to the head of the list
148. Sort List 2018/6/2 Here Merge Sort
149. Max Points on a Line 2018/7/8 Here
  • 1. Use HashMap to store "slope"
  • 2. Normalized diffY and diffX based on their GCD. And generated a String as key in the HashMap, inorder to deal with Double's precision problem.
150. Evaluate Reverse Polish Notation 2018/7/11 Here Using Stack to store number we met. Each time we meet an operator, We do a computation on the top two numbers, then we push the result back to the top of stack.
152. Maximum Product Subarray 2018/5/21 Here DP
155. Min Stack 2018/7/9 Here Each time we push a new item, we need to push current Minimal value alongside.
160. Intersection of Two Linked Lists 2018/6/1 Here Two pointers, finding entry point of the circular list
162. Find Peak Element 2018/5/24 Here Binary Search
163. Missing Ranges 2018/5/23 Here Iteration, edge cases
166. Fraction to Recurring Decimal 2018/7/6 Here 1. Using recursion to compute decimal 2. Using hashmap to deal with infinite circulating decimal
169. Majority Element 2018/5/21 Here Candidate + Count
188. Best Time to Buy and Sell Stock IV 2018/5/31 Here DP
189. Rotate Array 2018/5/23 Here General way to rotate array (3 reverse)
190. Reverse Bits 2018/6/18 Here
  • Iteration + Bit Operation
  • Divide & Conquer
198. House Robber 2018/7/8 Here Easy DP
200. Number of Islands 2018/7/9 Here Two solutions:
  • 1. Using DFS to "clear" a island when we meet an new island. However, this solution requires us to modify the input grid map
  • 2. If we are not allowed to modify grid map, Get help from Union Find
202. Happy Number 2018/7/12 Here Iteration + Using HashSet to record number we've met.
206. Reverse Linked List 2018/6/1 Here Two ways: 1. recursion; 2. pinpoint tail, and then continuously move head to the next of tail, until tail is head.
207. Course Schedule 2018/6/13 Here Topo sort
208. Implement Trie (Prefix Tree) 2018/6/21 Here Fundamental implementation of Trie
210. Course Schedule II 2018/6/13 Here Topo Sort
212. Word Search II 2018/6/19 Here Trie Tree stores dictionary, DFS searches words in mtx
215. Kth Largest Element in an Array 2018/6/21 Here
  • Priority Queue
  • Quick select (partition in QuickSort)
217. Contains Duplicate 2018/5/29 Here 1. Sorting; 2. HashSet
224. Basic Calculator 2018/6/7 Here
  • Recursion
  • Or using math logics
227. Basic Calculator II 2018/6/7 Here Stack, reverse polish expression
230. Kth Smallest Element in a BST 2018/6/10 Here Do Binary Search on BST. It's just like do DFS on BST, so that we can visit nodes in order. And we record how many nodes we have visited, and once we visited Kth node, we return it.
234. Palindrome Linked List 2018/5/22 Here Two Pointer, find half point in Linkedlist
236. Lowest Common Ancestor of a Binary Tree 2018/6/11 Here Recursion + From Bottom to top
237. Delete Node in a Linked List 2018/6/1 Here Set node's value to next node's value. Like the way we use to delete a value in the array
239. Sliding Window Maximum 2019/5/20 Java
  • Using PriorityQueue to store the elements with its idx within the window [O(nlogk)]
  • Using Deque to store the idx of elements within the window [O(n)]
242. Valid Anagram 2018/7/6 Here
    Two solutions:
  • 1. Sort two Strings, and then compare them.
  • 2. Using Array to store appearances of each character
251. Flatten 2D Vector 2018/6/12 Here Index to show we're at the Col-th element in the Row-th list. When moving forward col and row, we need to care about empty list
253. Meeting Rooms II 2018/7/3 Here 1st solution: Using TreeMap; 2nd Solution: using priority queue
266. Palindrome Permutation 2019/5/27 Java If only one character appears odd times, then the string can be converted to a palindrome.
267. Palindrome Permutation II 2019/5/27 Java Determine if a string can be converted to palindromes + backtracking to generate palindromes
268. Missing Number 2018/5/23 Here Using index space!
269. Alien Dictionary 2018/6/18 Here Topo Sort
283. Move Zeroes 2018/5/22 Here Two Pointer
285. Inorder Successor in BST 2018/6/10 Here do recursion along with passing a upperRight node
287. Find the Duplicate Number 2018/5/22 Here Binary Search (Brilliant!)
295. Find Median from Data Stream 2018/6/22 Here Two PriorityQueues: maxHeap + minHeap
297. Serialize and Deserialize Binary Tree 2018/6/12 Here Borrow ideas from Heap
300. Longest Increasing Subsequence 2018/6/14 Here Build LIS. Use binary search to find the lowerBoundIdx in the LIS when we meet an new number
309. Best Time to Buy and Sell Stock with Cooldown 2018/5/31 Here DP
315. Count of Smaller Numbers After Self 2018/6/13 Here Get helps from Merge Sort
322. Coin Change 2018/6/12 Here DP
328. Odd Even Linked List 2018/6/2 Here put nodes in one list to another list
329. Longest Increasing Path in a Matrix 2018/6/18 Here DFS + Memoization
334. Increasing Triplet Subsequence 2018/6/20 Here Borrow Idea from 300. Longest Increasing Subsequence. If one sequence contains Increasing Triple Subsequence, it means this array contains at least one increasing subsequence with 3 numbers.
340. Longest Substring with At Most K Distinct Characters 2018/6/4 Here
  • Two pointers to delimit substring;
  • HashMap to record how many different character appear in substring, and record number of appearances of each character
344. Reverse String 2018/6/5 Here Easiest
378. Kth Smallest Element in a Sorted Matrix 2018/6/12 Here Two ways:
  • PriorityQueue: Put element into PQ, along with each element, we also record their coordinates(x, y)
  • Binary Search: Just like the solution of 41. First Missing Positive, We do binary search on values space of elements in matrix
380. Insert Delete GetRandom O(1) 2018/5/29 Here ArrayList + HashMap + record index in hashmap
381. Insert Delete GetRandom O(1) - Duplicates allowed 2018/5/30 Here ArrayList + HashMap + record indexes using linkedlist
384. Shuffle an Array 2018/7/1 Here How to shuffle an array? For each index i from array.length-1 to 0, you can find an random number j ranged from [0, i], then swap array[i] and array[j]
387. First Unique Character in a String 2018/6/4 Here Using array to store appearance of lowercase character
454. 4Sum II 2018/6/13 Here Recall HashMap way in 2Sum. Turn 4Sum to 2Sum. See A[i]+B[j] as one, and C[k]+D[l] as the other.
526. Beautiful Arrangement 2019/5/30 Java Classical backtracking solution
675. Cut Off Trees for Golf Event 2019/6/2 Java
  • Using priorityqueue to sort the trees by their heights.
  • Cut the next tree one by one. Computing the distance between the current pos and the next tree's pos using BFS
695. Max Area of Island 2019/5/14 Java Follow up to the number of islands. Using DFS to find an island and count the area, and eliminate it.
703. Kth Largest Element in a Stream 2019/6/6 Java Easy minHeap (PriorityQueue) operation
712. Minimum ASCII Delete Sum for Two Strings 2019/5/18 Here It is very similar to 72. EditDistance. Classical DP
771. Jewels and Stones 2019/5/20 Java Using array to store the existance of characters
772. Basic Calculator III 2018/6/7 Here
  • Recursion to solve embedded expression closed by '()'
  • Stack to solve operators with diffrent priority
841. Keys and Rooms 2019/5/15 Java
  • Firstly convert the input string to a hashMap <room : [keys]>, which represents a graph structure
  • Classic DFS, nothing special. Using a boolean array to determine if a room is visiting or not
851. Loud and Rich 2019/5/16 Java
  • the richness among people can be converted into a tree(using hashMap)
  • Then go through each person, populate the quietist person from top to bottom: If a node is quieter than the value which children nodes has stored, then update the answer for that children node and continue populating the result for the children nodes of that node
872. Leaf-Similar Trees 2019/5/16 Using DFS to generate leaves string, then do comparison.
909. Snakes and Ladders 2019/6/2 Java BFS variance. Need to jump if a grid touch ladder or snake
931. Minimum Falling Path Sum 2019/6/3 Java Classical DP
934. Shortest Bridge 2019/5/18 Java Another variance of Number of islands. Still using DFS to find islands. And because there are only 2 islands, we can mark the found island using '1' and '2'. Then using DFS to find the shortest bridge between 2 islands.
  • Small performance improvement tip: if we use a hashset to store the locations of island 2, we can know if a bridge reaches island 2 in O(1) when we are doing DFS
    		•
    937. Reorder Log Files 2019/5/21 Java Sorting with customized comparator.
    957. Prison Cells After N Days 2019/5/23 Java Math : Find the cycle of states
    983. Minimum Cost For Tickets 2019/5/31 Java DP: res[i]represents the minimal costs at day i ending with 1-day pass([0]), ending with 7-day pass([1]), ending with 30-day pass([2]). Only update DP matrix for the day we travel, otherwise just directly copy the previous day's result
    984. String Without AAA or BBB 2019/5/30 Java Greedy algorithm:
    • Always put the character which has left more into the result firstly.
    • If we've already put 2 consective identical characters, then put the other one instead.
    1019. Next Greater Node In Linked List 2019/6/6 Java Using Stack to store visited values with their idx. When we meet a new value, pop up the previous smaller elements, and update their result to the value of the current node.
    1053. Previous Permutation With One Swap 2019/5/27 Java Reversed processing of Next Permutation. Find the bottom from the end firstly, the left element of the bottom is the element we need to change (called it bigger element). Then find out the first element which is slower than the bigger element from the end. Then swap them.

    Array

    Question Done Date Code Note
    11. Container With Most Water 2018/5/21 Here Two pointer
    16. 3Sum Closest 2018/5/21 Here Sorting
    41. First Missing Positive 2018/5/21 Here Using Index space
    238. Product of Array Except Self 2018/5/21 Here DP
    169. Majority Element 2018/5/21 Here Candidate + Count
    152. Maximum Product Subarray 2018/5/21 Here DP
    56. Merge Intervals 2018/5/21 Here Sorting + Greedy
    55. Jump Game 2018/5/21 Here DP
    153. Find Minimum in Rotated Sorted Array 2018/5/21 Here Binary Search
    154. Find Minimum in Rotated Sorted Array II 2018/5/21 Here Binary Search
    128. Longest Consecutive Sequence 2018/5/21 Here HashMap
    33. Search in Rotated Sorted Array 2018/5/22 Here Binary Search
    81. Search in Rotated Sorted Array II 2018/5/22 Here Binary Search
    53. Maximum Subarray 2018/5/22 Here DP
    283. Move Zeroes 2018/5/22 Here Two Pointer
    79. Word Search 2018/5/22 Here DFS
    287. Find the Duplicate Number 2018/5/22 Here Binary Search (Brilliant!)
    268. Missing Number 2018/5/23 Here Using index space!
    163. Missing Ranges 2018/5/23 Here Iteration, edge cases
    189. Rotate Array 2018/5/23 Here General way to rotate array (3 reverse)
    162. Find Peak Element 2018/5/24 Here Binary Search
    78. Subsets 2018/5/25 Here Backtracking (general way to solve subsets problem)
    90. Subsets II 2018/5/25 Here Sort + Backtracking
    26. Remove Duplicates from Sorted Array 2018/5/25 Here Two pointers
    73. Set Matrix Zeroes 2018/5/25 Here Take use of original matrix space
    84. Largest Rectangle in Histogram 2018/5/26 Here For each number, find longest range in which it's the minimum with the help of stack
    75. Sort Colors 2018/5/26 Here Two pointer
    34. Search for a Range 2018/5/26 Here Binary search
    54. Spiral Matrix 2018/5/26 Here Four pointers to denote boundaries
    48. Rotate Image 2018/5/27 Here Four pointer to denote four points on which we need to operate
    105. Construct Binary Tree from Preorder and Inorder Traversal 2018/5/28 Here logic behind preorder and inorder
    66. Plus One 2018/5/28 Here Advanced bit
    1. Two Sum 2018/5/28 Here Two ways: 1. sorting + two pointers; 2. HashMap
    15. 3Sum 2018/5/28 Here Classical Sorting + two pointers
    62. Unique Paths 2018/5/28 Here Classical DP
    217. Contains Duplicate 2018/5/29 Here 1. Sorting; 2. HashSet
    121. Best Time to Buy and Sell Stock 2018/5/29 Here DP
    122. Best Time to Buy and Sell Stock II 2018/5/29 Here DP
    123. Best Time to Buy and Sell Stock III 2018/5/31 Here DP
    188. Best Time to Buy and Sell Stock IV 2018/5/31 Here DP
    309. Best Time to Buy and Sell Stock with Cooldown 2018/5/31 Here DP
    380. Insert Delete GetRandom O(1) 2018/5/29 Here ArrayList + HashMap + record index in hashmap
    381. Insert Delete GetRandom O(1) - Duplicates allowed 2018/5/30 Here ArrayList + HashMap + record indexes using linkedlist
    689. Maximum Sum of 3 Non-Overlapping Subarrays 2018/6/1 Here DP, variance of Best Time to Buy and Sell Stocks
    251. Flatten 2D Vector 2018/6/12 Here Index to show we're at the Col-th element in the Row-th list. When moving forward col and row, we need to care about empty list
    131. Palindrome Partitioning 2018/6/12 Here DP for checking and finding Palindrome string. Backtracking for partitioning palindrome string.
    315. Count of Smaller Numbers After Self 2018/6/13 Here Get helps from Merge Sort
    454. 4Sum II 2018/6/13 Here Recall HashMap way in 2Sum. Turn 4Sum to 2Sum. See A[i]+B[j] as one, and C[k]+D[l] as the other.
    300. Longest Increasing Subsequence 2018/6/14 Here Build LIS. Use binary search to find the lowerBoundIdx in the LIS when we meet an new number
    269. Alien Dictionary 2018/6/18 Here Topo Sort
    334. Increasing Triplet Subsequence 2018/6/20 Here Borrow Idea from 300. Longest Increasing Subsequence. If one sequence contains Increasing Triple Subsequence, it means this array contains at least one increasing subsequence with 3 numbers.
    215. Kth Largest Element in an Array 2018/6/21 Here
    • Priority Queue
    • Quick select (partition in QuickSort)
    845. Longest Mountain in Array 2018/6/25 Here Two Pointers way:
    • Firstly find the peak (be careful about the platform, which is not the actual peak)
    • Secondly find the bottom
    719. Find K-th Smallest Pair Distance 2018/6/25 Here Binary Search on space of possible answers: We can know minimal distance and maximal distance from sorted array, then binary search to find k-th distance.
    384. Shuffle an Array 2018/7/1 Here How to shuffle an array? For each index i from array.length-1 to 0, you can find an random number j ranged from [0, i], then swap array[i] and array[j]
    253. Meeting Rooms II 2018/7/3 Here 1st solution: Using TreeMap; 2nd Solution: using priority queue
    198. House Robber 2018/7/8 Here Easy DP
    134. Gas Station 2018/7/12 Here Greedy. We need to find the peak of fuel "need" (the need of i is cost[i]-gas[i]). If we can run around a circuit successfully, the start point should be the next index of "need" peek. But if at the end the accumulated need is larger than 0, we cannot complete a circuit.
    771. Jewels and Stones 2019/5/20 Java Using array to store the existance of characters
    239. Sliding Window Maximum 2019/5/20 Java
    • Using PriorityQueue to store the elements with its idx within the window [O(nlogk)]
    • Using Deque to store the idx of elements within the window [O(n)]
    937. Reorder Log Files 2019/5/21 Java Sorting with customized comparator.
    46. Permutations 2019/5/27 Java Backtracking: enumerate every possibilities at each index
    31. Next Permutation 2019/5/27 Java find the element which is left of the last peak idx, then find the first element which is larger than nums[left] from the end. Swap them then reverse the array from the last peak to the end
    60. Permutation Sequence 2019/5/27 Java given an array with 1 to n. After idx i, there are (n-i-1)! permutations. Then we can compute the number at idx i one by one ( k / (n-i-1)! )
    1053. Previous Permutation With One Swap 2019/5/27 Java Reversed processing of Next Permutation. Find the bottom from the end firstly, the left element of the bottom is the element we need to change (called it bigger element). Then find out the first element which is slower than the bigger element from the end. Then swap them.
    526. Beautiful Arrangement 2019/5/30 Java Classical backtracking solution
    983. Minimum Cost For Tickets 2019/5/31 Java DP: res[i]represents the minimal costs at day i ending with 1-day pass([0]), ending with 7-day pass([1]), ending with 30-day pass([2]). Only update DP matrix for the day we travel, otherwise just directly copy the previous day's result
    42. Trapping Rain Water 2019/6/6 Java 2-way iteration:the first round is from left to right; the second round is from right to left
    703. Kth Largest Element in a Stream 2019/6/6 Java Easy minHeap (PriorityQueue) operation

    Linked List

    Question Done Date Code Note
    234. Palindrome Linked List 2018/5/22 Here Two Pointer, find half point in Linkedlist
    21. Merge Two Sorted Lists 2018/5/22 Here Two Pointer, Merge sort
    19. Remove Nth Node From End of List 2018/6/1 Here two pointers
    2. Add Two Numbers 2018/6/1 Here two pointers, advacend bit
    160. Intersection of Two Linked Lists 2018/6/1 Here Two pointers, finding entry point of the circular list
    141. Linked List Cycle 2018/6/1 Here Two pointers, one moves forward by 2 steps while the other moves forward by 1 step.
    142. Linked List Cycle II 2018/7/3 Here
    • Firstly, use fast-pointer & slow-pointer to find whether there are cycle in linkedlist
    • Then we find entry of that cycle by:
      • Start by head pointer and current slow pointer, they move forward by one step each time.
      • The node where they meet each other is the entry of cycle.
    237. Delete Node in a Linked List 2018/6/1 Here Set node's value to next node's value. Like the way we use to delete a value in the array
    206. Reverse Linked List 2018/6/1 Here Two ways: 1. recursion; 2. pinpoint tail, and then continuously move head to the next of tail, until tail is head.
    148. Sort List 2018/6/2 Here Merge Sort
    328. Odd Even Linked List 2018/6/2 Here put nodes in one list to another list
    23. Merge k Sorted Lists 2018/6/2 Here Priority Queue
    138. Copy List with Random Pointer 2018/6/2 Here Firstly, copy label and put new generated node right behind original node; Then copy random pointer; Finally, extract copied nodes and reset original list
    143. Reorder List 2018/6/22 Here
    • Find middle node and tail node
    • Reverse list from middle node to tail
    • merge two lists: one is from head to half, the other is leading by tail.
    147. Insertion Sort List 2018/6/23 Here Insertion Sort
    24. Swap Nodes in Pairs 2018/6/23 Here Operations on Linked List: Swap two nodes
    92. Reverse Linked List II 2018/7/1 Here Firstly determine start point and end point. Then reverse
    1019. Next Greater Node In Linked List 2019/6/6 Java Using Stack to store visited values with their idx. When we meet a new value, pop up the previous smaller elements, and update their result to the value of the current node.

    String

    Question Done Date Code Note
    408. Valid Word Abbreviation 2018/6/3 Here convert string to char array; Two pointers; Extract numeric string and convert it to number
    125. Valid Palindrome 2018/6/4 Here Two pointers, one is moving forward while the other is moving backward
    91. Decode Ways 2018/6/4 Here DP, edge cases, care about '0'
    387. First Unique Character in a String 2018/6/4 Here Using array to store appearance of lowercase character
    13. Roman to Integer 2018/6/4 Here Math logic
    340. Longest Substring with At Most K Distinct Characters 2018/6/4 Here
    • Two pointers to delimit substring;
    • HashMap to record how many different character appear in substring, and record number of appearances of each character
    76. Minimum Window Substring 2018/6/4 Here Same as above
    3. Longest Substring Without Repeating Characters 2018/6/4 Here Two pointers + Boolean array recording character appearing in s[slow:fast]
    344. Reverse String 2018/6/5 Here Easiest
    49. Group Anagrams 2018/6/5 Here HashMap; Firstly sort the string
    14. Longest Common Prefix 2018/6/5 Here Pointer to specify index we're at + vertical iteration and comparation
    28. Implement strStr() 2018/6/5 Here Using java built-in substring() and equals()
    20. Valid Parentheses 2018/6/6 Here Stack
    38. Count and Say 2018/6/6 Here Operation of StringBuilder
    8. String to Integer (atoi) 2018/6/6 Here Edge cases: 1. leading blanks; 2. '+' or '-'; 3. Integer overflow
    5. Longest Palindromic Substring 2018/6/6 Here Two pointers
    22. Generate Parentheses 2018/6/6 Here Backtracking
    17. Letter Combinations of a Phone Number 2018/6/6 Here Backtracking
    44. Wildcard Matching 2018/6/7 Here DP
    10. Regular Expression Matching 2018/6/7 Here DP
    224. Basic Calculator 2018/6/7 Here
    • Recursion
    • Or using math logics
    227. Basic Calculator II 2018/6/7 Here Stack, reverse polish expression
    772. Basic Calculator III 2018/6/7 Here
    • Recursion to solve embedded expression closed by '()'
    • Stack to solve operators with diffrent priority
    844. Backspace String Compare 2018/6/25 Here Go from tail to head. If meet '#', then skip previous non-'#' character
    242. Valid Anagram 2018/7/6 Here
      Two solutions:
    • 1. Sort two Strings, and then compare them.
    • 2. Using Array to store appearances of each character
    139. Word Break 2018/7/12 Here DP: DP[i] denotes whether we can break s[0:i-1]
    87. Scramble String 2018/5/14 Java DFS: Suppose we are standing at index i. string A is scramble string of string B if:
    • isScramble(A[0,i], B[0,i]) && isScramble(A[i, end], B[i, end]
    Or:
    • isScramble(A[0,i], B[end-i, end]) && isScramble(A[i, end], B[0, end-i]
    72. Edit Distance 2019/5/18 Here Classical DP: DP[i][j] represents the edit distance between word1[0...i) and word2[0...j)
    712. Minimum ASCII Delete Sum for Two Strings 2019/5/18 Here It is very similar to 72. EditDistance. Classical DP
    266. Palindrome Permutation 2019/5/27 Java If only one character appears odd times, then the string can be converted to a palindrome.
    267. Palindrome Permutation II 2019/5/27 Java Determine if a string can be converted to palindromes + backtracking to generate palindromes
    984. String Without AAA or BBB 2019/5/30 Java Greedy algorithm:
    • Always put the character which has left more into the result firstly.
    • If we've already put 2 consective identical characters, then put the other one instead.
    140. Word Break II 2019/6/6 Java
    • Used DP to find if we can break words. DP[i] stores all index j such that s.substring(j,i) exists in wordDict
    • Generated result strings using DFS

    Tree

    Question Done Date Code Note
    105. Construct Binary Tree from Preorder and Inorder Traversal 2018/5/28 Here logic behind preorder and inorder
    103. Binary Tree Zigzag Level Order Traversal 2018/6/8 Here Queue + boolean flag
    102. Binary Tree Level Order Traversal 2018/6/10 Here Using Queue to do BFS
    230. Kth Smallest Element in a BST 2018/6/10 Here Do Binary Search on BST. It's just like do DFS on BST, so that we can visit nodes in order. And we record how many nodes we have visited, and once we visited Kth node, we return it.
    94. Binary Tree Inorder Traversal 2018/6/10 Here Do DFS on Binary Tree. Visit left subtree firstly, then visit root, finally visit right subtree
    285. Inorder Successor in BST 2018/6/10 Here do recursion along with passing a upperRight node
    98. Validate Binary Search Tree 2018/6/10 Here From bottom to top. Firstly check left subtree, then check right subtree, finally check root.
    101. Symmetric Tree 2018/6/11 Here
    • Recursion.
    • isMirror(left.right, right.left) && isMirror(left.left, right.right) && left.val == right.val
    104. Maximum Depth of Binary Tree 2018/6/11 Here BFS using Queue
    108. Convert Sorted Array to Binary Search Tree 2018/6/11 Here Recursion + Property of BALANCED BST
    116. Populating Next Right Pointers in Each Node 2018/6/11 Here
    • Iteration. Do BFS
    • Recursion. connect Left Subtree, then connect right subtree, finally connect right boundary of left subtree with left boundary of right subtree.
    235. Lowest Common Ancestor of a Binary Search Tree 2018/6/11 Here Recursion + Property of BST
    236. Lowest Common Ancestor of a Binary Tree 2018/6/11 Here Recursion + From Bottom to top
    124. Binary Tree Maximum Path Sum 2018/6/11 Here
    • DP on Tree.
    • Recursive function returns local maximum of path sum which passed through root.
    • We passed a global variable in recursive function, where we possibly update global maximum.
    297. Serialize and Deserialize Binary Tree 2018/6/12 Here Borrow ideas from Heap
    127. Word Ladder 2018/6/14 Here Change one character in string to build a new string. BFS
    208. Implement Trie (Prefix Tree) 2018/6/21 Here Fundamental implementation of Trie
    872. Leaf-Similar Trees 2019/5/16 Using DFS to generate leaves string, then do comparison.
    851. Loud and Rich 2019/5/16 Java
    • the richness among people can be converted into a tree(using hashMap)
    • Then go through each person, populate the quietist person from top to bottom: If a node is quieter than the value which children nodes has stored, then update the answer for that children node and continue populating the result for the children nodes of that node
    6. ZigZag Conversion 2019/6/3 Java generate result strings level by level

    Graph

    Question Done Date Code Note
    207. Course Schedule 2018/6/13 Here Topo sort
    210. Course Schedule II 2018/6/13 Here Topo Sort
    841. Keys and Rooms 2019/5/15 Java
    • Firstly convert the input string to a hashMap <room : [keys]>, which represents a graph structure
    • Classic DFS, nothing special. Using a boolean array to determine if a room is visiting or not

    Math

    Question Done Date Code Note
    190. Reverse Bits 2018/6/18 Here
    • Iteration + Bit Operation
    • Divide & Conquer
    836. Rectangle Overlap 2018/6/25 Here Determined by relationship either between rec1's left-bottom and rec2's right-top, or between rec1's right-top and rec2's left-bottom
    69. Sqrt(x) 2018/6/30 Here Binary Search
    166. Fraction to Recurring Decimal 2018/7/6 Here 1. Using recursion to compute decimal 2. Using hashmap to deal with infinite circulating decimal
    149. Max Points on a Line 2018/7/8 Here
    • 1. Use HashMap to store "slope"
    • 2. Normalized diffY and diffX based on their GCD. And generated a String as key in the HashMap, inorder to deal with Double's precision problem.
    150. Evaluate Reverse Polish Notation 2018/7/11 Here Using Stack to store number we met. Each time we meet an operator, We do a computation on the top two numbers, then we push the result back to the top of stack.
    136. Single Number 2018/7/11 Here XOR
    137. Single Number II 2018/7/12 Here Bitwise + State Machine
    202. Happy Number 2018/7/12 Here Iteration + Using HashSet to record number we've met.
    957. Prison Cells After N Days 2019/5/23 Java Math : Find the cycle of states

    Matrix

    Question Done Date Code Note
    378. Kth Smallest Element in a Sorted Matrix 2018/6/12 Here Two ways:
    • PriorityQueue: Put element into PQ, along with each element, we also record their coordinates(x, y)
    • Binary Search: Just like the solution of 41. First Missing Positive, We do binary search on values space of elements in matrix
    130. Surrounded Regions 2018/6/13 Here DFS + Mark out node which's not killed
    329. Longest Increasing Path in a Matrix 2018/6/18 Here DFS + Memoization
    212. Word Search II 2018/6/19 Here Trie Tree stores dictionary, DFS searches words in mtx
    200. Number of Islands 2018/7/9 Here Two solutions:
    • 1. Using DFS to "clear" a island when we meet an new island. However, this solution requires us to modify the input grid map
    • 2. If we are not allowed to modify grid map, Get help from Union Find
    695. Max Area of Island 2019/5/14 Java Follow up to the number of islands. Using DFS to find an island and count the area, and eliminate it. Of course, if we are not allowed to modify the input matrix, we can use union find
    934. Shortest Bridge 2019/5/18 Java Another variance of Number of islands. Still using DFS to find islands. And because there are only 2 islands, we can mark the found island using '1' and '2'. Then using DFS to find the shortest bridge between 2 islands.
    675. Cut Off Trees for Golf Event 2019/6/2 Java
    • Using priorityqueue to sort the trees by their heights.
    • Cut the next tree one by one. Computing the distance between the current pos and the next tree's pos using BFS
    909. Snakes and Ladders 2019/6/2 Java BFS variance. Need to jump if a grid touch ladder or snake
    931. Minimum Falling Path Sum 2019/6/3 Java Classical DP

    Design

    Question Done Date Code Note
    295. Find Median from Data Stream 2018/6/22 Here Two PriorityQueues: maxHeap + minHeap
    155. Min Stack 2018/7/9 Here Each time we push a new item, we need to push current Minimal value alongside.
    146. LRU Cache 2019/5/15 Java
    • Bidirection linked list as container
    • Using hashMap to store key : node of linked list
    • the tail of linked list will be removed when cache is full
    • new coming value will go into the head of the list
    • The most recent visit value will be extracted from the list and put to the head of the list