se01
BAN USERjava implementation:
public static boolean fancy_shuffle(String s) {
HashMap<Character, Integer> hm = new HashMap<>();
int max = 0;
char maxChar = 0;
for (char i : s.toCharArray()) {
if (hm.containsKey(i)) {
hm.put(i, hm.get(i) + 1);
} else {
hm.put(i, 1);
}
if (hm.get(i) > max) {
max = hm.get(i) + 1;
maxChar = i;
}
}
if (max > (s.length()+1)/2.0) {
return false;
}
Set<Character> hs = hm.keySet();
hs.remove(maxChar);
Iterator<Character> iterator = hs.iterator();
char[] sCopy = s.toCharArray();
int tracker = 0;
while (tracker < sCopy.length) {
for (char i : hs) {
if (hm.get(i) > 0) {
if (max > 0) {
sCopy[tracker++] = maxChar;
max--;
}
sCopy[tracker++] = i;
hm.put(i, hm.get(i) - 1);
} else {
hs.remove(i);
}
}
}
s = String.copyValueOf(sCopy);
return true;
}
Each node is either a left child or a right child. Make two hashmaps, one for lefts and one for rights; key is the parent id, and value is the child id.
Figure out which one the head is while you're adding all of the relations (O(n)). Then, starting with the head, do a DFS with the help of a stack and figure out the children accordingly!
- se01 April 24, 2015