sd
BAN USERvoid PrintPerimeter(node *root, bool isleft, bool isright)
{
if (!root)
return;
if (!root->l && !root->r)
{
printf("%d ", root->data);
return;
}
if (isleft)
printf("%d ", root->data);
PrintPerimeter(root->l, isleft, false);
PrintPerimeter(root->r, false, isright);
if (isright)
printf("%d ", root->r);
}
int main()
{
......
PrintPerimeter(root,true,true);
}
- sd November 13, 2013Provided a 2*2 matrix is given as input, the below should take O(n+m).
A n*n 2D Matrix.
A[i][j] = 0 means P[i] does not know P[j].
A[i][j] = 1 mean P[i] knows P[j].
A[i][i] = 1
1. Start from A[0][0]. Move row wise.. In other words we stick to the column [j] as long as we don't have evidence that P[j] can not be a mayor.
2. At each position A[i][j] (i.e. P[j] under consideration) check A[i][ j]
3. If 1(i.e P[i] knows P[j]) then P[j] can still be a mayor. Stay in that column do i++.
4. Else if 0 P[j] can never be a mayor do j++ and move to next column. Start scanning from current i. Don't reset it to 0.
5. Once you hit the end of a row. i.e. j = N. with i<N, then there is no mayor.
6. Else if you hit the end of a column. i.e. i = N, then scan the column a[i->N-1 to 0 ][j] for all 1s. If all are 1 then P[j] is the mayor. Else no mayor exist.
For e.g. Let say there a 4 ppl. A B C D. And C is the mayor.
Let say the matrix is:
A B C D
A 1 0 1 1
B 1 1 1 0
C 0 0 1 0
D 1 0 1 1
1. Arr[0][0] = 1 => i++.
2. Arr[1][0] = 0 => j++
3. Arr[1][1] = 1 => i++
4. Arr[2][1] = 0 => j++
5. Arr[2][2] = 1 => i++
6. Arr[3][2] = 1 => i++
i = 4 & j<4. Scan the Column j i.e.=2. all are 1s. Therefore C is the mayor.
Implementing a hexdec counter.
Assumption: Max value is FFFFFFFFF The counter will reset when it reaches this max value.
char IncrementChar(char ch)
{
switch (ch)
{
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
return (char) ((int) ch + 1);
break;
case '9':
return 'A';
break;
case 'A':
case 'B':
case 'C':
case 'D':
case 'E':
return (char) ((int) ch + 1);
break;
case 'F':
return '0';
break;
default:
return ' ';
break;
}
}
char* IncrementString (char *str)
{
if( !strcmp(str,"FFFFFFFFF"))
return "000000000"; // Reset the counter after it reaches max
for (int i=8; i>=0;i--)
{
str[i] = IncrementChar(str[i]);
if ( str[i] != '0')
return str;
}
return str;
}
int _tmain(int argc, _TCHAR* argv[])
{
char num[10] = "000000000";
// Print value till FFF
while(strcmp(num,"000000FFF") != 0)
printf("%s\n" , IncrementString(num));
return 0;
}
OriginalNode1 --> CopiedNode1 --> OriginalNode2 --> CopiedNode2 --> OriginalNode3 --> CopiedNode3 --> NULL
The above linklists merge as well as separation should be simple.
Now, lets say OriginalNode1 --> Arbitrary = OriginalNode3
So, as per the above Arbitrary pointer updation logic
Originalnode1 -->next --> Arbitrary (= CopiedNode1 --> Arbitrary) = OriginalNode1 --> Arbitrary --> next (= OriginalNode3-->next = CopiedNode3)
which is essentially same as CopiedNode1 --> Arbitrary = CopiedNode3
And so on....
Dynamic programming approach:
Let S[I][J] denote the min valued operation required to convert the 1st I chars of A into first J chars of B.
Let Cd Ci Cr denote the cost pf deletion, insertion and replacement respectively.
S[0][J] = 0;S[I][0]=0;
S[I][J] = MIN ( S[I-1][J] + Cd , S[I][J-1] + Ci , (A[I] == B[J])? S[I-1][J-1], S[I-1][J-1] + Cr )
S[A.size()][B.size()] gives the optimal solution.
1. copy the 1st node and insert it between node 1 & node 2
3. Similarly, copy 2nd node and insert it between 2 & 3.. and so on
2) Copy the arbitrary link in this fashion
Originalnode->next->arbitrary = Originalnode->arbitrary->next;
and so on...for all nodes
3) Separate the original and copy linked lists.
string to_string(float f)
{
stringstream str;string s;str<<f;str>>s;return s;
}
int no_of_zero(string s)
{
int i=0,l=s.length();bool dotpresent=false;
while(i<l && s[i]!='.'){i++;if(s[i]=='.')dotpresent=true;}
if(!dotpresent)return 0;
while(s[--l]=='0');
return l-i;
}
int main()
{
float f;cin>>f;//no to b converted
cout<<no_of_zero(to_string(f))<<endl;
system("pause");
return 0;
}
note that we can take any floating point no directly as input string...
In this case to_string will be redundant...
- sd July 05, 2014