Leetcode Exercise Diary
#4.
Median of Two Sorted Arrays (◊◊◊◊◊)
This problem is hard. Even in the second round of exercise, I still needed to copy the standard answer and could not write it without looking at the solution.
Key idea: Find the (m+n)/2'th largest number, the divide-and-conquer strategy is to eliminate m/2 or n/2 smallest elements.
Key point: compare nums1[m/2] and nums2[n/2]
Details: 1. k is odd or even; 2. let nums1 shorter than nums2; 3. if k==1; 4. if m==0; 5. eliminating means to delete from the array; 6. better use recursive.
#10. Regular Expression Matching (◊◊◊◊)
First round note:
Use DP. This kind of two string matching problems shares the same DP format with LCS. The array is 2d. f[i][j] means the result of the substring ending at i-1 and j-1. The total size is f[m+1][n+1].
A two-layer loop is needed. i and j moves independently. The recursion equation should be designed carefully. The initial status should be initialized carefully: f[i][0] and f[0][j].
For this question, if no '*' appears, i and j moves together; else if '*' appears, f[i][j] = f[i][j-2] or f[i-1][j]. This is the crucial point. Without DP, in O(n), we cannot express this 'OR'.
To solve this problem, first we should figure out that the 'OR' exists, i.e. when 'a*' appears, a may repeat one or more times, 'OR' zero times. And the case when 'a' repeats more in s than in p can be unified to this: each time it decides to advance, it may also stay. At some point, only one of these two possibilities is true. Recursion can solve this, or DP.
bool isMatch(string s, string p) {
int m=s.length();
int n=p.length();
if(m==0&&n==0)return true;
//else if(m==0||n==0)return false;
vector<vector<bool>> res (m+1,vector<bool>(n+1));
res[0][0]=true;
for(int i=1;i<=m;i++)
res[i][0]=false;
res[0][1]=false;
for(int j=2;j<=n;j++)
if(p[j-1]=='*')res[0][j]=res[0][j-2];
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(p[j-1]!='*'&&(s[i-1]==p[j-1]||p[j-1]=='.'))
res[i][j]=res[i-1][j-1];
else if(p[j-1]=='*'){
res[i][j]=res[i][j-2];
if(s[i-1]==p[j-2]||p[j-2]=='.')
res[i][j]=res[i][j]||res[i-1][j];
}
}
return res[m][n];
}
Second round note:
Similar problems, like regular expression, wild card matching, or the variant wild card matching I met in Microsoft's interview, or LCS, are of the same pattern. The three matching problem only differ in a small details.
When '*' appears, consider two cases mostly: '*' means the character it represents appears 0 times, or it means the current character in the target string is absorbed in the former substring.
In this problem, since a* are bound together, the appearing-0-time case is
c[i][j] = c[i][j-2]
and the absorbing case is
if(s[i]==p[j-1]||p[j-1]=='.')
c[i][j] = c[i-1][j]
In the wildcard problem, the appearing-0-time case is
c[i][j] = c[i][j-1]
and the absorbing case is
c[i][j] = c[i-1][j]
and the matching case is
c[i][j] = c[i-1][j-1]
In the variant wildcard, the appearing-0-time case is
c[i][j] = c[i][j-1]
and the absorbing case is
if(s[i]==s[i-1])
c[i][j] = c[i-1][j]
and the matching case is
c[i][j] = c[i-1][j-1]
And the trickiest point is like to match aa with c*aa, the initialization of ' ' matching c* should be careful. The only way to ensure the starting c* matching is in the initialization.
#11. Container with Most Water
Very easy problem. Do shrinking from both ends.
Spent a long time on it. At the very first I fell into the trap on sorting. My algorithm is very ugly due to sorting and max_min shrinking.
#15. 3 Sum (◊)
First Round:
No better algorithms. O(n^2) is the best. Thought about sorting, however tried to find algorithms in O(n) after sorting, and stuck there.
After knowing that no better algo, the trick is to jump identical numbers. Otherwise, it would be time exceeded.
Second Round:
Thought about unordered_map. However, with hash table, we cannot prevent repeating. The standard way is to
sort, then
l-r-2-middle. Remember to skip repeatings.
#18. 4 Sum
Similar to 3 Sum. But should learn to use MAP to reduce time cost.
#19. Remove node from a linked list
Very easy problem. Tried and failed to pass in one submission: Didn't think about the boundary criteria: what if the node to be moved is head. BE AWARE OF THIS!
#20. Stack
A basic exercise on stacks. Learnt about interfaces of stack. However, should remember some basic experiences on stack:
1. check empty, very important.
2. ...
#22. Generate Parentheses (◊◊)
Second Round:
DFS. Initially, we have n '(' and n ')' to be placed. We call DFS(s, n, n). In each recursion, we firstly place a '(', and check if ')' is more than '(' to be placed, we place a ')'. Stop at all are placed.
This question is the same as "
go down and right".
This is a typical DFS pattern.
#23. Merge k lists (◊)
A simple divide-and-conquer applied to k lists. It is slow. A better min_heap method should be understand.
Second Round:
A recursive divide-and-conquer is not slow in fact. The priority queue solution is just pushing every node into the priority queue: firstly pushing every head of these lists into the queue, and once a head is merged, push its next node into the queue. This is just merging every list at once. Its time complexity is O(Nlogn), and the divide-and-conquer way has O(max(L)logn) which is faster.
#39. Combination Sum
A classic backtracking problem. Should memorize the template of the solution.
#43. Multiply Strings (◊◊◊)
A detail-implementation problem. Firstly I used a very inefficient solution. Secondly, for the simpler solution I made so many mistakes.
Should repeat this question at least twice to memorize all details.
Second Round:
Totally forgot the solution. Did with a really stupid naive way and had tons of detailing mistakes. The trick of this question is
use vector to store "occupied digit space" and accumulate all "flags" instead of do string addition and multiplication over and over again.
＃44. Wildcard Matching (◊◊◊◊)
I did classical dp which is very slow. There are some optimized methods.
A best solution is using pure
backtracking:
bool isMatch(string s, string p) {
int n=s.length(), m=p.length();
int pid=0, sid=0;
int pidp=-1, sidp=-1;
while(sid<n){
if(p[pid]==s[sid] || p[pid]=='?'){ pid++; sid++; }
else if(p[pid]=='*'){ pidp=pid++; sidp=sid; }
else{
if(pidp>-1){ pid=pidp+1; sid=++sidp; }
else{ return false; }
}
}
while(p[pid]=='*') pid++;
return pid==m;
}
The idea is to try to match s with the rest of p after the last *. If not match, get back with one char less and assume that char is absorbed by the last *.
#46. Permutation
Note that it is a 3-layer loop. This is just the canonical solution. Remember it.
#50. Pow(x,n) (◊◊◊)
Second round:
While doing divide-and-conquer, remember not to
directly write the function call in the merging statement! This makes duplicate calls by exponential time!
#57. Insert Interval
No algorithm trick, but corner cases are too much and hard to think out. Should take care of this question.
This question can use binary search to solve!
#68. Text Justification (◊◊)
This question has no algo, but just to deal with details.
Key points: 1. how to distribute the remaining blanks; 2. what if there is only word that fills the whole line, or does not fill the whole line? 3. The last line.
# 69. Sqrt(x)
Use binary search instead of linear scanning. Be careful when using
mid*mid>x.
#71. Simplify Path (◊◊)
A very detailing problem. A best way is to
segment the "word" between each '/', and then verify what the word is. This is much more elegant than reading each character one at a time.
#75. Sort Colors (◊)
Not hard problem. But should be very careful about the pointers!
#76. Minimize Window Substring (◊◊)
First Round:
Very hard problem. Have no idea. Should memorize the standard solution.
string minWindow(string s, string t) {
map<char,int> T;
for(char i: t){
if(T.find(i)!=T.end())
T[i]++;
else
T[i]=1;
}
int t_mark = t.length();
int stp=0;
int mL,mR;
int w=INT_MAX;
for(int i=0;i<s.length();i++){
if(T[s[i]]>0)
t_mark--;
T[s[i]]--;
while(t_mark==0){
if(i-stp+1<w){
w=i-stp+1;
mL=stp;
mR=i;
}
if(T[s[stp]]==0)t_mark++;
T[s[stp]]++;
stp++;
}
}
if(w==INT_MAX)return "";
else{
return s.substr(mL,mR-mL+1);
}
}
Second Round:
A classic 'two pointers' problem. The hardest part of this question other than others is, during the process when i is moving, it may encounter a character that is in the alphabet, but not the one discarded just now by j. In this case, this character's counter may become negative, and when j is moving, to recover this counter may lead to detail issues.
#77. Combinations
The standard solution is really clear. Had the same idea but didn't write so neat code. Memorize it.
#78. Subset (◊)
Third Round:
This question has a most elegant approach: each subset is a mapping with a number in [0,2^n-1]. By converting this number to binary, the digits "1"'s represent the attendance of the corresponding elements. For example: for {1,2,3}, "111" means {1,2,3}, and "101" means {1,3}, and "010" means {2}.
Using bit shifting with mod operator, we can determine at each digit, if "1" attended.
#79. Word Search (◊)
My code was always 'time exceeded limit', because I
didn't return true once I found the series. Instead, I set bool res = true, and then still allow the other searching paths looping, which is the reason that I got out of time.
#85. Maximal Rectangle (◊◊◊)
A really tricky problem. The solution is not DP, which is misleading.
Basically, the solution is similar to 'Bomber', which requires sweeping. However, this question's most tricky part is the storage space that stores the swept results.
The idea is to record the height of this point, and also the left bound and right bound. HOWEVER, THE LEFT BOUND AND RIGHT BOUND OF CONSECUTIVE '1's ARE NOT FOR THIS ROW, BUT FOR THE NARROWEST PREVIOUS ROW. AND THE STORAGES ARE ITERATIVE WHICH CAN KEEP PREVIOUS ROWS' INFORMATION.
L[i][j] = ('1')?max(L[i-1][j],left):0;
R[i][j] = ('1')?min(R[i-1][j],right):n-1;
H[i][j] = ('1')?H[i-1][j]+1:0;
Second Round:
We can think about it as a DP problem, but the key point is still firstly compute the height of each column at each position. The area is the min height of the width range times the width. At each position, just select the max area for all possible ranges: at j, the possible ranges are (0,j), ... , (j,j). Just starting from j, backward to 0, and record the min height starting from height at j.
This is not fastest way, but an clear and easy DP-wise solution.
#90. Subsets II (◊◊◊◊) (◊◊◊◊)
Memorize the iteration method: firstly push [] into res. Then for each element in nums, for each vector in res, if i==0 (the first element) or nums[i]!=nums[i-1] (new element) or
j>=previous_size (if this current element is repeated, but there exist some already vectors such that adding in this element would not cause repeating) , then add this new element to this vector, and add this newly-combined vector into res.
＃91. Decode Ways
DP, but not 2-edge! Just one-edge iterative. Must have very clean case-dividing. Be careful of illegal cases!!
#101. Symmetric Tree
Very easy problem. Just got stuck.
NOTE: the iteration version of tree recursively visit is just using a stack and then imitate the recursive process.
#107. Binary Tree Level Order Traversal
Not hard. Very basic. Should get it more familiar. The key is we can push back elements to the vector inside a vector. This makes it dynamic and easier. The feature of C++.
And remember the processing of C++ about passing by reference.
＃117. Populating Next Right Pointers II
Iterative is much more direct and easier to implement, but I just got the recursive solution, which is complicated and time consuming to write and run.
Second Round:
To do it "two-layer-wise" is a clear and simple way. At current level, if the chain is ended, move the cursor at previous level till find a node who has children, and connect the chain, until the previous level cursor hit NULL.
One key point to remember:
when to stop? the current level head's update is not simply as if the most-left node has no children, but as: go right and find the first node who has children.
#119. Pascal's Triangle II
Create enough space for the whole array since the size is predictable. Avoid using push_back to reduce time.
#120. Triangle
This kind of trick to save space for DP is special. It only suits for 'triangle's, since it takes use of the property that each line has one element less and can reuse the space without overwriting.
#125. Palindrone
Easy. But many implementation details. Should notice!
#128. Longest Consecutive Sequence (◊◊◊◊◊)
This problem itself is not hard. But this solution is tricky: after each insertion, check if its left and right neighbor is already there. If so,
update the current consecutive segment's length to its terminals. By doing so, we won't need to re-traverse the map.
Standard solution:
unordered_map<int,int> S;
if(nums.size()==0)return 0;
int len = 0;
for(int& c: nums){
if(S.find(c)!=S.end())continue;
S[c]=1;
if(S.find(c-1)!=S.end()){
S[c]+=S[c-1];
S[c-S[c-1]]++;
}
if(S[c]>len)len=S[c];
if(S.find(c+1)!=S.end()){
int tmp = S[c];
int left = c-(S[c]-1);
int right = c+S[c+1];
S[left]+=S[c+1];
S[right]+=tmp;
if(S[left]>len)len=S[left];
}
}
return len;
Second Round:
Should try to implement by myself. Should do a third round.
Third Round:
Still did not remember the solution.
#133. Clone Graph (◊◊)
Second Round:
A classic DFS with note problem. Use map as note to record clone pair nodes.
#136. Single integers
Use xor.
#137. Single Number II
Bit Operations.
#139. Word Break
Two ways: DFS with memorizing previous results, or DP.
I used DP but the case is sophisticated and made mistakes in '&&' vs '||'.
DFS should memorize paths, otherwise it would be out of time.
Second Round: A classic DP matrix computation pattern. Its complexity is O(n^3).
However, this question can also be solved by
rod-cutting pattern, which is O(n^2).
#140. Word Break II (◊◊◊◊)
To output all possibilities, we have to use DFS, and there are no pruning.
#142. Linked List Cycle II
A classic problem. Spent some time thinking. And made 3 detailed mistakes. Should take care of breaking point condition check in loops to avoid dead loop.
#146. LRU Cache
Firstly, we should make clear what this question means. LRU means: 1. if a key is visited by 'get' or 'set', its priority gets to highest; 2. erase the lowest priority key.
Secondly, learn some features of list: splice (iterator positionOfThisList, list& theOtherList, iterator positionOfTheOtherList) moves the item in the position of the other list to the position of this list.
Finally, to design the map and the list, make sure that the item in the map can refer to the position of the item whose value is the key of this item in the map -- from map we can find the corresponding in the list, and from the list we can know the key.
Second round:
Think iterators like pointers! The mistake is first set the value of the map as L.begin(), then do splice, which change the pointers! Imagine that the value (the iterators) stored in M are linking with nodes of L, and when doing splice, every iterator is moving accordingly. So
make sure firstly set the node, then refer its iterator to the map.
Should memorize list's operations: push_back(), push_front(), pop_back(), pop_front(), splice(target_position, source_list, source_position).
#155. Min Stack (◊)
Second round:
In the first round, what I did is very awkward. And a much better solution is to
use two stacks. The second stack only record local minimum elements. When the top of the two stacks are the same and when popping, the second stack pops, and when the newcomer is minimal, push it to the second stack. And the top of the second stack is the minimum.
#158. Read N characters (◊◊)
The key point is that, in each time, read4() moves 4 characters forward. This means that, if firstly I read n<4 characters, the next time, I should start from somewhere that is already in the buffer.
The solution is to use a global buffer to receive read4() contents, and use global cursors to record where to start next time, and to judge if we need to read4() again.
It is a tricky problem, though implementation is not hard. The details and idea is not easy.
#159. Longest Substring with At Most Two Distinct Characters
A classic two-pointer problem. One thing to note: when the left pointer is moving, we don't need to use 'while' to let it move till the end of a long single-char-substring. We can
just use 'if' to speed up. The only difference is the interval of the two pointers will never decrease, which just doesn't matter, since if a larger substring appeared, it still can detect it.
#160. Intersection of Two Linked Lists
The solution is tricky. Didn't think it out. Should bear it in mind.
#166. Fraction to Recurring Decimal
For all multiplication or division,
should concern negative! For all negative cases, should concern
-2147483648! Use long long, or do division manually.
#168. Excel Column Name
1. Memorize reverse(s.begin(),s.end());
2. Pay attention to those %==0 cases;
#172. Factorial Trailing Zeroes
Idea was correct. But should optimize the computing process to reduce time.
#200. Islands
If using BFS, remember to mark current element that is pushing into the queue as '2'.
DFS is definitely much faster than BFS. Use DFS as priority.
#204. Count Primes
A good question to memorize!
The algorithm is:
if i is prime, for j=i^2, j<n, j+=2i, all these j are composite.
First trick is to use space to reduce time.
Second is to use best traversal to reduce time: just need to verify to sqrt(n), after sqrt(n), all composite can be marked by the above procedure:
start from i^2 because if N < i^2, N contains lesser prime and can be marked by former prime's procedure. Interval is 2i since the other multipliers of i are even.
#205. Isomorphic String
Using memset is much faster than using map.
#211. Add and Search Word
Use Trie. Should memorize implementation of Trie.
A point that made me never passed:
Always check whether "if()return true" may lead "else return false" necessary or it never ends.
#212. Word Search II
Very hard problem. Originally, we should implement a dfs routine to search for each word. The trick is to set the visited character to 'X', and before return set it back.
However, this question requires to use a Trie to optimize the backtracking.
So firstly, we should implement a Trie build routine.
And then, we should modify the searching algorithm:
not search for each word, but put words into Trie, and search at each location of the board (brute-force searching). Normally this searching strategy is at exp time level, but we can use the Trie to control the ending point, that is, doing the search according to the Trie (along with each path of the Trie), and stop when finding that this path ends on the Trie. By doing so, not only we are not in exp time level, but we also reduce all repeated word 'paths'.
#215. Kth largest number
A classic question. The incomplete version of sorting. Can be done by heap (pop k elements), quicksort (sort last k elements) mergesort (merge k last elements).
#218. Skyline (◊◊◊◊◊)
I am picking the simplest but very clumsy approach: Firstly store every upward and downward lines in the map. Then for each upward or downward line, insert it in the ordered_set so that after each insertion we can read the highest point by now. If the current point does not change, do not output. Otherwise, output the updated highest point.
#219. Contains Duplicate II
Using map. Should be more clear about basic operations, like insert, count.
Search for an element in a map is faster than doing a linear comparison.
#234. Palindrome Linked List
Not hard but didn't come out. Attention!
Should implement reverselist quickly.
Know the fast&slow pointer trick.
#236. Lowest Common Ancestor of a Binary Tree (◊◊◊)
Made it accepted but my way was too complicated. The key mistake I made was that I tried to use a stack to keep results. However, a tree recursive traversal is already a stack if we keep returning things. So next time,
when I met a question that should traverse the tree and keep track of the path, I don't need a stack.
Second Round:
The solution is tricky and I even did not understand it: "
if only one of the nodes are in this subtree, just return this node". In this way, the node where both left and right check are true is the LCA; and if one of the subtree is not NULL, then just return that node to upper levels. That node is either the LCA, or one of the node. If it is LCA, it will be returned to topest level; and if it is just one of the node, there must be a level at or before the topest where the other node is returned from the other subtree and that node is LCA. This idea is really very tricky, and it takes use of the truth that the nodes are guaranteed in the tree.
#238. Product of Array Except Self
Memorize the idea: two sides: product one by one.
#239. Sliding Window Maximum
Very tricky. The key idea is that to
divide the array into n/k blocks, each of which is of size k. Then at point i, the maximum in window of size k at position i is the larger one of maximum of the left block and maximum of the right block:
| x,x,x,[x,x,x,x | x,x,x] x,x,x,x |
Use two passes to calculate the max from left and max from right at each point, then at each point, the max is the max of (max-from-left at left bound, max-from-right at right bound).
This idea is tricky and new. Should memorize it and apply it to blockwise max/min problems.
#240. Search a 2D Matrix
A classic problem, and the standard solution is neat and simple. Should remember it.
Starting from right top corner, if larger, go down, if smaller, go left.
#241. Different Ways to Add Parenthesis
The complexity is high. So no need to care about the complexity. Writing with recursive reads simple.
The standard answer is elegant. The trick is to transfer multidigits to integers with substring and stoi, and only when single number to output.
#253. Meeting Room II (◊◊◊)
I tried a clumsy approach which is very slow.
The smart way to do it is using ordered_map.
The idea is to regard the intervals like parentheses, and insert them into an axis in order. Then the number of rooms needed is the number of consecutive '('s. That is, if ')' appears after '(', it means these two intervals can coexist, and the number of consecutive '('s means the conflicts, i.e. the number of rooms required.
#257. Binary Tree Path
Using auto item:vector needs reference. Use to_string to convert int to string.
#260.
Single integers III
First get the xor of all numbers (name it A). A represents the xor of the two unique numbers. Then use A&(-A) to get the rightest digit which is nonzero. The two numbers must differ at this digit. Then
use this digit to classify all numbers to two different rows, and use xor to get the unique number of each row.
#271. encode strings
Use the idea of encoding an image: put information in the head. This always works: to create some method that reads the head, it won't have any confusion.
#276. Paint Fences
Was mislead by 'easy'. It is not very easy - not very explicit to use iterative.
Firstly, notice that iteratively, the current status is dependent with 'k-1' or '1' of the last fence. If last is '1', then this time we will only have 'k-1' choices, else if last is 'k-1' which means last is different from last last, then we will have 'k' choices this time, and this 'k' can be split to 'k-1' and '1'. Notice that we can combine the two 'k-1' case, so the iterative equation is:
c[i] = (c[i-1,1]+c[i-1,2])*(k-1) + c[i-1,1]*1
c[i,1] = (c[i-1,1]+c[i-1,2])*(k-1)
c[i,2] = c[i-1,1]
#277. Find the Celebrity (◊◊)
Used DFS which is stupidly slow. But in fact my DFS is just O(n) which never repeats its paths. So it can be simplified to a for-loop:
first pass: stop at the one who knows no one after it.
second pass: check if it knows anyone before it.
third pass: check if someone doesn't know it.
Second Round:
This question is not at all DFS, since its conditions are too strong. Once a knows b, a can never be the celebrity; if a does not know c, c cannot be the celebrity. So this question is
just like a "find_min" question.
#278. First Bad Version
Though don't know why (a+b)/2 is not working, but should memorize a standard way to do BS:
s = 1;
t = n;
m = (s+t)/2;
if{s = m+1;}else{t = m-1;}
#279. Perfect Squares
The BFS solution is much faster: the idea is to firstly construct the 2s, then if n is not reached, put 2s in queue and construct 3s, till n is reached.
#282. Expression and Operators (◊◊◊◊◊ + ◊)
A very hard problem.
An easy solution should be memorized:
Just do left-to-right DFS. At each position, traverse +, -, *. with path memorization. sum = sum + int / sum = sum - int /
sum = sum - prev + prev*int. The multiplication case is the tricky one.
The trickiest part is the decision of "no signs", i.e.
multi-digit numbers. The way to do it is
USE A FOR LOOP at POSITION i. Try j from i to the end of the string and try num(i~j) as the candidate number, instead of traverse this "no sign" possibility together with "+,-,*".
The next trickiest part is
in "-" case, the "prev" number is negative!
The pattern of this question is Left-to-Right DFS which terminates at pos equals length. At the last position, determine if the results satisfy, if so, push the path to the result container. Several questions are in this pattern.
#290. Word Pattern
Basic string operations. Train to do it faster and bug free!
#295. Find Median (◊◊)
At first I used multiset, and found that multiset is not random access container, which means I cannot access its middle value in O(1).
Then head to heap, and saw the solution that uses
two heaps.
This is natural, but should memorize it.
#301. Remove Invalid Parentheses (◊◊◊◊◊)
Second round:
In the first round I solved this question. But in the round I cannot.
My straightforward idea was that, firstly count the number of '(' and ')' to be removed. Then remove recursively: First remove ')'s, then remove '('s. When number of l and r are both 0, check if it is valid. If so, push it into res.
To remove: first find a ')', erase it, then put the rest string into a recursive function and the number of r is reduced by 1.
The key point is: in the recursive function, both left and right removal are included.
#308. Range Sum Query 2D (◊◊◊◊◊)
Learnt to use binary index tree to store sums: If use an array to store sums up to here for every position, each update takes O(n), though get sum takes O(1), so introduced in BIT: to reduce update to O(logn) by increasing get-sum to O(logn).
A BIT is a similar array, but each position does not store the sum up to here, but like following:
1, 1+2, 3, 1+2+3+4, 5, 5+6, 7, 1++8, 9, 9+10, 11, 9++12, 13, 13+14, 15, 1++16
Thus add in difference (update value) is traversing like this:
for(int i=I;i<=m;i+=(i&-i))
which means to update all entries from r,c to the right bottom corner.
and getting sum is traversing like this:
for(int i=I;i>0;i-=(i&-i))
which means to get the sum from r,c to the left top corner, and call this 4 times to get the bounded box sum.
By this special array, we can store sum and update the stored sum both in O(logn).
#313. Super Ugly Number (◊◊◊◊)
DP for O(kN) or Heap for O(NlogK). Should remember the solutions. Should memorize that "every super ugly number is the product of one prime in the input with one super ugly number already in the array." These prime factorization problems can always have this kind of DP idea.
a[i] = min(a[index[j]]*prime[j]);
index[j] = index[j] + (a[i] == a[index[j]]*prime[j]);
#318. Maximum Product of Words
Time limit exceeded: Key is not to construct bitset every comparison, but construct the list of all bitsets at first, and compare them every time.
#325. Maximum Size Subarray Sum Equals k (◊◊)
Medium but hard to me. The idea is to record each sum generated by subarrays starting from left end. And then at each location, we can try to see if the sum from left end to here is k, if not, if we can truncate some left subarray so that the left part sums to k.
This algo takes use of the difference of current sum and k which is a number, like what we did in 2-sum. And it regards each subarray as
left-end to here minus left-end to somewhere before. This is the tricky part, and worthy to be memorized.
#328. Odd Linked List
Not too familiar with linked list operations! Keep no loop pointers!
#329. Longest Increasing Path
A classic matrix DFS/BFS problem. Using DFS, I should notice to use MEMORIZATION to
record subpath's distance results.
#331. Verify preorder serialization
I used a stack. However, I found that the stack only stores statuses instead of true values. This is a hint that a optimized way can be done -- simplify the stack to some status counter.
#337. House Robber III
Binary Tree no neighbor sum. Classic problem.
1. Consider all possibilities of "no neighbor sum".
2. For recursive solutions, never allow recomputing. Store all results to avoid re-calling functions.
#347. Top k frequencies
1. Become more familiar with map and vector
2. use the upperbound of frequencies to do bucket sort-like linear time analysis
3. become more familiar with traversal of map: auto& pair, pair.first, pair.second
＃367. Valid Perfect Square
Use sum of odd numbers.
#380. GetRandom (◊◊)
Design problem. Since it requires access random, a simplest way is to use an array. So a combination of array and map is enough.
Should get more experiences from these kinds of questions.
#398. Random Pick (◊◊)
The reservoir algo:
counter=1;
{res = rand()%counter==0?i:res;
counter++;}
#410. Split Array Largest Sum (◊◊◊◊◊)
Did DP solution, which is complicated and time exceeded.
The standard solution is too tricky, have to memorize:
bool doable (const vector<int>& nums, int cuts, long long max) {
int acc = 0;
for (num : nums) {
if (num > max) return false;
else if (acc + num <= max) acc += num;
else {
--cuts;
acc = num;
if (cuts < 0) return false;
}
}
return true;
}
int splitArray(vector<int>& nums, int m) {
long long left = 0, right = 0;
for (num : nums) {
left = max(left, (long long)num);
right += num;
}
while (left < right) {
long long mid = left + (right - left) / 2;
if (doable(nums, m - 1, mid)) right = mid;
else left = mid + 1;
}
return left;
}
The idea is:
If the array can be cut to get a minmax sum of K with m-1 cuts, then it must be cut to get a minmax sum less than K with m cuts.
The minimum possible minmax sum is the largest value in the array, while the maximum possible is the sum of the array.
Use binary search to search for the smallest value that can be cut with m cuts.
How to determine if the array can be cut to K with m cuts? Sum up from beginning, if exceeded K, consider a cut here and discard the previous subarray and restart from here to sum up, in the meanwhile decrease the number of cuts available. If the process hasn't been done to the right side of the array but the number of cuts is decreased to negative, then it cannot be done with so few cuts. In the opposite, if the process is done while the remained number of cuts is at least zero, it means a number at most K can be cut with so many cuts.
#32. Longest Valid Parenthesis
Not hard. Don't be fooled by the hint 'dynamic programming'. Just use stack to eliminate the valid substrings, and recorded the invalid positions. And calculate the lengths of each eliminated substrings.
