T_Dog
BAN USERtypedef struct __TreeNode
{
unsigned int val;
__TreeNode *left;
__TreeNode *right;
__TreeNode (unsigned int val) : val(val), left(NULL), right(NULL) {}
}TreeNode;
int getDigitCount(unsigned int n) {
if(n == 0) return 1;
int d = 0;
while(n) {
++d;
n /= 10;
}
return d;
}
void getMinMaxVerticalLevel(TreeNode *root, int curL, int &minL, int &maxL, int &maxDigits) {
if(root == NULL)
return;
if(curL < minL) minL = curL;
if(curL > maxL) maxL = curL;
int digitCount = getDigitCount(root>val);
if(digitCount > maxDigits)
maxDigits = digitCount;
getMinMaxVerticalLevel(root>left, curL  1, minL, maxL, maxDigits);
getMinMaxVerticalLevel(root>right, curL + 1, minL, maxL, maxDigits);
}
void itoa(char *str, unsigned int n) {
if(n == 0) {
*str = '0';
return;
}
char *orgStr = str; unsigned int r = 0;
while(n) {
r = n % 10;
n /= 10;
*(str++) = '0' + r;
}
str;
while(orgStr < str)
swap(*(orgStr++), *(str));
}
void PrintTree(TreeNode *root) {
if(root == NULL) return;
int minL = INT_MAX, maxL = INT_MIN, maxDigits = 0;
getMinMaxVerticalLevel(root, 0, minL, maxL, maxDigits);
int totalL = maxL  minL + 1;
string lineStr;
queue<TreeNode*> nodeQ; queue<int> levelQ;
nodeQ.push(NULL); levelQ.push(0);
nodeQ.push(root); levelQ.push(0);
int curL = 0, curD = 0;
bool lineFilled = false;
while(!nodeQ.empty()) {
root = nodeQ.front(); nodeQ.pop();
curL = levelQ.front(); levelQ.pop();
if(root == NULL) {
if(lineFilled) cout << lineStr.c_str() << endl;
while(!nodeQ.empty() && nodeQ.front() == NULL) {
nodeQ.pop(); levelQ.pop();
}
if(nodeQ.empty()) break;
lineStr = string(totalL * maxDigits, ' ');
lineFilled = false;
nodeQ.push(NULL); levelQ.push(0);
}
else {
if(root>left) {
nodeQ.push(root>left); levelQ.push(curL  1);
}
if(root>right) {
nodeQ.push(root>right); levelQ.push(curL + 1);
}
curD = getDigitCount(root>val);
itoa(&lineStr[maxDigits * (curL  minL) + ((maxDigits  curD) >> 1)], root>val);
lineFilled = true;
}
}
}
int main() {
TreeNode node10(10), node5(5), node15(15), node2(2), node8(8), node18(18), node7(7);
node10.left = &node5; node10.right = &node15;
node15.right = &node18; node5.left = &node2; node5.right = &node8; node8.left = &node7;
PrintTree(&node10);
return 0;
}

T_Dog
January 06, 2015 I made my own version of DP codes and here are some results:
===========================================
Now test len 2
The min operations for xx is 1
The min operations for ** is 2
The min operations for x* is 1
The min operations for *x is 1
===========================================
Now test len 3
The min operations for *x* is 1
The min operations for *** is 2
The min operations for **x is 2
The min operations for x*x is 2
The min operations for x** is 1
===========================================
Now test len 4
The min operations for **** is 3
The min operations for x**x is 2
The min operations for *x*x is 2
The min operations for xx** is 1
The min operations for x*** is 2
The min operations for **xx is 3
The min operations for xxxx is 2
===========================================
Now test len 5
The min operations for x**xx is 2
The min operations for ***xx is 3
The min operations for x*xxx is 3
The min operations for x*x*x is 2
The min operations for **xx* is 2
The min operations for *x*xx is 2
............
===========================================
Now test len 96
The min operations for ***xx*xx*x*x******xxxx*xxxx*xxx***xxxx*x**xxx**xx*xxx***xxxx*xxx***xx***x**xxx*x*x*xxxxx**x**xxx is 13
The min operations for x**xxx*****x**x*xxxx*x***xxxx***xx***xx****x**xx*xx**x**x****xx*xx**x*x*xx*x*x******x**x***xxx*x is 10
The min operations for x**xxx**x*xx***xx*xx***x*x*x*xxxxx*xxx*****xxxxx*xxxx***x*x***x**x***xx***x*x*xxx***x*xxxx*xxxx* is 5
The min operations for *x**x*xx**x***xx*xx**x***xxxxxxxx**xxxxxxx*xx****xxx*x***x**x*******xx**x*xx**x*xx***xx**xx*xxxx is 7
The min operations for *x***xx*x****x**x*****x***xx*x*x*xxxx*x*x**xxx*x*x*x*xx**x*xxxx**xx**x*x****xxxx**x*xx**x**x**** is 8
The min operations for *xxxxxxx***xx****x*xxx*xx*xx*xx******x*x*xx**xxx*xxx***x***x*xx******xxxxx*xx*x**x***xx****x*xxx is 4
The min operations for ***xx*x*x*x**xxxx*xx*x***x*x**xx*xx*x*xx*xxxxxx*xx*x*xxx*xxx*xx**xx*xxxx*xxx***x**xx***x*xx**x*x is 11
The min operations for **x****x**x**xxxx*******xx**xxx*x**x***x***x*x*xx*x*x***x*xx**x**x*xxx*****xxx*x*x**xx**xxxxx**x is 12
The min operations for x**x**x*x*****x****x**x***********xxxxx*xxx**x**x**xx***xxx**xxx*xx**xx*x*x**x*xx*xxx*x**xxxx*x* is 16
I can only think out two algorithms.
First one is sorting array and traversing the array like 3sum problem;
Second one is using hashing to record pair sums.
The first one's time complexity is O(n^3) and the second one's time complexity is O(n^2). Could anyone share a O(n^2) complexity at most with sorting? Thanks.
I write a DP solution and found one interesting thing. That is, the maximum lead change count is always min(S1, S2). So I guess there should be some math proof that can lead to this result. Can anyone give a math proof? Thanks.
These are some test results:
Max changes of 83 and 86 is 83
Max changes of 77 and 15 is 15
Max changes of 93 and 35 is 35
Max changes of 86 and 92 is 86
Max changes of 49 and 21 is 21
Max changes of 62 and 27 is 27
Max changes of 90 and 59 is 59
......
Max changes of 34 and 64 is 34
Max changes of 43 and 50 is 43
 T_Dog January 06, 2015