yangxh92
BAN USERdef driver(arr, n, m):
if len(arr) == 0:
return set(range(1, n + 1))
s = set()
for i in range(1, arr[0]):
s.add(i)
bst(arr, 0, n - m - 1, 0, s)
for i in range(arr[n - m - 1] + 1, n + 1):
s.add(i)
return s
def bst(arr, left, right, miss, s):
if right - left <= 1:
for i in range(arr[left] + 1, arr[right]):
s.add(i)
return
mid = (left + right) / 2
diff = arr[mid] - mid - 1
if diff > miss:
bst(arr, left, mid, miss, s)
miss = diff
bst(arr, mid, right, miss, s)
n = 8
arr = [1, 2, 4, 5, 6, 8]
m = n - len(arr)
s = driver(arr, n, m)
print s #set([3, 7])
Driver prints out the numbers between 1 and the smallest number in list, process the list, and prints out the numbers between the largest number in list and n.
In function bst, variable "miss" stands for number of founded missing numbers on the left of arr[mid], variable "diff" means the number of missing numbers on the left of arr[mid].
Therefore, if diff > miss, it means there are some missing numbers we didn't found on the left of arr[mid], thus we need to search the left part of the list. Otherwise, we can proceed to the right part.
Assume that now you know there are M sub-combinations will form left subtree, and N sub-combinations will form right subtree. Now all you need to know is how many combinations can they form?
Let's assume the size of left subtree is P, the size of right subtree is Q, and P <= Q, then the answer is C(P, Q + 1) * N * M. That is, in the new combination, first you fix Q positions for the right subtree, then you need to insert a combination with P elements into the new combination. Now there are Q + 1 possible place to insert, you need to choose P out of Q + 1 positions, that is C(P, Q + 1). After the positions are fixed, multiply the result by the number of possible permutations.
If the question is to find the number of combinations that would result in the exact same binary tree as the input list, I doubt the correctness of the first test case.
To calculate the result, we need to know how many permutations exist with constrain root always occur before its children(the order of occurrence of siblings does not matter), we can use some math trick to do that. However, I'll just display all possibilities here.
Let's look at the left subtree: 8, 6, 9, 4, 5, we have 8 permutations to generate this subtree:
8, 6, 4, 5, 9
8, 6, 4, 9, 5
8, 6, 5, 4, 9
8, 6, 5, 9, 4
8, 6, 9, 4, 5
8, 6, 9, 5, 4
8, 9, 6, 4, 5
8, 9, 6, 5, 4
Since the first position is fixed to 10, insert 15 to any position of any permutation shown above, then we'll get 8 * 6 = 48 permutations which form the same binary tree as the input list, rather than 24
Let list[i:j] be the sub-list containing: list[i], list[i + 1], ..., list[j].
If the kth element in the list is the root, then there could be count(list[i:k - 1]) * count(list[k + 1:j]) unique binary search trees which have element k as their roots. Increase k from 1 to n and count the number recursively, you'll get the answer.
Traverse the grid from left to right, top to bottom. For each cell, check if any words that start from this cell is in the dictionary. If current word is in the dictionary or the length of current word has exceeded the maximum length of words in dictionary, you can skip to next cell.
If the grid A has size N*M, dict has size K, the strings in dict has a maximum length of L, then the time complexity will be
O(NM(min(max(N, M), L) + log K))
Vector is implemented base on array, say size m.
1. If the array is full, create a new array of size 2m, copy the elements from original array to the new one, and put the to-be-inserted element into the new array
2. The size gets doubled.
3. If the array has size 0 for initialization, then you need log n copies to insert n elements.
Put those years into an array, then you get an array with length 2n. Sort those years, sequence through the array and maintain a variable count. If you meet a birth year, plus one to count, otherwise minus one. Every time you need to update, compare count with the maximum result so far, if count > maximum, then you need to update maximum and the year which maximum occurs.
class Year {
public:
int year;
string type;
friend bool operator<(const Year &y1, const Year &y2) {
return y1.year < y2.year;
}
};
//The following function returns the last period that max people were alive
pair<int, int> maxAlive(vector<People> people) {
vector<Year> years;
for (People p : people) {
Year birth, death;
birth.year = p.birth;
birth.type = "birth";
death.year = p.death;
death.type = "death";
years.push_back(birth);
years.push_back(death);
}
sort(years.begin(), years.end());
int maximum = 0, count = 0, max_beg = 1900, max_end = 1900;
for (Year y : years) {
if (y.type == "birth") {
count++;
if (maximum <= count) {
maximum = count;
max_beg = y.year;
}
}
else {
if (maximum == count)
max_end = y.year;
count--;
}
}
return pair<int, int>(max_beg, max_end);
}
My mistake, I drew a wrong tree
- yangxh92 December 07, 2014