t4k9
BAN USERWe will use dynamic programming by creating an int[] count array, where each element, count[i], stores the number of strings we can make with a substring starting from i. For example, input = "01234", count[3] = # of diff strings of "34", count[2] = # of diff string of "234".
To find count[0], we use a the following relationship:
Number of different string of "1234" = number of different string of "234" + number of different string of "34" if "12" is in the mapping lookup table.
Let LU be the lookup table containing the keys, and let N = input length. Then, initialize count[N] = 1, count[N-1] = 1 and follow the relationship
count[i] = count[i+1] + LU.containsKey(input.substring[i, i+2])? count[i+2]: 0;
Loop through i from N-2 to 0.
Finally, count[0] is what we are looking for.
Perform pair-wise comparison on the initial n ints. This costs n/2 ops.
Collect the winners in the winner set and losers in the loser set. Each set has n/2 items.
Find the max of winner requires n/2 ops.
Find the min of loser requires n/2 ops.
Overall, it requires 3/2 n + c ops.
Special care is needed for tied result in the original pair-wise comparison: when a pair is tied, grab the next number and do compare.
If there is a left-over after all pair-wise comparison, put it in both the winner and loser brackets.
We will use a recursive algorithm to find the max score. The recursive function will take in the employee node, an n-ary node, and a Boolean parameter: bossIsGoing. Idea: At a node x, if boss is going, x won't go, recursively attempt to invite all his/her subordinate; if boss is not going, decide whether x will go or not using recursion.
- t4k9 January 25, 2015