StartFromNeg1
BAN USER1. compare the median m_a, m_b of two array a, b
2. if same return the median
3. if different,
if m_a > m_b
//remove right half of a, or left half of b;
if length of a > length of b
remove left half of b, meanwhile remove left (length of b/2) elements of a
recursive;
if length of b > length of a
....
if m_a < m_b
....
seems BS() is incorrect,
before searching from each position (i, j), v[][] should be initialized to zero, not only v[i][j]
int BST2DLL(node** root)
{
stack<node*> s;
node* p = *root;
while(p -> lchild)
{
s.push(p);
p = p -> lchild;
}
//dummy head;
node* head = (node*)malloc(sizeof(node));
if (!head) return 0;
head -> lchild = head;
head -> rchild = head;
node* tail = head;
while(!IsEmpty(s))
{
node* tp = pop(s);
// link
tail -> rchild = tp;
tp -> lchild = tail;
tail = tp;
if(tp - > rchild)
{
node* ttp = tp -> rchild;
while(ttp)
{
push(ttp);
ttp = ttp->lchild;
}
}
}
tail -> rchild = head;
head -> lchild = tail;
return 1;
}
binary search:
int findOne(vector<int> a)
{
int start = 0;
int end = a.size() - 1;
int middle;
while(start >= 0 && start <= end)
{
middle = (start + end) / 2;
if(a.at(middle) == 1)
{
if(middle == 0 || a.at(middle - 1) == 0)
return middle;
else
{
end = middle - 1;
continue;
}
}
else
start = middle + 1;
}
return -1;
}
1. breadth first traversal the tree, push nodes into a stack.
- StartFromNeg1 March 01, 20122. while stack is not NULL, pop the top element in the stack, and add it's value with values of its child nodes. update the max value as well as the result node.
Am I right?