naji247
BAN USERpublic static String reverseStringByWord(String sentence){
int lastSpace =0;
for(int i =0; i < sentence.length; i++){
if(sentence.charAt(i) == ' '){
reverseString(sentence, lastSpace+1, i-1);
lastSpace = i;
}
}
}
public static void reverseString(String str, start, end){
char temp;
char[] charArr = str.toCharArray();
while(start < end){
temp = charArr[start];
charArr[start] = charArr[end];
charArr[end] = temp;
start++;
end--;
}
str = new String(charArr);
}
public static int depthOfTree(Node root){
if(root == null)
return 0;
return Math.max(depthOfTree(root.left), depthOfTree(root.right)) + 1;
}
public static int depthOfTreeIt(Node root){
if(root == null){
return 0;
}
Queue<Node> q = new Queue<Node>();
Queue<Node> nQ = new Queue<Node>();
q.enqueue(root);
int level = 0;
while(!q.isEmpty()){
Node v = q.dequeue();
if(v.left != null)
nQ.enqueue(v.left);
if(v.right != null)
nQ.enqueue(v.right);
if(q.isEmpty()){
level++;
q = nQ;
}
}
return level;
}
- naji247 October 27, 2014
Hi, I believe your first answer is not O(N*logk). For example, K= 100 of size 20:
- naji247 October 28, 2014100 -->merge to 50 of size 40 ea --> 25 of size 80 ea-->
12 of size 160 ea --> 6 of size 320 ea --> 3 of size 640 --> ...
50 + 25 + 12 + 6 + 3 + 2 +1 = 99 = K
Not to mention that the size at each step doubles so each step requires double the work.
So your solution is actually O(N*K)