Leetcode list(updating)

55 minute read

Published: July 29, 2019

LeetCode Question List

Question	Type	Description	Solution
1.Two Sum	HashMap	Return indeices of two numbers such that sum of them == target	Keep a HashMap and do a linear search, see if target - cur exists in Hashmap
2. Add Two Numbers	LinkedList	Add Two LinkedLists	Just traverse the linked list and add. Pay attention to different length of the numbers and carry on.
3. Longest Substr wo repting chars	Index moving	As the title	When we see a repeating character, we update the starting index. We use hashMap to keep the info of where each char first appear and use that to calculate the result.
4. Median of Two Sorted Arrs	Merge & sort	As the title	Just like a merge operation in merge sort. Pay attention to odd and even length of the array.
5. Longest Palindromic Substr (Practice)	Index moving	As the title	The question asks to return the palindrome. We need to find and keep the start and the length of the palindrome so we can rebuild it. Pay attention to multiple duplicate chars may appear in the center of the palindrome. Deal with them first and then update the index.
6. ZigZag Conversion	Implementation	Input: s = “PAYPALISHIRING”, numRows = 4 Output: “PINALSIGYAHRPI” Explanation: P I N A L S I G Y A H R P I (like a reverse N)	With extra storage: Just loop through the string, Keep track of the direction you’re going and keep a storage of chars in a row. In the end merge all rows in the result. Without extra storage: Add every character in a row at the same time to the result. You can calculate the gap of index given the shape and the number of rows.
8.String to Integer (atoi)	Implementation	Basically ATOI, but you have a lot of constraints.	Consider how to meet all the constraints in the simplest way when implementing the answer. Always check the requirement in the question. Ask yourself what else constrains or possibilities are implied by the question.
11. Container With Most water	Two pointer(Greedy)	Find the largest area determined by two values in the array	Moving the two index from the two ends, since the gap is always getting smaller, so we want the smaller value to be greater. We move the (left) pointer only when the right end is greater than the left end or otherwise (right).
15. 3Sum	Moving index	a+b+c == 0	Sort the array, we loop the array, keep arr[i] as the smallest number in the sequences and use two pointers l and r. When the sum is less or equal to target, we move l as long as the number at the point is the same as the one after. Same thing for the right side. We are taking advantage of the sorted sequence just like binary search. Pay attention to arr[i] larger than the target and duplicate arr[i].
16. 3Sum Closest	Moving indexUs	Almost the same as 3 Sum	We are looking for the closest sum right now. Change the way we’re updating the answer, and every procedure is the same as that in 3 Sum.
17. Letter Combinations of a Phone Number	DFS	Phone key combination	Keep a table of number to letters and then do DFS to find all combinations.
18. 4 Sum	Moving index	as title	Very similar to 3 Sum. Add one more layer of iteration. Difference is that we now have more exceptional cases to consider when doing the loops.
19. Remove Nth Node from end of list	Linked list	as title	Using two index, one pointing N elements ahead of the other, when the first one reach the end of the linkedlist, the other one is now pointing to the element to be removed. Notice that you should init the two pointers to point to the node before the first node.
20. Valid Parentheses	Stack	as title	When stack gets empty or stack top mismatches.
22. Generate Parentheses	DFS	as title	Keep a counter of left parentheses used and right parenthese to be used
23. Merge K Sorted Lists	Linked List	as title	Just like merge sort. This time, merging sorted lists. (Like a merge sort done in half actually) Pay attention to check null and pointed content when doing linked list problems.
24. Swap Nodes in Pairs	Linked List	Swap every two adjacent nodes and return its head.	Linked list implementation problem. To keep the index, find our the length first. Then do swap and index shifting every time.
25. Reverse Nodes in k-Group	Linked List	Reverse the numbers in group of K	You have to find the length first to do the iteration. Then do reverse in k iterations.
26. Remove duplicate in sorted array	Implementation	Remove duplicate, do the modification the same array and return the length afterwards.	Keep a index i of the modified array, when a non-duplicate found, increase i and copy the value to index i.
27. Remove element	Almost the same as 26
28. Implement strStr()	Implementation	Find first Occurence of a string	…
31. Next Permutation(VIP)	Implementation		See Post (& Last Permutation)
32. Longest Valid Parentheses(VIP)	Stack		See Post
33. Search in Rotated Sorted Array	Binary Search		Modified binary search. First Search for the turning point. The do modified binary search based on adjusted index.
34. Find First and Last Position of Element in Sorted Array	Binary Search	Exp. 1, 2, 3, 3, 4, 5. target=3 retrun=[2,3]	First time to find the start of the target sequence, just use normal lower bound technique. Then look for the lower bound of target + 1, which is the end of the target sequence. Be careful about updating l and r pointer when doing binary search and the exiting condition.
35. Search Insert Position	Binary Search		Lower_bound
36. Valid sudoku	Binary Operation		Use some arrays to store the status in each row, col, small block. The binary status represent which number is used in this area, updated using \| operation and when there is a number in this area and the & operation result is positive, return false.
37. Sudoku solver	DFS		Basic dfs and back-tracking. ONe technique is to preprocess the occupied info and gather all the points to be updated.
39. Combination sum	DFS	Given a set of candidate numbers and a target number , find all unique combinations in where the sum(numbers) == target	Basic dfs and back-tracking, since all possible combinations are required by the problem. Since it’s combination, you should track the last pos reached.
40. Combination Sum2	DFS	This time there are duplicates in the array	Just skip the duplicates when doing dfs.
41. First Missing Positive	Bucket Sort	smallest missing positive integer.	The original array can be used as a bucket since the index is set. and place every number in the array into the right place, and the missing number is the number that is first not in the right place.
43. Multiply Strings	Big number multiply		remember to remove leading zeros
44. Wildcard Matching(VIP)	String procecssing		Do a post on this
45. Jump game 2	Looks like DP, but can be solved by greedy	Your goal is to reach the last index in the minimum number of jumps.	Maintain the farthest point reachable right now and previous farthest reachable point, and update the steps and previous reachable point when reach the previous reachable point. The step count is the optimal (Since you are always trying to jump the farthest, farthest at each step => optimal!!!). See a dp-like question, ask yourself can I get an optimal solution just by making the greediest choice at each step?
46. Permutations	DFS	All permutations
47.	DFS	With duplicates in array this time	With extra space: Using a visited array to store the visited information. Without extra space: Sort the array first, then keep two pointers and do swap between the two pointers and dfs, just don’t do swaps when the two numbers are the same.
48. Rotate image	implementation	inplace rotation	Do swap (swap mat[i][j] and mat[j][i]) then reverse
49. Group Anagrams	Hashmap	group all the anagrams	Sort the current word and add to map, add the other words with same permutation to map then do retreival from map to form the final answer.
50.pow(x, n)	Implementation		Just do fast pow, but be careful about some special cases as the range of inputs is integer
51.N-Queens	DFS	return board	classic back-track question
52.N-Queens 2	DFS	return number
53. Spiral matrix(Practice)	Implementation		Moving in four directions and change range accordingly. Pay attention to the stopping conditions and range checking
55. Jump Game	Greedy		Similar solution to Jump Game 2. The only change is that you check whether maxJump is greater than the end of the array.
56. Merge Intervals	Sort & Implementation	Merge all overlapping intervals	Sort first according to the starting point. Then compare the starting point with end of the result sequence.
57.Insert interval		insert and merge	Keep a new vector/ArrayList of the resulted intervals. Update the ends of the new interval based on the original intervals in the array. If the interval has no overlap with the new interval then just add it.
54. Spiral Matrix2 (Practice)	Implementation		Instead of traversing a given array, you should generate an array. Almost the same solution as the first one.
60. Permutation Sequence(VIP)	(Obviously you can’t use DFS here)	The k th permutation	Do a post on this question.
61. Rotate List	Linked List	Rotate the linkedlist by k places	Inplace solution: Make the original linked list into a loop and then cut at kth place. Or you can create a list and move the last k elements to the new list and then merge.
62. Unique Paths	DP (Summing)	All unique paths moving accross a checker-board	The base case is that the robot can move to every point in the graph with at least one unique path. The original dp expression would be f[i][j] = f[i][j - 1] + f[i - 1][j]. However, we can determine that f[i - 1][j] is the sum of f[i - 1][0] to f[i - 1][j - 1]. So we can remove the dimension of i by just suming f[j] = f[j - 1] for N times. Since each summing has included the sum from the last row.
63. Unique Paths 2	DP(Summing)	Obstacles placed	When an obstacle appears, f[j] = 0, that’s the only difference.
64. Minimum Path Sum	DP	top left to bottom right	f[i][j] = min(f[i - 1][j], f[i][j - 1] ) + w[i][j] Make sure that you init all grids except for those around the starting block to the MAX value.
65. Valid Number	Implementation	…	Too complicated
66. Text Justification	Implementation	…	Just pay a lot of attention to details and have a clear understanding of what you’re trying to write right now.
71. Simplify Path	Implementation with stack	Simplify an absolute path	Path attention to the rules. Use stack to deal with '..’
72. Edit Distance	dp	classical question	f[i][j] = f[i - 1][j - 1] when chars equal, f[i][j] = min(f[i][j - 1], f[i - 1][j - 1], f[i - 1][j]) + 1. Make sure to init f[i][0] and f[0][i] to corresponding is since the base case is to delete every letter when the length is 0.
73. Set Matrix Zeros	Implementation	Given a m x n matrix, if an element is 0, set its entire row and column to 0.	Add some bool marks to check whether the row should be set zero. Store the information about which row is the last zero row. Do not update the last zero row to all zero at first, since we are using the last zero row to store the info about which column to clear. Then use info in the last zero row to update the column case. In this way, we can do the operation in place.
74. Search a 2d matrix	Binary Search	Write an efficient algorithm that searches for a value in an m x nmatrix.	First you search which row the target belongs to, and then you. Then Search for the target in the row.
75. Sort colors	Implementation		Write a merge sort or just can use bucket sort.
76. Minimum Window Substring	Sliding window like problem	Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).	First record the count of each character in the target array. Then we keep two pointers and do updates on the count. The key is to keep a temp to find out how many letters we have not found in the source array. If we still have not found the required array, move end pointer forward (the longer, the more possible that it contains all the letters), then we try to minimize the length by moving start forward.
77. Combinations	DFS	return all possible combinations of k numbers out of 1…n	Just modified DFS from finding all combinations. Besides recoding the last position, you should also keep track of what numbers are used since we are not asked to use up all the numbers.
78. Subsets	DFS	Given a set of distinct integers, nums, return all possible subsets (the power set).	Sort the array and just push back every combination you visit.
79. Word Search	DFS	Find a work in a 2d board	Just do normal dfs, but one smart update method is to set the grid to some value that may not exist in the word so we don’t need to keep an extra array of visited nodes. Remember to do border check.
80. Remove duplicates from sorted array 2	implementation	remove duplicates in place, appear at most twice	just keep a counter and do remove.
81. Search in Rotated Sorted Array 2 (VIP)	Binary Search	With duplicates right now.	Do a post
83. Remove Duplicates from Sorted List	Linked List		Compare current to the next of current. then update next if equals or shifts when not equals.
82. Remove Duplicates from Sorted List2	Linked List	Remove any numbers with duplicates.	keep a pointer to the previous value and while the next value equals the duplicate value, remove it.
84. Largest Rectangle in Histogram	Greedy	Largest rectangle formed	We are trying to find the values as large as possible, so we use a stack that keeps an increasing sequence of values looped in the array. Then we do the pop option when the stack is not empty and the current value is samller than the top of the stack. Then calculate the area. If stack is empty use the stack top height times i, else use the last highest value to time the gap.
85. Maximal Rectangle (VIP)	DP		Do a post on this problem
86. Partition List	LinkedList	Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.	create two Linkedlist head and add values to them correspondingly. Merge them in the end.
88.Merge Sorted Array	Implementation & Sorting	Easy question
89.Gray Code	DFS	Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0	The constraint in the problem is that the bit representation of consecutive codes only differs in one bit. At each stage of the dfs, we have two choises: change the bit at 1 « n or not. Use xor operation to change the resulting code by one bit each time.
90. Subset2	DFS	Now with duplicate	Just deal with duplicate when iterating in each round.
91. Decode Ways	DFS/DP	Given a non-empty string containing only digits, determine the total number of ways to decode it.	A-Z is representedy by 1-26. DFS: Just do dfs to find out different sequences, try to do partition (single digit or two digits) at every round, and sum up in the End. DP: f[0] = 0. if (s[i] > ‘0’) f[i] += f[i - 1]; calculate two digit sum => if (s[i - 1] != ‘0’ && num <= 26) f[i] += f[i - 1]; else f[i] ++; Special case: The sequence start with zero => no way to decode.
92. Reverse Linked List2	Linked List	Reverse a linked list from m to n, only in one pass	First go to the place where index is m, maintain the prev reference of m index. Then move each element visited (cur->next) from m to n to the m index. The list is then reversed.
93. Restore IP address	DFS	Restore possible IP address from seqence	Record how many dots have added, and the current position reached. Then do partion and condition checking (check sum <= 255). Note that no parts should start by zero.
94.Binary Tree Inorder Traversal	DFS	inorder traversel	Dfs print Dfs
95.Unique Binary Search Tree2	DP	See posts
96. Unique Binary Search Tree	DP
97. Interleaving String	DP	Given s1, s2, s3, find whether s3 is formed by the interleaving of s1and s2.	See post
98. Validate BST	DFS		A valid BST => cur node >= all left && curnode <= all right. However, actually checking that the cur node is greater or smaller than the max or min from one side is enough. If check from right first, then cur node should be smaller than the min from the right side. Then we go on to check the left side. The tree is a mono-increasing/decreaseing going from left to right, so we are just checking if the tree is strictly increasing/decreasing from left to right or from right to left.
99. Recover Binary Search Tree	DFS and implementation	Two values are swapped, do not change the tree structure and reconstruct the tree.	Brute-force method: Traverse the tree and store all the nodes with value in an array. Sort the array and put the values back. A better method: Do inorder traversal (left to right) and recorde the previous node. If previous value is not smaller than the current value, then we do a swap.
101. Symmetric Tree	DFS and implementation
102. Binary Tree Level Order Traversal	BFS and queue
103. Binary Tree Zigzag level order traversal	BFS	Given a binary tree, return the zigzag level order traversal of its nodes’ values.	BFS: Two queues (make sure same level) and reverse the index DFS: Make new arrays when level increases. Add to different places given the layer number.
104. Maximum Depth of Binary Tree	DFS	easy question
105. Construct Binary Tree from Preorder and Inorder traversal	DFS	Given preorder and inorder traversal of a tree, construct the binary tree.	The root is at the start in the preorder array, then we look for the index in the inorder array, and do partition and reconstruct from the parts recursively. We need to pass down the index of the range(left, right) in both arrays.
106. Construct Binary Tree from Inorder and Postorder traversal	DFS	as above	The root is at the end in the postorder array, then we look for the index in the inorder array. Same as above.
108. Convert Sorted Array to Binary Search Tree	DFS	Given an array where elements are sorted in ascending order, convert it to a height balanced BST.	Starting from the mid of the array, construct the partitioned left and right recursively. In this way the tree is balanced.
109. Convert Sorted List to BST	LinkedList DFS	Difference is that now there is a linked list.	Partition the array with slow-fast pointer method.
114. Flatten binary Tree to linked list (practice)	LinkedList BFS/DFS		while loop, if left is not null, rotate left to top, then go to right side.
115. Distinct Subsequences	DP	Given a string S and a string T, count the number of distinct subsequences of S which equals T.	A modified version of the longest common subsequence. This time we are not counting the max number but we are counting the total number. f[i][0] = 1 (s idx, t idx, t length == 0 case). if (s[i - 1] == t[j - 1]) f[i][j] = f[i - 1][j - 1] + f[i - 1][j] else f[i][j] = f[i][j - 1];
116. Populating next right pointers in each node	Linkedlist	Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to `NULL`.	None-dfs: current node pointer, previous node pointer. Connect the children first and move to the sibling in the same layer, and then do connect. When the layer is finished, move previous to the left. DFS: Connect left child and right child, then recursively connect the leftleft, left right, leftrightrightleft etc. recursively. Queue: push the nodes into a queue, connect them, and push their children into the queue. (uses two queues.)
117. Populating next right pointers 2(practice)	LinkedList	The binary tree is not perfect now	Create a temporary linkedlist (temporary pointer) for each children layer for the ease of linking traversing. Connect childern nodes and then move on to its sibling.
120. Triangle	DP	Minimum path down the triangle.	f[i][j] = min(f[i + 1][j], f[i + 1][j + 1]), from bottom to the top, in this way we can use the original array to do the calculation.
121. Best time to buy and sell stock		buy sell once	Difference between the highest and lowest.
122. Best Time to Buy and Sell Stock II		As many times	Add up all the positive differences between the days.
123. Best Time to Buy and Sell Stock III	Greedy	At most two times	Decide on four factors: By for the first time on this day, buy1 = max(buy1, 0-p[i]) sell on this day sell1 = max(sell1, buy1 + p[i]) Same for the second transaction.
124. Binary Tree Max Path Sum	DFS		First get the max path sum from left branch, then from right, update the max(sum of the path sums) , then return root->val + max(l, r) max path sum from this branch.
125. Valid Palindrome		Easy question
126. Word Ladder2 (practice)	DFS/BFS	Shortest transformation path from the beginning word to the end word. One letter changed a time, word must be in word list	DFS/BFS, change one letter, pay attention to duplicate handling. Difficult implementation
127. Word Ladder	DFS		No need to return the detailed path.
128. Longest Consecutive Sequence		Find in O(n) time	Put all numbers into a set, then center around the number, find and erase consecutive numbers from the set (both larger and smaller).
129. Sum Root to Leaf Numbers	DFS		sum left tree and right tree recursively. But the sum is now digit sums.
130. Surrounded Regions	DFS	Mark all surrounded Os to Xs except for bordering regions	Just normal DFS but the trick is that instead of directly looking for surrounded Os you are starting from the bordering regions, and mark the bordering regoins with some marks. Then mark all the Os remaining with Xs. Pay attention to edge cases where there is only one row or one column.
131. Palindrome Partitioning	DFS	Given a string s, partition s such that every substring of the partition is a palindrome. Output all the results.	DFS, we should know the current position. Then we look for palindromes between left and right(pos and i), then we do the partition and make the recursion goes on, then back-track after reach the end.
132. Palindrome Partitioning 2	DP	Minimum cuts	We keep a record is_palindrome[i][j] to improve efficiency. We check if the subarray between i and j is a palindrome (s[i]==s[j] && (i - j < 2\|\| is_palindrome[i - 1][j + 1]). if so, we update the counting. cnt[i] = min(cnt[i], cnt[j - 1] + 1), where cnt[i] is initially set to i; if j reaches 0,then cnt[i] is 0, the subarray 0-i is a palindrome.
134. Gas Station	Implementation	There are N gas stations along a circular route, where the amount of gas at station i is `gas[i]`. You have a car with an unlimited gas tank and it costs `cost[i]` of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.	Actually you just start at every station, then go forwrd until the remaining gas is zero or return the starting index if the cirle is finished. The optimization is that you jump j steps forward because starting at any station in this range will case remaining gas to be zero.
135. Candy (VIP)	DP	There are N children standing in a line. Each child is assigned a rating value. Each children must have at least one candy. Chilren with higher rating get more than neighbours. Minimum number of candies.	Two pass Solution => First nums[i] = nums[i - 1] + 1 if the rating is greater than that of previous person. Then going backward, if the previous person rates greater, nums[i - 1] = max(nums[i - 1], nums[i] + 1). In this way, we fix the relationship from both ends, and make sure that every one has more than their neighbors on both sides.
136. Single Number	Implementation/Bit operation	All twice but only once	Bit operation, do xor on all numbers and the final result is the number
137. Single Number II	Implementation/ Bit operation	All three times but once	Count the appearance time of each bit, if mod 3== 1, it belongs to the number we are looking for.
138. Copy List with Random Pointer	DFS + LinkedList	A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list.	To take advantage of the random pointer, so we have to put a map of the points we have visited (map original to new node). Recursively rebuild the next and random pointer. if the current node already exists in the Hashmap, return the copied node.
139. Word Break	DP	Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. The same word in the dictionary may be reused multiple times in the segmentation.	Actually it’s like a packing problem. f[i] = f[j] + w[i] (0<=j<= f[i] - c[i]). And each good can be used multiple times. However, here we use f[i] to denote that whether the staus is reachable. if (f[j] && substr(j, i - j) exists in dict), then it’s reachable.
140. Word Break2	DFS	Find all the combinations now.	Partition and search.
141. Linked List Cycle	Linked List	Check cycle in linked list	fast slow pointer.
142. Linked List Cycle II	Linked List	Return the node where the cycle begins.	first check cycle, then reset the slow pointer to the head. Move the fast and slow at the same speed, when they meet, the start of the cycle is there.
143. reorder list(practice)	LInked List	Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…	First use fast slow pointer, then reverse the second half and insert it into the first half. One trick to ease the reverse process is to add a stack and pop from the stack.
144. BT preorder 145. BT postorder
146. LRU cache		Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: `get` and `put`. O(1) get time complexity	Maintain a queue and a counter in order to maintain the order the elements are visited while keep track of the least recently used element. Also we should know how many new elements are added. When the capacity is exceeded, we pop from the queue while cnt[q.front()]. When we reach a cnt[q.front()] == 0, we remove the element from the table.
147. 148. List Sorting		You need to parctice list-related question more.
150. Evaluate Reverse Polish Notation	Expression eval/ Stack		Push elements into the stack. Whenever you reach a operator, do the caculation.
151. Reverse words in a string	Implementation	Trim and remove duplicate spaces	Pay attention to implementation details.
152. Maximum product subarray	Greedy	Given an integer array `nums`, find the contiguous subarray within an array (containing at least one number) which has the largest product.	Keep current max/min, previous max/min, curent max/min comes from max/min of previous max/min times the current number, and don’t forget to compare with the current number(might be even larger), then update information stored.
153. Find Minimum in Rotated Sorted Array	Binary Search		Just search for the point where the array is rotated.
154. Find Minimum in Rotated Sorted Array2	Binary Search	With duplicates	The update is that move the left end and right end one forward one when nums[mid] == nums[right]
160. Intersection of 2 linked list	Linked List	Find the intersection point of 2 linked lists	First get the lenght of two linked list, Then move the gap between the two linked lists, then move the pointers together and find the point that intersects.
164. Maximum Gap (VIP)	Bucket & Mapping	Given an unsorted array, find the maximum difference between the successive elements in its sorted form.	Make a post on this problem
166. Fraction to Recurring Decimal	Implementation	Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.	There are just a lot of cases to consider. First of division by zero, sign, parts that is not fraction.First convert all the number to long, then look for the remainder of the division. The remainder is where fraction is caused. Calculate each digit of the fraction by division and modding. Then we maintain a set to find whether a remainder(will cause the same pattern to occur) appears again.
173. Binary Search Tree Iterator	DFS	Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.	A inorder traversal implemented by stack is used. First go to left and push every element into the stack. Then pop from the stack, then go to right.
179. Largest Number		Given a list of non negative integers, arrange them such that they form the largest number.	Sort the list first in dictionary order. Append them altogther into a string. Then remove the trailing zeros in the string. If in the end the string is empty, return 0.
174. Dungeon Game	DP	Whether the prince can rescue the princess by walking down or right in a grad. Will lose or win some points at each node. Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.	f[i][j] = min(f[i + 1][j], f[i][j + 1]) - val[i][j], initial values at each end are set to 1, and others are INT_MAX. Since the knight needs at least one health to survive. After calculation, if f[i][j] is less than zero, we reset it to 1(need at least one life, this will happen when there are too many magic orbs). Finally we are back to f[0][0] and this is the result.
188. Best time to buy and sell stock 4	DP (Based on question3)	Design an algorithm to find the maximum profit. You may complete at most k transactions.	Decision to do the k th buy or sell on each day. Actually very similar to the third question in this series. f[j][0] = max(f[j][0], f[j-1][1]-prices[i]) // buy f[j][1] = max(f[j][1], ddf[j][0]-prices[i]) // sell
198. House Robber	Easy DP	the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.	f[i][0] = max(f[i - 1][1])f[i][1] = max(f[i - 1][0] + val[i], f[i - 1][1])Can use two variables to reduce dimension of f.
199. Binary Tree Right Side View	Tree DFS	Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.	Always visited right might not lead to right answer since the tree is not necessarily complete. BFS or DFS can easily solve the problem by selecting the rightest element in the level. (Modified level-order traversal)
200. Number of Islands	DFS	Connected ones.
201. Bitwise and of numbers range	bit operation	Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
202. Happy Number	Implementation & linked-list like trick	19->1^2+9^2=82-> … -> 1	Implement sum of digit squares. Then do fast slow pointer like operation to find a cycle(this is the trick). One number do the operation twice each time.
203. Remove Linked List Elements	Linked-list & Implementation	Remove all elements from a linked list of integers that have value val.	nothing to say…
205. Isomorphic Strings	Map & Implementation		Use map to store each match, then find contradiction.
206. Reverse Linked List	Linked-list & Implementation
207. Course Schedule	DFS/Implementation	Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?	Topological sort
208. Trie(Practice)	Trie
210. Course Schedule	DFS	Return the list of course
211. Add and search word	Trie
212. Word Search2(Practice)	DFS + Trie	Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.	Now you have a list of words, so first build a trie with these words. Then dfs on the board with the trie.
213. House Robber 2	DP	Determine the maximum amount of money you can rob tonight without alerting the police. It will automatically contact the police if two adjacent houses were broken into on the same night.	f[i + 1] = max(f[i - 1] + nums[i], f[i]). But the problem can be solved without using extra stroage space. Just use pre, cur to denote f[i - 1] and f[i], then update pre and cur. Also notice that the thief can either start at the first or start at the second house. (Two base cases) So you should do two loops.
214. Shortest palindrome (VIP)	DP	Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.	Brute force is to find the longest palindrome prefix, then add the remaining part to the start of the string. But the more efficient way is to solve with KMP. Because the palindrome prefix will appear again at the suffix in the combined string, so we can know the longest palindrome prefix by knowing the kmp table index of the last char in the combined string. If adding from back, we just look for such a substring in the reverse order.(Tricky and smart solution!!!)
215. Kth largest element in the array	Kth-select		Notice that as the array is sorted in the increasing order, the kth largest element is the size-k element in the array.
216. Combination Sum 3	DFS	Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.	normal combination dfs.
218. The Skyline Problem (VIP)		Key points of a city silhouette. Given the buildings starting and ending index and the height.	Do a post on this problem
220. Contains Duplicate 3 (VIP)	Sliding window	Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k **.	Brute force is to go through the array and compare each pair of the numbers. But we notice that the difference between i and j is at most k, so we can konw that this problem is a sliding window problem. The key is to update an sequence(store in a sorted set) and try to find out the whether the newly added value is within t to any value in the window.
223. Rectangle Area	Implementation	Find the total area covered by two rectilinear rectangles in a 2Dplane.
224. Basic Calculator	Expression eval	Implement a basic calculator to evaluate a simple expression string. Only plus and minus	Op and num stack(Used for parentheses).
225. Implement Stack using queue	Implementation		When adding, push the new element in, then pop and push back every element in the original array in until the latest added element227(equivalent to adding to the front)
227. Basic Calculator 2	Expression eval	With mult and div now	Op and num stack(Used for parentheses).
229. Majority Element 2	Implementation	Given an integer array of size n, find all elements that appear more than `⌊ n/3 ⌋` times.	Solution with extra space: Use a map to count the occurences of different numberes. A better way is to sort the numbers and thencount the number of duplicate elements in a row.
230. Kth smallest element in a BST	dfs		Inorder traversal and keep a counter
232. Implement Queue using Stacks	Implementation		Two stacks. One store in original order, one stored in reversed order. When getting the top of the stack, pop and push the elements in the original stack into the stack that stores the reversed stack.
233. Number of digit one (VIP)	Implementation, math	Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.	do a post
234. Palindrome Linked List	Implementation	Given a singly linked list, determine if it is a palindrome.	First find the half of the list, then reverse the second half of the list, then compare the reversed list with the first half.
235. LCA in a binary search tree	DFS		If root value is smaller then both target, go to the right side, else if root value is greater than both target, go to left.
236. LCA in a binary tree		Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.	post order traversal. If we meet the target values, return the values, else the returned value will be null.
237. Delete node in a linked list			Delete without reference to the previous element: copy the value of the next node to the current node and then delete the next node.
239. Sliding Window Maximum			Typical sliding window problem. Maximum value in each window. A priority queue will be a preliminary optimization.
240.Search a 2D Matrix 2	Implementtion	Write an efficient algorithm that searches for a value in an m x nmatrix. This matrix has the following properties: Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom.	You can’t do binary search in this problem because the values are not sorted between different rows. More like moving either down or left in the array. Starting from the first row and last column (largest in this row), if the current element is larger than target, move leftwards. If the current element is smaller than the target, move downwards.
241. Different Ways to Add Parentheses	DFS		The key is that when parenthses is added, the equation is divided into two parts, then recursively calculate the left and right resuls.
243. Shortest Word Distance(paid)	Implementation	Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list. (difference in index)	Record pos1 and pos2 and then calculate the distance. Update pos1 and pos2 and distance as you loop through the array.
244. Shortest Word Distance 2		The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?	Use a map to store the places where each element appears, then calculate the minimum distance between each pair of the index.
245. Shortest Word Distance 3		The two words may be the same	Just add another contition to the first problem. Now we are also considering whether cases when two words are the same.
246. Strobogrammatic number		A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).	Map the numbers that have a valid transformation (69180) then check if the hash of nums[i] equals nums[len-i-1]
247	dfs	Find all strobogrammatic numbers that are of length = n.	Regular dfs, notice that 6 and 9 can’t be placed in the middle and 0 can’t be put at the first place
248	Dfs	Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.	Still dfs, but count the number. The number may be large, use long
249 group shifted strings	Hashmap	Given a string, we can “shift” each of its letter to its successive letter, for example:”abc” -> “bcd”. We can keep “shifting” which forms the sequence:	Create a hashfunction using gap between letters for those in a group.Then return the value set.
250. Count univalue trees		Given a binary tree, count the number of uni-value subtrees. Subtrees with the same values.	Post order traversal, if the node is a leaf, it is a valid subtree. If left is true and right is true and root->left value and root->right equals root->val. (check null first)
238. Product of Array except self	Prefix sum	Given an array `nums` of n integers where n > 1, return an array `output` such that `output[i]` is equal to the product of all the elements of `nums` except `nums[i]`. No division and O(n)	First, you should think of something like prefix sum when you are to find out the sum or product of a sequencea and the information should be used multiple times. Then it’s the tricky part. To do the multiplication without dividing the current number, it’s yet simple: find the left and right prefix multiplication to the current value and then multiply them together.
222. Count Complete Tree Nodes	DFS		easy problem
228. Summary ranges	Implementation problem	Given a sorted integer array without duplicates, return the summary of its ranges. [0,1,2,4,5,7]->[“0->2”, “4->5”, “7”]	Quite a easy problem, but pay attention to dealing with the last element.
221. Maimal Square	DP	Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.	The brute force solution is to find a point in the matrix and then expand the length of the square and check if all the points on the newly added boundary is all 1. But the problem can be solved in a dynamic programming way (Take advantage of the already found squares): if (mat[i - 1][j - 1] == ‘1’) f[i][j] = min(f[i - 1][j - 1], f[i][j - 1], f[i - 1][j]) + 1, result = max(result, f[i][j]); else if (mat[i][j] == ‘0’) f[i][j] = 0 And as usual, the optimization is to store the f[i - 1][j - 1] in a variable prev. Then we can reduce the dimension to f[j].
981. Time Based Key-Value Store	HashMap	Create a timebased key-value store class `TimeMap`, that supports two operations. set key, value, timestamp, get key, timestamp, to get the value which has the largest timestamp that is no greater than the query timestamp.	We can use a map to store keys and list of added elements, Then we use binary search (lower bound) to look up for the element we want in the mapped list. Or in java, use Treemap instead of a list and do binary search.
983. Minimum Costs For Tickets	DP	In a country popular for train travel, you have planned some train travelling one year in advance. The days of the year that you will travel is given as an array `days`. Each day is an integer from `1` to `365`. Train tickets are sold in 3 different ways: a 1-day pass is sold for `costs[0]` dollars; a 7-day pass is sold for `costs[1]` dollars; a 30-day pass is sold for `costs[2]` dollars.	First mark all days with a travelling plan with some number, then if (marked) : f[i] = min(f[i-1] + cost[0], f[i - 7] + cost[1], f[i - 30] + cost[2]); else: f[i] = f[i - 1], then return f[lastday with a travel plan]
950. Reveal Cards in increasing order	IMPL+DFS	In a deck of cards, every card has a unique integer. You can order the deck in any order you want. Initially, all the cards start face down (unrevealed) in one deck. Now, you do the following steps repeatedly, until all cards are revealed: Take the top card of the deck, reveal it, and take it out of the deck. If there are still cards in the deck, put the next top card of the deck at the bottom of the deck. If there are still unrevealed cards, go back to step 1. Otherwise, stop. Return an ordering of the deck that would reveal the cards in increasing order.	The problem is presented in a recursive manner. Then we can figure out the index of the numbers given the number of cards, and place the sorted array into the corresponding index. f(0) : (0), f(1):(0, 1), f(2): (0, 2, 1), f(3): (0, 3, 1, 2), f(4): (0, 3, 1, 4, 2 ). From f(n - 1) to f(n), we do this: Set every p[i + 2] tp p[i] + 1 for every i between 0 and n-3. Then set p[1] to the original p[n - 2] + 1.
948. Bag of Tokens	Looks like a DP problem, but is actually more simple: Greedy+two pointers.	You have an initial power `P`, an initial score of `0` points, and a bag of tokens. Each token can be used at most once, has a value `token[i]`, and has potentially two ways to use it. If we have at least `token[i]` power, we may play the token face up, losing `token[i]` power, and gaining `1` point. If we have at least `1` point, we may play the token face down, gaining `token[i]`power, and losing `1` point.	An apparent strategy is to select tokens as small as possible to earn more points, then if the current token is greater than the total power, we flip the largest tokens face down, gaining the most power possible and then try to add more points by facing the tokens up.
947. Most stones removed with same row or col	Actually this is a counting island problem. Solved by DFS or Union-find	On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone. Now, a move consists of removing a stone that shares a column or row with another stone on the grid. What is the largest possible number of moves we can make?	First of all, create two maps which map each x or y coordinates to the points with that x or y coordinates. Then we do dfs on the points. The neighbours of the points are those who have the same x or y coordinates as it. The number to remove is the total number minus the number of islands. Or we can use union find. We try to merge the points with the same x or y coords, put them into different sets, then we can get the count of sets, which is the number of islands.
946. Validate Stack Sequences.	Greedy & Stack & two pointer	Given two sequences `pushed` and `popped` with distinct values, return `true` if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.	Two pointers: i for the pushed array, j for the popped array. First we push the elements in the push array into the stack, move i forward. Then if we see a match in the pop stack, we pop the top element in the stack, move j forward. After we have moved to the end of the pushed, we pop the elements from the stack and while it matches the popped array. Finally we see whether the stack is empty and we have reached the end of the popped array.
945. Minimum Increment to make array unique	HashSet & greedy	Given an array of integers A, a move consists of choosing any `A[i]`, and incrementing it by `1`. Return the least number of moves to make every value in `A` unique.	First we sort the array, Keep a visited array, then we check whether we have the current element in the set. If so, we set A[i] to A[i - 1] + 1, then add A[i - 1] - A[i] + 1 to the result. The best way to tackle duplicate subarray is to make them into a consequtively increasing array. However, we might encounter conflict. That’s why we are keep a Set of visited array. When we encounter a conflict, we can be certain that the end of the previous incremented subarray is greater than the current element, since the array is sorted. So we add A[i - 1] - A[i] to the total moves to cover up for the conflict.
974. Subarray Sums divisible by K	prefix sum & Hashmap	Given an array `A` of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by `K`.	We keep a prefix sum mod by K, and we put each sum to the map. We add the count of the sum in the map to the final result each time since every pair of the points with the same prefix sum mod by K can form a new subarray divisible by K.
988. Smallest String Starting from leaf	DFS		Traverse the whole tree in a preorder manner and keep updating the result.
978. Longest Turbulent Subarray	Two pointer, impl	A subarray `A[i], A[i+1], ..., A[j]` of `A`is said to be turbulent if and only if: For `i <= k < j`, `A[k] > A[k+1]`when `k` is odd, and `A[k] < A[k+1]`when `k` is even; OR, for `i <= k < j`, `A[k] > A[k+1]`when `k` is even, and `A[k] < A[k+1]`when `k` is odd. Return the length of a maximum size turbulent subarray of A.	Keep a starting pointer and an ending pointer. A subarray must be continuous, so we stop when the current element does not satisfy the requirement, Remember to update the length at the end of the array. Also , for arr[i] == arr[i - 1], starting and end is the same, and the length is 1. (A continuous part that does not satisfy the requirement.)
987. Vertical order traversal	HashMap + DFS + IMPL	For each node at position `(X, Y)`, its left and right children respectively will be at positions `(X-1, Y-1)` and `(X+1, Y-1)`. Running a vertical line from `X = -infinity`to `X = +infinity`, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing `Y` coordinates). If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.	First, traverse the tree and give every node a coordinate(x, y), then add points to hashmap which map x coords to points. Then sort each list of points mapped by x by their y index. x is index, y is level.
785. Is Graph Bipartite?	Search(BFS, DFS)	Is the graph binary colorable	Assign color alternatively to each node and check for collisions
979. Distribute Coins in Binary Tree	DFS	Given the `root` of a binary tree with `N`nodes, each `node` in the tree has `node.val`coins, and there are `N` coins total. In one move, we may choose two adjacent nodes and move one coin from one node to another. (The move may be from parent to child, or from child to parent.) Return the number of moves required to make every node have exactly one coin.	For each node in the tree, it only keeps one coin and gives what it has to the children nodes. We keep the add dfs(left) and dfs(right) to the answer, and we reutrn dfs(left) + dfs(right) + val - 1. When the value is positive , it represents moving coins to the children. When it is negative, it represents moving coins to the parent. We count the absolute values.
761. Special Binary String	Divide and Conqure	The number of 0’s is equal to the number of 1’s. 1’s count >= 0’s count in any prefix. Swap some special consecutive substrings to make the string lexicographically largest.	For each level of recursion, the string ranges from l to from l to r, keep a temporary subsum of 1 and 0s, if the subsum is zero (same number of 0 and 1s)，Swap 1 foward and put the 0 backward, then recusively do the recusion between l + 1 and i - 1.push the sub to the end of an array and then sort and integrates the outcome.

Share on

Twitter Facebook LinkedIn

Lixing Liu / 刘励行

Leetcode list(updating)

Share on

You May Also Enjoy

New 21 game

解题记录 1

Largest Sum of Averages

背包笔记

应用层学习笔记