hidro
BAN USERMemorize sub-paths so we don't calculate it again.
public Set<String> stairs(int n) {
List<Set<String>> list = new ArrayList<>();
list.add(new HashSet<String>(){{ put(""); }}); // 0
list.add(new HashSet<String>(){{ put("1"); }}); // 1
for (int i = 2; i <= n; i++) {
Set<String> set = new HashSet<>();
for (String sub : list.get(i - 1)) {
set.add("1" + sub);
}
for (String sub : list.get(i - 2)) {
set.add("2" + sub);
}
list.add(set);
}
return list.get(n);
}
@Pratik, by sorting absolute values, you are putting all start & end events in chronological order.
Now when you loop, if you encounter a positive number, it means a meeting is starting, you need an extra room so +1. If you encounter a negative number, it means a meeting has finished, you release a room so -1.
At the end of the loop, take max number of meeting room you need at any time to be results.
We can do a reversed BFS traversal. For each node, queue its right before its left. Remember the last dequeued node, set it as 'next' of the current dequeued node.
This will make all nodes at the same level points to the right one, except the right-most one will point to the first one at the upper level. We rectify this by traversing thru all the right-most nodes from root, and clear their 'next'.
If we can afford O(N) space, then we can use it to store an array of 'count' of consecutive chars:
- hidro May 17, 2015E.g., the following input string would result in the following count array (we don't count space)
'thiiis iss aa teeest seentennnce' => 11123101120120112311011211112311
It will take O(N) time to get this count array, then another O(N) to loop thru count array to print the character at position with max count value.