grec.vs
BAN USERI could not come up with a solution without using an intermediate list to keep the nodes.
Looking at other solutions, it seems it can be done without.
private void traverseInWidth(ArrayList<Node> list) {
if (list.size() <= 0) {
return;
}
ArrayList<Node> temp = new ArrayList<Node>();
String data = "";
for (int i = 0; i < list.size(); i++) {
Node current = list.get(i);
data += current.data;
temp.addAll(current.children);
}
System.out.println(data);
list.clear();
traverseInWidth(temp);
}
And it is called like this:
ArrayList<Node> list = new ArrayList<Node>();
list.add(root);
traverseInWidth(list);
Hi all, this is my first submission! Here's the implementation in Java.
The drawback of this implementation I see, is that it duplicates the memory of input string by splitting it into a char array.
Suggestion for improvements are welcomed.
private static void runtimeLengthCode(String data) {
if (data.length() < 1) {
return;
}
char[] a = data.toCharArray();
char currentChar = a[0];
int count = 1;
StringBuilder result = new StringBuilder();
for (int i = 1; i < a.length; i++) {
if (currentChar == a[i]) {
count++;
} else {
result.append(currentChar).append(count);
currentChar = a[i];
count = 1;
}
}
result.append(currentChar).append(count);
System.out.println(result.toString());
}
}
If we are iterating till the middle of the array, we could have 2 pointers, one at the start of the array that will move forward, and one at the end of the array that will move backward.
It will give N/2 time complexity. But does this count as less than O(N)?
Feedback is welcomed. Thank you.
- grec.vs January 09, 2015