tetura
BAN USERDon't understand why we need two queues, one is sufficient. Steps should be like,
1. push root to the queue.
2. if queue is NOT empty
pop the element from the queue.
print it.
if the element has any children,
push all its children to the queue.
Repeat step 2 until queue is empty.
Any comments?
This is not correct. If root has left and right sub tree of different structure, still it will return true, since first if condition will be satisfied.
code should be like this,
int areMirrorImages(struct node* left, struct node* right)
{
if (left == NULL && right == NULL)
return true;
else if (left != NULL && right != NULL)
return ( areMirrorImages(left->left, right->right)
&& areMirrorImages(left->right, right->left));
else
return false;
}
See the below code.
The logic here is, we will check if the HashMap contains the character or not.
If not, we will continue pushing the character, and if present that means, we found the first repetitive character. Now that character can be the first character in the String or not.
For eg.
abca = Here, non repetitive char is b, so, if the repetitive character is first element, we will take the 2nd element
or, abcb = Here no repetitive char is a, so, if the repetitive character is NOT first element, we will take the 1nd element.
private char usingHashing(String s)
{
Map m = new HashMap();
for (int i=0;i<s.length();i++)
{
char c = s.charAt(i);
if (! m.containsKey(c))
{
m.put(c,i);
}
else
{
int j = ((Integer)m.get(c)).intValue();
if (j==0)
{
return s.charAt(1);
}
else
return s.charAt(0);
}
}
return ' ';
}
we need not to scan entire string, we will stop when there is a repetition, and we will start scan again. complexity O(k) where k=position of first repeated char
private char findIt(String s)
{
boolean[] bit = new boolean[26];
int index=-1;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if (bit[c-97]==true){
index=i;
bit[c-97]=false; // reset it back to false, so now we have first group of non repetitive chars
break;
}
else
bit[c-97]=true;
}
if (index==-1) System.out.println("no repet");
for (int j=0;j<index;j++){
char cc = s.charAt(j);
if (bit[cc-97]==true)
return cc;
}
return 0;
}
Answer is 13, here is the explanation.
- tetura May 11, 2011first, lets group them with 9 horses, we now have 9 groups.Each group will have one race(9 races).
Among the winners of each group, we will have another race (+1 race).
So what we have now?
Winner of 10th race is the fastest horse among 81 horses.
Since we have to find out first 6 fastest horses, we will eliminate all except,
(where A1 is the fastest horse in the 10th race, and F1 is the slowest horse in the 10th race A1> B1>C1>D1>E1>F1 in 10th race)
and A1>A2>A3>A4>A5>A6 in the first race, same for other groups
A1 B1 C1 D1 E1 F1
A2 B2 C2 D2 E2
A3 B3 C3 D3
A4 B4 C4
A5 B5
A6
why?
because, all other horses cannot be among the first 6 fastest horses(think :)).
Now, A1 is already fastest.
2nd fastest must be either A2 or B1
3rd fastest must be either A3, B2 OR C1
4th fastest must be either A4, B3, C2, D1
we will conduct another race(11 th race) among them.
Winner, first runners up, and 2nd runners up are 2nd, 3rd and 4th fastest among 81.
Note that, still 2nd position must be held by either A2 or B1.3rd position by A3, B2, OR C1. And 4th position by A4, B3, C2, OR D1.
5th fastest must be either A5,B4,C3,D2 OR E1 = have a race(12th race) and winner is 5th fastest. NOTE THAT WE CANNOT DETERMINE 6TH FASTEST HERE. FOR THIS, WE MUST CONDUCT ANOTHER RACE.
6th fastest must be either A6,B5,C4,D3,E2,F1 = have the last race(13th race)