Hash Table (Part 1)
Target May 20th to finish
(1) Check whether the two input array have the same size if not, return false.
438Find All Anagrams in a String
Use two vectors to mimic hash map (easier for compare between vectors)
(1) Count the frequency of chars appeared in string p and save the result in vector freq1
(2) Count the frequency of first p.size() chars in string and save the result in the vector freq2
(3) if freq1 == freq2 put 0 in the result array
(4) Slide the window from position p.size() to the last char in string s. Each time increase the frequency for the char entered into the slide window and also decrease the frequency the char frequency for the char that slide out of the window (we keep the window sizes fixed at p.size())
If found freq1 == freq2 put the index for the left most char in the current window into the result array. (i - p.size() + 1)
(5) return result array.
781Rabbits in Forest
Write some examples to figure out the number pattern
If x+1 rabbits have same color, then we get x+1 rabbits who all answer x.
now n rabbits answer x.
If n%(x+1)==0, we need n/(x+1) groups of x+1 rabbits.
If n%(x+1)!=0, we need n/(x+1) + 1 groups of x+1 rabbits.
the number of groups is math.ceil(n/(x+1)) and it equals to (n+x)/(x+1) , which is more elegant.
the total number of rabits in the group would be (n + x) / (x + 1) * (x + 1)
(2) In the second loop check the frequency of each number, if there is one num with frequency one. return it.
(3) Otherwise, no early exit. Meaning no such number exist.
In the first loop use a hash map to calculate the frequency of each unique char in the string.
O(S + J) time and O(S) space hash table solution.
(1) Calculate the frequency of all the stones in string S and save it in the hash map.
(2) For loop the diamond char c in the string J. If c is also in S, add its frequency to the count.
(3) Return count in the end.
508 Most Frequent Subtree Sum
Hash map combined with DFS.
Keep a map which saves the current subTree sum and its frequency. Also update the max frequency while recursion. After DFS recursion, in another loop put the max frequency node value into the vector result and return it.
Use a unordered_set to record the numbers have encountered so far while repeatedly calculating the sum of digits squares, if we run into a sum that already in the set, that means there is a cycle, it could not be a happy number. Otherwise keep loop until we reach 1, then we have a happy number.
(1) For loop each cell in the matrix, check if it is a land cell, if so check its 4 neighbours (row +/- 1) * (col +/- 1). And count the number of land cell N. And add 4 - N to the total perimeter count.
204 Count Prime
Eratosthenes Sieve for prime numbers
Time O(N*N^(1/2)) = O(N^(1.5)), Space O(N)
Mark all 1-n numbers as prime number initially. Then cross out the one divisible by 2, and then cross out the one divisible by 3, then 5, 7 (i.e. cross out all the numbers that divisible by previous prime number left), then the remaining one are the real prime numbers.
https://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif
Same idea with 643 Maximum Average Subarray I .
Except we need to use hash set to save all the elements in the first
window. While move the window forward, erase the first element from the
old window, and check whether the current element exist in the remaining
window elements. If there is duplicate, return true. Otherwise, insert
the new element into the window. If in the end no early exit, there is
not duplicate.
1. Frequency Match
(1) For loop array A and array B, save all the sum of
a and b into a new hash map.
(2) For loop array C and array D, try to find the negative sum of c + d (i.e : -(c + d))in the hash map created in step 1.
(3)If found, add the iter->second (frequencies of (a + b)) to the total count.
(4) Return total count in the end.
O(N^2) time and O(N^2) space.
Using STL unordered_map as hash map, O(N) time and O(N) space
(1) Count the frequency of each citation number in a loop. For these paper
(2) that has citation more than the total number of papers N, treat them as cited as N, since the hIndex is the minimum of number and citation times.
(3) Backward loop the frequency map i: from N to 1 (all possible h-Index), and check whether freq[i] >= i, if so return it. Otherwise, add the freq[i - 1] += freq[i]; If no early return meaning no citation or no paper published at all, return 0.
| 454 |
(2) For loop array C and array D, try to find the negative sum of c + d (i.e : -(c + d))in the hash map created in step 1.
(3)If found, add the iter->second (frequencies of (a + b)) to the total count.
(4) Return total count in the end.
O(N^2) time and O(N^2) space.
| 274 |
(1) Count the frequency of each citation number in a loop. For these paper
(2) that has citation more than the total number of papers N, treat them as cited as N, since the hIndex is the minimum of number and citation times.
(3) Backward loop the frequency map i: from N to 1 (all possible h-Index), and check whether freq[i] >= i, if so return it. Otherwise, add the freq[i - 1] += freq[i]; If no early return meaning no citation or no paper published at all, return 0.
560
|
Use prefixSum to save the total sum until current element. And define a unordered_map to save all the prefixSum and its frequency. Remember to initialize map[0] = 1 (to calculate these sub-array starting from index 0). Add map[prefixSum - k] to the total count while iterating all the element on the fly. And update the map by map[prefixSum]++.
| 242 |
(2) Define a hash map to calculate the frequency of each unique char in string 1. And for loop each char (str1[i]) in string 1 and increase its frequency and decrease the frequency of the char at the same index in string 2 (str2[i]).
(3) After the loop, check the frequency of each char, if there is one char frequency that is not equal to zero, return false.
(4) If after the loop in step 3, and there is no early exit. Return true.
438Find All Anagrams in a String
Use two vectors to mimic hash map (easier for compare between vectors)
(1) Count the frequency of chars appeared in string p and save the result in vector freq1
(2) Count the frequency of first p.size() chars in string and save the result in the vector freq2
(3) if freq1 == freq2 put 0 in the result array
(4) Slide the window from position p.size() to the last char in string s. Each time increase the frequency for the char entered into the slide window and also decrease the frequency the char frequency for the char that slide out of the window (we keep the window sizes fixed at p.size())
If found freq1 == freq2 put the index for the left most char in the current window into the result array. (i - p.size() + 1)
(5) return result array.
781Rabbits in Forest
Write some examples to figure out the number pattern
If x+1 rabbits have same color, then we get x+1 rabbits who all answer x.
now n rabbits answer x.
If n%(x+1)==0, we need n/(x+1) groups of x+1 rabbits.
If n%(x+1)!=0, we need n/(x+1) + 1 groups of x+1 rabbits.
the number of groups is math.ceil(n/(x+1)) and it equals to (n+x)/(x+1) , which is more elegant.
the total number of rabits in the group would be (n + x) / (x + 1) * (x + 1)
(1) Loop the array and count the frequency of each num
(2) Loop the hash map and check whether current num - 1 is also in the map, if so update the LHS with LHS = max(LHS, current num frequency + num - 1 frequency)
(3) return LHS
(1) Use two hash map to keep the map between chars in the two string to its position.
(2) If there is two chars has not equal positions, then the two strings are not isomorphic. Otherwise,
Update the two chars map to the current index position + 1 ( cannot set to index directly, since it could be zero)
(3) return true if not early exit.
Word Pattern
Similar to 205 above. Except we have to split the word string into a vector of words first. Using stringstream ss(str); while (ss >> str) vec.push_back(str); to do so. Then instead of creating two char to int frequency map, we create one char to int frequency map and one string to int frequency map for word. The rest is the same.
Use a hash map to count each 10 character string frequency. In the second loop, loop each map element to check f its frequency is > 1, put it in the result array. Return the result array in the end.
(1) Sort both arrays and call STL a.erase(set_intersection(a.begin(), a.end(), b.begin(), b.end(), a.end()), a.end()). O(NlgN) time and O(1) space
(2) Loop the hash map and check whether current num - 1 is also in the map, if so update the LHS with LHS = max(LHS, current num frequency + num - 1 frequency)
(3) return LHS
| 205 |
(2) If there is two chars has not equal positions, then the two strings are not isomorphic. Otherwise,
Update the two chars map to the current index position + 1 ( cannot set to index directly, since it could be zero)
(3) return true if not early exit.
Word Pattern
Similar to 205 above. Except we have to split the word string into a vector of words first. Using stringstream ss(str); while (ss >> str) vec.push_back(str); to do so. Then instead of creating two char to int frequency map, we create one char to int frequency map and one string to int frequency map for word. The rest is the same.
| 187 |
| 350 |
(2) (2.1) Count the frequency of each number for array1 and save the result in a hash map. (2.2) For loop each number in the second array if found in the hash map and its frequency is still larger than 0, put it in the result array and decrease the frequency by 1. (2.3) In the end, return the result array.
O(M+N) time and O(M) space.
O(M+N) time and O(M) space.
| 389 |
Similar to 242. Except we have to separate the increase and decrease of char frequency in two different loops (since they have different size). In the last step we just need to check whether there is a frequency value that is less that zero. If so, return that char. If after that, and there is no early exit. Meaning there is no extra char in string t.
(1) Count the frequency of each number in the first loop.| 532 |
(1) Use a hash set to keep track of the possible starters for all K-diff pairs and use a freq hash map to count all the num and its occurrance frequency.
(2) For loop each num in the array. If count(num + k) > 0 is in the map already, add num to the starters set. If (Not else if, since they are Coordinative relation) count(num - k) > 0, add num - k to the starters as well.
(3) Return the starters set size in the end, which is the number of unique K-diff pairs in the array.
| 136 |
(2) In the second loop check the frequency of each number, if there is one num with frequency one. return it.
(3) Otherwise, no early exit. Meaning no such number exist.
| 387 |
Starting from the first char, in the second loop check the frequency of each char, if it is greater than one. Return it. Return -1 if after the second loop and no early exit.
O(S + J) time and O(S) space hash table solution.
(1) Calculate the frequency of all the stones in string S and save it in the hash map.
(2) For loop the diamond char c in the string J. If c is also in S, add its frequency to the count.
(3) Return count in the end.
| 409 |
Intuition
A palindrome consists of letters with equal partners, plus possibly a unique center (without a partner). The letter
ifrom the left has its partner i from the right. For example in 'abcba', 'aa' and 'bb' are partners, and 'c'is a unique center.
Imagine we built our palindrome. It consists of as many partnered letters as possible, plus a unique center if possible. This motivates a greedy approach.
Algorithm
For each letter, say it occurs
v times. We know we have v // 2 * 2 letters that can be partnered for sure. For example, if we have 'aaaaa', then we could have 'aaaa' partnered, which is 5 // 2 * 2 = 4 letters partnered.
At the end, if there was any
v % 2 == 1, then that letter could have been a unique center. Otherwise, every letter was partnered. To perform this check, we will check for v % 2 == 1 and ans % 2 == 0, the latter meaning we haven't yet added a unique center to the answer.Tree
508 Most Frequent Subtree Sum
Hash map combined with DFS.
Keep a map which saves the current subTree sum and its frequency. Also update the max frequency while recursion. After DFS recursion, in another loop put the max frequency node value into the vector result and return it.
DP
| 718 |
DP:
vector<vector<int> > dp(sizeA + 1, vector<int>(sizeB + 1, 0));
vector<vector<int> > dp(sizeA + 1, vector<int>(sizeB + 1, 0));
if A[i] == B[j]
dp[i][j] = dp[i + 1][j + 1] + 1;
dp[i][j] = dp[i + 1][j + 1] + 1;
res = max(res, dp[i][j]);
Binary Search with Rolling Hash
Binary Search with Rolling Hash
Kind of complicated, need to learn
Mixed Data Structure
This kind of questions are usually use multiple mixed DS to speed the operation. Basically it is trading space for time. Similar one: use a queue + heap (or priority_queue) to speed up the getMax()
, delete and insert from queue.
Data Structure
unordered_map<int, int> mp
+
vector<int> nums
insert:
emplace_back(val)
mp[val] = nums.size() - 1
Delete:
idea: copy the last to overwrite the one to be deleted and update the map accordingly.
int last = nums.back();
mp[last] = mp[val];
nums[mp[val]] = last;
nums.pop_back();
mp.erase(val);
getRandom():
return nums[rand() % nums.size()];
Sliding Window (SW)
Mixed Data Structure
This kind of questions are usually use multiple mixed DS to speed the operation. Basically it is trading space for time. Similar one: use a queue + heap (or priority_queue) to speed up the getMax()
, delete and insert from queue.
| 380 |
unordered_map<int, int> mp
+
vector<int> nums
insert:
emplace_back(val)
mp[val] = nums.size() - 1
Delete:
idea: copy the last to overwrite the one to be deleted and update the map accordingly.
int last = nums.back();
mp[last] = mp[val];
nums[mp[val]] = last;
nums.pop_back();
mp.erase(val);
getRandom():
return nums[rand() % nums.size()];
Math
166 Fraction to Recurring Decimal (Y)
Well, the key to this problem is on how to identify the recurring parts. After doing some examples using pen and paper, you may find that for the decimal parts to recur, the remainders should recur. So we need to maintain the remainders we have seen. Once we see a repeated remainder, we know that we have reached the end of the recurring parts and should enclose it with a
). However, we still need to insert the ( to the correct position. So we maintain a mapping from each remainder to the position of the corresponding quotient digit of it in the recurring parts. Then we use this mapping to retrieve the starting position of the recurring parts.
Step1: Insert copy nodes
Step2: copy the random pointer. q->random->random->next is the dst random pointer value for the new list.
Step3: Recover the old list using saved result in hash map
Sliding Window (SW)
| 3 |
Sliding window O(N) time, O(K) space where K is the size of set Define a hash set and loop over each char in the string from left to right while the right side of the window is still within the range of string size check whether the current char is already in the set, if not: insert it into the set and move the right side right by 1, update maxCount if the current window size is greater that maxCount. If yes, erase the current element indicated by the left side of the window from the set and move the left side of window right by one. After the right side of the window exceeds string size. maxCount will be the longest substring without repeating characters.
Other
(1) Sort the string array in lexicographically ascending order
(2) Use a hash set to save the prefixes found so far. Add all the length 1 prefixes or prefixes that already has its sub-prefixes in the set to the set
(3) Return the longest prefixes in the set if there is an equal, return the lexicographically smaller one.
| 202 |
| 463 |
| 217 |
Standard hash set. For loop each num in the input array. If it already exists in the hash set return true. Otherwise insert it into the hash set. If after exit and there is no early exit. Return false.
(1) Initialize a hash set with the input array 1 ( to get rid of dup)
(2) For loop each num in the second array. If num can be find in the hash set, insert it to the result array and erase it from the hash set.
(3) In the end return the result array.
(a) For loop the vector<Employee*> input and set up a hash map from the employee id to the Employee object pointer. Use a helper function with two parameters: the map and the employee id
that we want to get its and its subordinates importance. In the helper function using DFS to calculate the total importance. Set the initial importance to its own importance. For each subordinates, DFS-recursively call the helper function to calculate its and its subordinates importance. Finally return the total summation of initial value and the recursively function call value, which is the desired importance value.
Use a hash set to collect the candle kinds number in a for loop. Since the maximum kinds the sister could get is half the number of candles (You need to distribute these candies equally in number to brother and sister). After the loop, check whether the kind number is >= half the candle numbers. If so, return half the candle numbers. Otherwise, return the kind number.
(1) Use 3 char hash set to save the three row chars.
| 690 |
that we want to get its and its subordinates importance. In the helper function using DFS to calculate the total importance. Set the initial importance to its own importance. For each subordinates, DFS-recursively call the helper function to calculate its and its subordinates importance. Finally return the total summation of initial value and the recursively function call value, which is the desired importance value.
| 575 |
| 500 |
(2) For each word in the words list. Check each char in the word. To see whether every char in the word is in the same row. We can use 3 count (count1, count2, count3) to help us decide this. We set count1 to 1 if find one char in row 1, similarly set count2 or count3 to 1 if find one char in row2 or row3. If we find count1 + count2 + count3 > 1 we can break out of the loop since the word cannot be constructed from one line. After the loop check whether the sum of count1 + count2 + count3 == 1, if so put the current word into the result list.
(3) return the result list in the end.
204 Count Prime
Eratosthenes Sieve for prime numbers
Time O(N*N^(1/2)) = O(N^(1.5)), Space O(N)
Mark all 1-n numbers as prime number initially. Then cross out the one divisible by 2, and then cross out the one divisible by 3, then 5, 7 (i.e. cross out all the numbers that divisible by previous prime number left), then the remaining one are the real prime numbers.
https://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif
| 219 |
535. Encode and Decode TinyURL (Y)
Simple but not very secure solution
Use
a vector<string> url to save the longUrl and decode the shortUrl
to the prefix followed by the vector array size - 1. When decoding just
return url[index].
(1) Use hash set to save all the prefix
(2) Use stringstream to split the sentence into word. And for each word get its root and append to the result string.
For get root of a word function
(1) For loop each prefix of word (from len 1 to len sizeof(word)), check whether it is in the prefix set, assign it to the res and break (since we are checking shorter prefix first, we can break after find one and still guarantee that is the shortest one)
O(NW*LW *(LP + LW)) time and O(NP * LP) space. Where NW is the total number of word. And LW is the length of word. and NP is the number of prefix and LP is the longest prefix length.
(1) Use hash set to save all the prefix
(2) Use stringstream to split the sentence into word. And for each word get its root and append to the result string.
For get root of a word function
(1) For loop each prefix of word (from len 1 to len sizeof(word)), check whether it is in the prefix set, assign it to the res and break (since we are checking shorter prefix first, we can break after find one and still guarantee that is the shortest one)
O(NW*LW *(LP + LW)) time and O(NP * LP) space. Where NW is the total number of word. And LW is the length of word. and NP is the number of prefix and LP is the longest prefix length.
| 49 | Group Anagrams |
Hash map O(N * Mlg(M)) time, two itearation, O(N * M) space
Where N is the number of strings, M is the maximum string length
The idea is to use an unordered_map to store those strings that are anagrams. We use the sorted string as the key and the string itself as the value. The strings are stored in a multiset since there may be duplicates. Moreover, multiset will sort them by default as we desire.
If we don't care the sort within the anagram group, we can also define a unordered_map<string, vector<string> > mp;
Use hash set to keep track the number encountered so far in the current group (either current row or current col or current sub-box), if find some repeated number early return false. If all check and no early return, return true.
Similar to 15 3Sum. Only difference is one more level loop. And you can do some early exit checks to make it faster. Like if first 4 elements already > target early exit. If first 1 and last three elements sum < target, continue next loop.
O(N^3) time and O(N^3) space, O(1) extra space.
If we don't care the sort within the anagram group, we can also define a unordered_map<string, vector<string> > mp;
| 36 |
| 18 |
O(N^3) time and O(N^3) space, O(1) extra space.
Comments
Post a Comment