Heap (priority queue)
hash map + priority_queue
659 Split Array into Consecutive Subsequences
Maintain a set of consecutive sequences, call this set S. S begins as an empty set of consecutive sequences.
Now, iterate through each num in nums. For each iteration, if there exists a consecutive sequence in S that ends with element num - 1, then append num to the end of the shortest such sequence; otherwise, create a new sequence that begins with num.
The problem has a solution (i.e. the array can be split into consecutive subsequences such that each subsequence consists of at least 3 consecutive integers) if and only if each sequence in S has size greater than or equal to 3.
O(N) time, O(N) space solution, using priority_queue with a helper queue to filter the already 0-counted pairs.
For priority queue, the highest priority element (maximum count element here, therefore we want the pair in the priority queue be pair<int, char> rather than pair<char, int>, the later will sort the queue by descending alphabetical order, the first will sort the array according to the int number in descending order) is always at the front.
Graph
743 Network Delay Time
O(N*E) time O(N) space. Bellman Ford single source shortest path algorithm.
(1) Repeat the following step 2 n times.
(2) For loop each edge in the graph, get its source u and destination v, and weight w. If the distance from k to u plus w is less than the distance from k to v, update dist(v) = dist(u) + w.
(3) For loop each distance in the distant array get the max value, which will be the wait time to propagate the message to each node in the graph.
Could Use priority queue as well.
787 Cheapest Flights Within K Stops
Similar to 743, except that we only need to iterate K + 1 time before stop. We also cannot do the update on the fly. Since we may update to much and get the value should be update in the next iteration. Therefore we have to save the price to a buff and update the buff value within the same inner loop. After the inner loop, we can copy the buff value to the price value and do the next iteration.
355 Design Twitter
=====================================================================
hash map + priority_queue
451 Sort Characters By Frequency
(1) Count the frequency of each char in the string using a hash map (from char to int)
(2) Push the pairs of (int, char) into the priority_queue (max heap by default)
(3) append p.n copies of each p.c in for each pair of p at the priority queue top while its not empty
(4) return the result string.
373 Find K Pairs with Smallest Sums
Use customized min heap to solve this problem.
(1) Put all the possible pairs into the priority_queue and sort them according to their pair sum so that the smaller sum pairs will be in front of the queue
(2) Pop and save the top k pairs to the result array and return it.
378Kth Smallest Element in a Sorted Matrix
Put all the elements in a priority_queue (max heap).
Pop the top first n - k element, the (n - k + 1) th largest element will be the kth smallest element.
Exactly the same idea with 451 above, except here the basic element is int number while it is chars above. We need to use push_back into result vector instead of append(n, c) to result string in 451.
Similar to 347 above.
Only different is we have to define a customized compare function for priority_queue to make sure that words of the same length are outputted in the ascending order of alphabet.
We can define as follows:
typedef priority_queue< pair<int, string>, vector<pair<int, string> >, decltype(comp) > PQT;
PQT pq(comp); // Don't forget pass comp to pq definition.
Here we are sort the queue using descending order of frequency of words.
and ascending order of alphabet order for words with the same length, that's
auto comp = [&] (const pair<int, string>& a, const pair<int, string>& b) {
return (a.first < b.first) || (a.first == b.first && a.second > b.second);
};
O(KlgN) time, O(N) space if no optimization (O(N - K)) space with opt.
Since insert into the heap is O(1) delete top from heap is O(lgN), we do K times of the deleting from the heap.
Solution 1: a naive way is to save all the elements in a max heap. And pop until you get the kth element from top. Which takes O(N) time and O(N) space.
Solution 2: A slightly better way is to save only O(N - K + 1) largest element always. Pop the top if the size bigger than that. In the end return the top element which is the (N-K+1) smallest element, which is also the Kth largest element. Takes O(N-K+1) space and O(N) time.
264 Ugly Number II
(1) Define a min heap by customizing the priority_queue with a greater than compare func
(2) Push 1 into the priority queue initially
(3) Repeat the following step n - 1 times
(4) get the top element value and save it to tmp. while queue top equal to tmp keep popping the queue.
(5) Then push tmp * 2, tmp * 3, tmp * 5 on to the heap.
(6) return the top element as the nth ugly number.
Same idea with 264, except need to for loop each prime in the array to multiply tmp and push to the heap.
659 Split Array into Consecutive Subsequences
Maintain a set of consecutive sequences, call this set S. S begins as an empty set of consecutive sequences.
Now, iterate through each num in nums. For each iteration, if there exists a consecutive sequence in S that ends with element num - 1, then append num to the end of the shortest such sequence; otherwise, create a new sequence that begins with num.
The problem has a solution (i.e. the array can be split into consecutive subsequences such that each subsequence consists of at least 3 consecutive integers) if and only if each sequence in S has size greater than or equal to 3.
| 767 |
For priority queue, the highest priority element (maximum count element here, therefore we want the pair in the priority queue be pair<int, char> rather than pair<char, int>, the later will sort the queue by descending alphabetical order, the first will sort the array according to the int number in descending order) is always at the front.
Graph
743 Network Delay Time
O(N*E) time O(N) space. Bellman Ford single source shortest path algorithm.
(1) Repeat the following step 2 n times.
(2) For loop each edge in the graph, get its source u and destination v, and weight w. If the distance from k to u plus w is less than the distance from k to v, update dist(v) = dist(u) + w.
(3) For loop each distance in the distant array get the max value, which will be the wait time to propagate the message to each node in the graph.
Could Use priority queue as well.
787 Cheapest Flights Within K Stops
Similar to 743, except that we only need to iterate K + 1 time before stop. We also cannot do the update on the fly. Since we may update to much and get the value should be update in the next iteration. Therefore we have to save the price to a buff and update the buff value within the same inner loop. After the inner loop, we can copy the buff value to the price value and do the next iteration.
355 Design Twitter
Complexity:
O(1) post/follow/unfollow, O(n + k log n) newsfeed for getting k tweets
from n followed users, with the O(n) part coming from constructing the
heap of followed users (see below), as correctly noted by @poligun.
Use
std::vector to store tweets, std::unordered_set to store followed users, std::unordered_map to associate each user with their tweets and followed users.
Use a heap to merge most recent k tweets from followed users.
std::make/push/pop_heap provide finer control than std::priority_queue.=====================================================================
hash map + priority_queue
451 Sort Characters By Frequency
(1) Count the frequency of each char in the string using a hash map (from char to int)
(2) Push the pairs of (int, char) into the priority_queue (max heap by default)
(3) append p.n copies of each p.c in for each pair of p at the priority queue top while its not empty
(4) return the result string.
373 Find K Pairs with Smallest Sums
Use customized min heap to solve this problem.
(1) Put all the possible pairs into the priority_queue and sort them according to their pair sum so that the smaller sum pairs will be in front of the queue
(2) Pop and save the top k pairs to the result array and return it.
378Kth Smallest Element in a Sorted Matrix
Put all the elements in a priority_queue (max heap).
Pop the top first n - k element, the (n - k + 1) th largest element will be the kth smallest element.
| 347 |
| 692 |
Only different is we have to define a customized compare function for priority_queue to make sure that words of the same length are outputted in the ascending order of alphabet.
We can define as follows:
typedef priority_queue< pair<int, string>, vector<pair<int, string> >, decltype(comp) > PQT;
PQT pq(comp); // Don't forget pass comp to pq definition.
Here we are sort the queue using descending order of frequency of words.
and ascending order of alphabet order for words with the same length, that's
why we use '<' for first and '>' for second. :-). Please remember that the default heap in C++ STL is max heap, which using smaller<int>(), we can pass in greater<int>() for the third parameter to
make a min heap. So we can consider that max heap is made from
ascending order while min heap is made from descending order. We know
ascending using '<' while descending using '>' for other
containers like vector.
return (a.first < b.first) || (a.first == b.first && a.second > b.second);
};
O(KlgN) time, O(N) space if no optimization (O(N - K)) space with opt.
Since insert into the heap is O(1) delete top from heap is O(lgN), we do K times of the deleting from the heap.
| 215 |
Solution 2: A slightly better way is to save only O(N - K + 1) largest element always. Pop the top if the size bigger than that. In the end return the top element which is the (N-K+1) smallest element, which is also the Kth largest element. Takes O(N-K+1) space and O(N) time.
264 Ugly Number II
(1) Define a min heap by customizing the priority_queue with a greater than compare func
(2) Push 1 into the priority queue initially
(3) Repeat the following step n - 1 times
(4) get the top element value and save it to tmp. while queue top equal to tmp keep popping the queue.
(5) Then push tmp * 2, tmp * 3, tmp * 5 on to the heap.
(6) return the top element as the nth ugly number.
| 313 |
Comments
Post a Comment