We were discussing young's tableau yesterday and spotted the mistake we saw in a version of the online solution.
The correct solution is something like this :
void youngify(int[,] m, int N, int i, int j)
{
int si = i;
int sj = j;
if (i+1<=N and m[i,j] > m[i+1,J]){
si = i + 1;
sj = j;
}
if (j+1<=N and m[i,j] > m[i,j+1]{
si = i;
sj = j + 1;
}
if (si != i && sj != j){
Swap(m[si,sj], m[i,j]);
youngify(m, N, si, sj);
}
}
Insertion is also recursive and can be applied backwards.
Insert(m,k)
m[m,n] = k
Youngify(m,n)
Youngify(Y,i,j)
{
li = i;
lj = j;
if (i-1>=1 && m[i,j] < m[i-1,j]){
li = i-1;
lj = j;
}
if (j-1 >= 1&& m[li, lj] < m[i,j-1]){
li = i;
lj = j-1;
}
if (li !=i || lj !=j){
swap(m, i,j,li,lj)
Youngify(m,li,lj);
}
}
#one more coding question
Determine chain length of a binary tree. A chain length is the sum of the left node series, the right node series and one.
1
2 3
4 5 6 7
8 9
has chain length 3 + 2 + 1 for nodes 8,4,2,1,3,7
int chainlength(node root)
{
int ret = 1;
node left = root.left;
while(left){ ret+=1; left = left.left;}
node right = root.right;
while(right){ ret+=1; right = right.right}
return ret;
}
The correct solution is something like this :
void youngify(int[,] m, int N, int i, int j)
{
int si = i;
int sj = j;
if (i+1<=N and m[i,j] > m[i+1,J]){
si = i + 1;
sj = j;
}
if (j+1<=N and m[i,j] > m[i,j+1]{
si = i;
sj = j + 1;
}
if (si != i && sj != j){
Swap(m[si,sj], m[i,j]);
youngify(m, N, si, sj);
}
}
Insertion is also recursive and can be applied backwards.
Insert(m,k)
m[m,n] = k
Youngify(m,n)
Youngify(Y,i,j)
{
li = i;
lj = j;
if (i-1>=1 && m[i,j] < m[i-1,j]){
li = i-1;
lj = j;
}
if (j-1 >= 1&& m[li, lj] < m[i,j-1]){
li = i;
lj = j-1;
}
if (li !=i || lj !=j){
swap(m, i,j,li,lj)
Youngify(m,li,lj);
}
}
#one more coding question
Determine chain length of a binary tree. A chain length is the sum of the left node series, the right node series and one.
1
2 3
4 5 6 7
8 9
has chain length 3 + 2 + 1 for nodes 8,4,2,1,3,7
int chainlength(node root)
{
int ret = 1;
node left = root.left;
while(left){ ret+=1; left = left.left;}
node right = root.right;
while(right){ ret+=1; right = right.right}
return ret;
}
No comments:
Post a Comment