w****x
发帖数: 2483 | 1 //Merge two BST
//O(n) solution
//1. Change BST into linked list
//2. Merge 2 linked lists
//3. Change linked list into a balanced BST
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
////////////////////change BST to linked list///////////////////////////////
void _inner_chng_link(NODE* pNode, NODE*& ph, NODE*& pt)
{
if (NULL == pNode) return;
NODE* pLft1 = pNode;
NODE* pLft2 = pNode;
_inner_chng_link(pNode->pLft... 阅读全帖 |
|
w****x
发帖数: 2483 | 2
写一个
//Merge two BST
//O(n) solution
//1. Change BST into linked list
//2. Merge 2 linked lists
//3. Change linked list into a balanced BST
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
////////////////////change BST to linked list///////////////////////////////
void _inner_chng_link(NODE* pNode, NODE*& ph, NODE*& pt)
{
if (NULL == pNode) return;
NODE* pLft1 = pNode;
NODE* pLft2 = pNode;
_inner_chng_link(pNode-... 阅读全帖 |
|
w****x
发帖数: 2483 | 3 /*
add sibling pointer to the right sibling of each node in a tree, O(n) time,
O(1) space.
5 minutes thinking, 10 minutes coding, a hint he gave me: recursion
*/
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE* pSibling;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL), pSibling(NULL) {}
};
void LinkRightFromParent(NODE* pNode, NODE* pParent)
{
if (pNode == NULL) return;
//Under this situation, the current node will connect to the child of
current parent
if (pPa... 阅读全帖 |
|
w****x
发帖数: 2483 | 4 /*
add sibling pointer to the right sibling of each node in a tree, O(n) time,
O(1) space.
5 minutes thinking, 10 minutes coding, a hint he gave me: recursion
*/
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE* pSibling;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL), pSibling(NULL) {}
};
void LinkRightFromParent(NODE* pNode, NODE* pParent)
{
if (pNode == NULL) return;
//Under this situation, the current node will connect to the child of
current parent
if (pPa... 阅读全帖 |
|
w****x
发帖数: 2483 | 5 struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int x) : nVal(x), pLft(NULL), pRgt(NULL) {}
};
struct TreeIter
{
stack m_stk;
void movNext()
{
if (m_stk.empty())
return;
NODE* pCur = m_stk.top();
if (pCur->pRgt != NULL)
{
pushLft(pCur->pRgt);
return;
}
while (!m_stk.empty() && pCur != m_stk.top()->pLft)
{
pCur = m_stk.top();
m_stk.pop... 阅读全帖 |
|
w****x
发帖数: 2483 | 6 不用队列实现next连接
void LinkRightFromParent(NODE* pNode, NODE* pParent)
{
if (pNode == NULL) return;
if (pParent != NULL && pParent->pLft == pNode && pParent->pRgt
!= NULL)
pNode->pSibling = pParent->pRgt;
else
{
NODE* pIter = pParent == NULL ? NULL : pParent-
>pSibling;
NODE* pRgtCon = NULL;
while (pIter != NULL && pRgtCon == NULL)
{
if (pIter->pLft != NULL)
pRgtCon = pIter->pLft;
else if (pIter->pRgt != NULL)
pRgtCon = pIter->pRgt;
pIter = pIter->pSibling;
}
pNode->pSibling = pRgtCon;
}
LinkRightFro... 阅读全帖 |
|
w****x
发帖数: 2483 | 7 这题作的不下5遍了, 说实话, 第一次做还挺不容易的:
============带parent===========================
void InOrderPrint(NODE* pRoot)
{
assert(pRoot);
NODE* pCur = pRoot;
while (pCur != NULL)
{
while (pCur->pLft != NULL)
{
cout<nVal<
pCur = pCur->pLft;
}
cout<nVal<
//The ending condition is tricky but simple
while (pCur != NULL)//use "pCur != NULL" rather than "pCur->pParent
!= NULL"
... 阅读全帖 |
|
w****x
发帖数: 2483 | 8 //Get all trees according to preorder
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
void GetComb(int a[], int n, vector& vec)
{
if (n <= 0)
return ;
if (n == 1)
{
vec.push_back(new NODE(a[0]));
return;
}
vector vecTmp1;
GetComb(a+1, n-1, vecTmp1);
for (vector::iterator it = vecTmp1.begin();
it != vecTmp1.end(); it++)
{
NODE* pRoot = ne... 阅读全帖 |
|
w****x
发帖数: 2483 | 9 struct NODE
{
string str;
NODE* pLft;
NODE* pRgt;
NODE(const char* szStr = "") : str(szStr), pLft(NULL), pRgt(NULL) {}
};
void serialize(NODE* pNode, char*& p)
{
if (p == NULL) return;
if (pNode == NULL)
{
*((int*)p) = 0;
p += sizeof(int);
return;
}
int nLen = pNode->str.length();
*((int*)p) = 1;
p += sizeof(int);
strcpy(p, pNode->str.c_str());
p += nLen+1;
serialize(pNode->pLft, p);
serialize(pNode->pRgt... 阅读全帖 |
|
w****x
发帖数: 2483 | 10 struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
int getHeight(NODE* pNode, bool bLft)
{
int nRet = 0;
NODE* pIter = pNode;
while (NULL != pIter)
{
if (bLft)
pIter = pIter->pLft;
else
pIter = pIter->pRgt;
nRet++;
}
return nRet;
}
int getNum(int h)
{
return pow((double)2, h) -1;
}
int getNumberOfNodes(NODE* pRoot)
{
NODE* pNode = pRoot;
int h = get... 阅读全帖 |
|
w****x
发帖数: 2483 | 11 5 minutes
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
class BTIterator
{
public:
void Init(NODE* pRoot)
{ PushLefts(pRoot); }
NODE* Next()
{
if (m_stk.empty())
return NULL;
NODE* pRet = m_stk.top();
m_stk.pop();
PushLefts(pRet->pRgt);
return pRet;
}
private:
void PushLefts(NODE* pNode)
{
while (NULL != pNode)
{
m_stk.p... 阅读全帖 |
|
w****x
发帖数: 2483 | 12 struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
class CIterator
{
public:
CIterator(NODE* pRoot)
{
pushLft(pRoot);
}
NODE* GetNext()
{
if (m_stk.empty()) return NULL;
NODE* pRet = stk.top();
stk.pop();
pushLft(pRet->pRgt);
return pRet
}
private:
void pushLft(NODE* pNode)
{
NODE* pIt... 阅读全帖 |
|
p*****3
发帖数: 488 | 13 struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
class BTIterator
{
public:
void Init(NODE* pRoot)
{ PushLefts(pRoot); }
NODE* Next()
{
if (m_stk.empty())
return NULL;
NODE* pRet = m_stk.top();
m_stk.pop();
PushLefts(pRet->pRgt);
return pRet;
}
private:
void PushLefts(NODE* pNode)
{
while (NULL != pNode)
{
m_stk.push(pNode)... 阅读全帖 |
|
w**x
发帖数: 362 | 14 your code is not C++, but C.
No constructor.
No operator()++.
No destructor.
No current iter.
why void PushLefts(NODE* pNode) ?
Left is left not lefts.
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
class BTIterator
{
public:
void Init(NODE* pRoot)
{ PushLefts(pRoot); }
NODE* Next()
{
if (m_stk.empty())
return NULL;
NODE* pRet = m_stk.top();
m_stk.pop();
PushLefts(pRet... 阅读全帖 |
|
m**e
发帖数: 857 | 15 where did you get this info? Link?
IMF份额“洗盘”:中国将跃升为第三大份额国
2012年10月10日03:55
来源：中证网 作者：严婷
http://business.sohu.com/20121010/n354538844.shtml
世界经济版图已经发生巨大变化，全球治理的格局也将作出相应改革。本次国际货币基
金组织（IMF）与世界银行秋季年会将为2010年决定的IMF份额改革做最后冲刺。
这项改革意义深远，尤其对中国而言：超过6%的份额将从代表性过高的成员国转移
到代表性不足的新兴市场和发展中国家，而中国的份额将从目前的3.994%大幅上升至6.
390%，跃身为仅次于美国和日本的IMF第三大份额国，标志着中国的综合实力和全球话
语权的显著提升。
份额改革后中国将成第三大份额国
份额认缴（quota subscriptions）是IMF资金的主要来源。IMF的每个成员国都会
基于该成员国在世界经济中的相对地位被分配一定的份额（quota）。成员国的份额决
定了其向IMF出资的最高限额和投票权，并关系到其可从IMF获得贷款的限额。
2010年... 阅读全帖 |
|
w****x
发帖数: 2483 | 16
的却是很好的一个方案，不需要用heap, 因为一定是连续的
void _inner_mclosest(NODE* pNode, int nTg, int m, deque& que)
{
if (NULL == pNode)
return;
_inner_mclosest(pNode->pLft, nTg, m, que);
if (que.size() < m)
que.push_back(pNode);
else
{
if (abs(pNode->nVal - nTg) < abs(que.front()->nVal - nTg))
{
que.pop_front();
que.push_back(pNode);
}
}
_inner_mclosest(pNode->pRgt, nTg, m, que);
}
bool getMClosest2(NODE* pRoot, int nTg... 阅读全帖 |
|
w****x
发帖数: 2483 | 17 那个烙印这些题根本就是想灭你嘛， 楼主不要自责。
中国人最后那题可能是要这个解法：
void inner_get_rightmost(NODE* pNode, vector& vec, int nLev)
{
if (NULL == pNode)
return;
if (nLev >= vec.size())
vec.push_back(pNode);
inner_get_rightmost(pNode->pRgt, vec, nLev+1);
inner_get_rightmost(pNode->pLft, vec, nLev+1);
}
vector getRightMost(NODE* pRoot)
{
vector vec;
inner_get_rightmost(pRoot, vec, 0);
return vec;
} |
|
