1. LeetCode 56 : Merge Intervals?
Solution:
First sort the array using lambda or comparator defined by yourself. Then loop the array. For every item in the array, compare the start of current item and the end the last item pushed in the result array. Here is the example: [[1, 4], [4, 5]], in this case we should combine two items, in other words, update the end of first item. [[1, 4], [5, 6]], in this case, we could just push the item into result array.
Learned: Python Sort
Sort will not change the list but sorted will change. However, sorted are more powerful since it could sorted by keys, comparators as well as reverse. Keys are helpful according to list elements and its attributes. This techniques is fast because the key function is actually called once for each input record. Example: sorted(student_tuples, key=lambda student: student[2]) . Comparators is much like in c++.? def reverse_numeric(x, y):return y - x sorted([5, 2, 4, 1, 3], cmp=reverse_numeric)?
For lambda, its expression is much like lambda arguments1, argument2.. : return value
2. Top K Problem
Problem1: LeetCode 347 Top K Frequent Elements
Solution:
The context mentioned that the complexity should be better than O(nlogn) so sorting is not the way. Here we have to two solutions. First, in C++, use map + nth_element. The expected running time of nthe_element is O(N). The worst case running time for most implementations is O(N * N) because most implementations use QuickSelect and it could be that QuickSelect runs into bad partitions. Second, in Python, use bucket sort + dict. I really like the nice and succinct code in LeetCode. Here is what he wrote.
Learned:
1. nth_element complexity is O(n) of expected running time but O(n * n) for the worst cases. ? ??
2. In Python list comprehension: thing for thing in list_of_things: This is a way to construct list ?
3. itertools.chain: Make an iterator that returns elements from the first iterable until it is exhausted and it is used for treating consecutive sequences as a single sequence. So in the case below, it will ignore the empty element.?
4. Counter will count the element frequency and return a dict. dict.items() will return a list whose elements are much like pair(first, second) actually it is a tuple and the first is the element, the second is the frequency.?
5. Bucket Sort: Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. In this case, the bucket width is 1. In LeetCode 220 Contains Duplicate III, it is one of the solutions.?
Problem2: LintCode 544 Top k Largest Numbers
Probem3: LintCode 545 Top k Largest Numbers II
Solutions:
C++: Priority_queue plus multiset. Python: Heapy
Learned:
By default, in C++, its comparator returns the same as applying the less-than operator (a < b). It means, it's top is the largest value of current heap. In Python, we use heapy. heapq.nlargest(k, iterable[,key]) will return Return a list with the n largest elements from the dataset defined by iterable; heapq.heapify(x) will transform list x to a heap. The interesting property of a heap is that a[0] is always its smallest element; heapq.heappop(heap), pop and return the smallest item from the heap, maintaining the heap invariant. If the heap is empty, IndexError is raised. To access the smallest item without popping it, use heap[0].
3. Contains Duplicate I, II, III?
Solution:
In the 1st and 2nd problem, use set and dict+map. For the third problem, we have constrains: find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
In C++: we create a window whose length is k. The data structure is set. We also have a function called lower_bound which returns iterators first no less than the given value. The value pointed by the iterator returned by this function may also be equivalent to value. Set is actually a BST and it is sorted so we could use lower_bound. We need to find the pos nums[i] ?- t.
In Python, we use bucket sort. The length of bucket constructed by dictionary is setted to t + 1 to avoid case t = 0. Still, we maintains a window which width is k. Every time, we have new item. pos = nums[i]/ width. If it is in the bucket, the array contains duplicated items. If not, try bucket[pos + 1] and bucket[pos - 1] and test the difference is whether smaller than width(t + 1) The idea could be concluded as consecutive buckets covering the range of nums. The width of one bucket is t + 1. If two numbers, the index difference is smaller than k, they are in the same window. If the difference between actual value is smaller than t, then
Two numbers are in the same bucket.
Two numbers are in the neighbor buckets
Learned:
In C++, for set insert functions, the return value is a pair. The first value is a pointer pointing to either the newly inserted element or to the equivalent element already in the set. The second value is true if a new element was inserted or false if an equivalent element already existed.
In Python, range vs xrange. range create a list and it occupies memory. Xrange, mostly fast, it returns a object, like generators, rather than a list.?
4. Permutations Problem
Problem1: Next Permutation/Previous Permutation
Given a list of integers, which denote a permutation. Find the next/ previous permutation in ascending order. It is actually the same problem. We can use the similar way to deal with it. In this section, let us talk about the next permutation.
Solution:
Find the rightmost character in it, which is smaller than its next character. Let us call this character as ‘first character’. Example: 4 2 1 5 6 10 7 9 8. 7 is what we want. Then find the ceiling of the ‘first character’ and its position X. Ceiling is the smallest character on right of ‘first character’, which is greater than ‘first character’. Let us call the ceil character as ‘second character’. Swap the first and second character. Sort X right part numbers in default increasing order.?
Learned:
In Python, else could follow for loops. Loop statements may have an else clause; it is executed when the loop terminates through exhaustion of the list (with for) or when the condition becomes false (with while), but not when the loop is terminated by a break statement. Range could generate list in decreasing order. Example: range(start, end, -1).?
Problem2: Permutation Index I & II
Solution:
The first problem is dealing with unique numbers while the second problem is dealing with the duplicated numbers. For the first problem, we need the rank list of the numbers. We calculate the rank of number and use it to multiply the factorial. Example: 4, 1, 2. 4 is third and there are actually 2 numbers smaller than 4. So 2 * A(2,2) = 4. 1 is the first 0 * A(1,1) and 0 * A(0, 0). Finally, sum plus one is our results. We need to update the ranking list every time.
Here is the key to second problem. When we have duplicate numbers, we need use the all numbers factorials value divide the duplicate numbers factorials. Here is the case. 1, 1, 2, 2, 3, 4. The permutation value is A(6,6) / (A(2,2) * A(2,2)). In such cases, we need a map and updated it every time. Here is the C++ Code.
Learned:
How to calculate duplicate permutation index?
Problem3: Permutation Sequence
Solution:
The idea is actually reverse of the Problem2. Now, we have the index and we need to generate the sequence. Remember: k = (k - 1) % factorial[n - i - 1] + 1 for every time update.?
Learned:?
Python, change the list to string. "".join([str(i) for i in target_list])
Problem4: Permutations I & II and String Permutation II
Solution:
Permutations II is the problem with duplicated numbers. String Permutation II is just String version of Permutations II. For the first problem, it is a backtracking problem. For the second problem, add the visited vectors for help. Here is the C++ code. Here we need put more attention on the visited[i - 1]. If it is true, we will have much more useless loops. Here is the small case. [1, 1, 1] If we use false, we only need to call helper functions for 8 times while for true, it need 3 times. Here is the visited state in function calling.?
0 0 0 ? 1 0 0 ??1 0 1 ? 0 1 0 ? ?1 1 0 ? ?0 0 1 ? ?1 0 1 ? ?0 1 1 ? ?1 1 1 (visited[i - 1] = true, pass)
0 0 0 ? 1 0 0 ? 1 1 0 ? 1 1 1 (visited[i - 1] = false, pass)?
Problem5: Next Permutation II?
Solution:
Dealing with the duplicated numbers. Challenge in place. Similar way to the Permutation I. In finding the second position, we can find from the rightest to left. Once bigger, that is what we want. Swap them and reverse that part.?
