开赌7月排期吧 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>EB23 - 劳工卡

开赌7月排期吧

开赌7月排期吧# EB23 - 劳工卡

w*x2014-05-15 07:05

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, pLft1, pLft2);
if (pNode != pLft2) //forget this link logic
{
pNode->pLft = pLft2;
pLft2->pRgt = pNode;
}
NODE* pRgt1 = pNode;
NODE* pRgt2 = pNode;
_inner_chng_link(pNode->pRgt, pRgt1, pRgt2);
if (pNode != pRgt1) //forget this link logic
{
pRgt1->pLft = pNode;
pNode->pRgt = pRgt1;
}
ph = pLft1;
pt = pRgt2;
}
NODE* ChngToLink(NODE* pRoot)
{
assert(pRoot);
NODE* ph = pRoot;
NODE* pt = pRoot;
_inner_chng_link(pRoot, ph, pt);
return ph;
}
//////////////////////////////////////////////////////////////////////////
///////////////////Merge 2 linked lists/////////////////////////////////
NODE* MergeLink(NODE* pHead1, NODE* pHead2)
{
assert(pHead1 && pHead2);
NODE* pNewHead = NULL;
NODE* pIter = NULL;
NODE* pIter1 = pHead1;
NODE* pIter2 = pHead2;
while (pIter1 != NULL && pIter2 != NULL)
{
NODE* pTmp = NULL;
if (pIter1->nVal <= pIter2->nVal)
{
pTmp = pIter1;
pIter1 = pIter1->pRgt;
}
else
{
pTmp = pIter2;
pIter2 = pIter2->pRgt;
}
if (pIter == NULL)
{
pNewHead = pTmp;
pIter = pTmp;
}
else
{
pIter->pRgt = pTmp;
pTmp->pLft = pIter;
pIter = pIter->pRgt;
}
}
if (pIter1 != NULL)
{
pIter->pRgt = pIter1;
pIter1->pLft = pIter;
}
if (pIter2 != NULL)
{
pIter->pRgt = pIter2;
pIter2->pLft = pIter;
}
return pNewHead;
}
//////////////////////////////////////////////////////////////////////////
////////////////Construct BST from linked list/////////////////////////////
NODE* _inner_construct(NODE* pHead, int nLen)
{
if (NULL == pHead || nLen <= 0)
return NULL;
NODE* pNode = pHead;
int nCount = (nLen + 1)/2;
for (int i = 1; i < nCount; i++)
pNode = pNode->pRgt;
pNode->pLft = _inner_construct(pHead, (nLen + 1)/2 - 1);
pNode->pRgt = _inner_construct(pNode->pRgt, nLen - (nLen + 1)/2);
return pNode;
}
NODE* ConstructBST(NODE* pHead)
{
assert(pHead);
int nLen = 0;
NODE* pIter = pHead;
while (pIter != NULL)
{
nLen++;
pIter = pIter->pRgt;
}
return _inner_construct(pHead, nLen);
}
//////////////////////////////////////////////////////////////////////////
NODE* MergeBST(NODE* pRoot1, NODE* pRoot2)
{
assert(pRoot1 && pRoot2);
NODE* ph1 = ChngToLink(pRoot1);
NODE* ph2 = ChngToLink(pRoot2);
NODE* ph = MergeLink(ph1, ph2);
return ConstructBST(ph);
}
---- 30 min with IDE

c*42014-05-15 07:05

2 楼

y*u2014-05-15 07:05

3 楼

我觉得唉
这个solution可能不对
谁都想得出来啊。。。

//

【在 w****x 的大作中提到】

: //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;

d*02014-05-15 07:05

4 楼

赌上全副身家，7月EB3不到2009年11月。。。。输了就太开心了。。。

【在 c*****4 的大作中提到】

: RT

p*22014-05-15 07:05

5 楼

不错。我也想做做呢。先mark一下。晚上我也试试。

c*y2014-05-15 07:05

6 楼

好不容易攒了8个包子准备绿了发...
要么就赌一赌吧

w*x2014-05-15 07:05

7 楼

为啥不对, 这题就是把BST->linkedlist, merge linked list, construct balance
BST from linked list合起来

s*c2014-05-15 07:05

8 楼

7月，2009年10月。

y*u2014-05-15 07:05

9 楼

这样感觉就没什么意思了。。。就是基础题啊

【在 w****x 的大作中提到】

: 为啥不对, 这题就是把BST->linkedlist, merge linked list, construct balance
: BST from linked list合起来

d*02014-05-15 07:05

10 楼

10月，。。几号是个问题。。。

【在 s********c 的大作中提到】

: 7月，2009年10月。

w*x2014-05-15 07:05

11 楼

写写看嘛~~~ 没那么基础. 我觉得一般公司这题够涮掉至少95%以上的人了

【在 y**********u 的大作中提到】

: 这样感觉就没什么意思了。。。就是基础题啊

c*22014-05-15 07:05

12 楼

Eb3c不可能动。 eb3i 继续前进

p*22014-05-15 07:05

13 楼

这么长，面试不死定了？

w*x2014-05-15 07:05

14 楼

面试给45分钟做这题

【在 p*****2 的大作中提到】

: 这么长，面试不死定了？

t*22014-05-15 07:05

15 楼

为啥不用vector用linked list?

w*x2014-05-15 07:05

16 楼

BST自己就是linked list啊, vector要额外空间

【在 t*****2 的大作中提到】

: 为啥不用vector用linked list?

t*e2014-05-15 07:05

17 楼

Maybe we can do 2 in order traversal at the same time and construct trees
from smallest element.
Here is a way to construct tree from smallest element:
http://www.leetcode.com/2010/11/convert-sorted-list-to-balanced

p*22014-05-15 07:05

18 楼

写了一下BT 到 linkedlist不好写呀。
Node Convert(Node node)
{
Node head;
if (node.left == null)
head = node;
else
{
Pair1 pair = Change(node.left, null, node, true);
node.left = pair.max;
head = pair.min;
}
if (node.right != null)
{
Pair1 pair = Change(node.right, node, null, false);
node.right = pair.min;
}
return head;
}
Pair1 Change(Node node, Node prev, Node next, boolean left)
{
Pair1 pp = new Pair1(null, null);
if (node.left == null)
{
node.left = prev;
pp.min = node;
}
else
{
Pair1 pair = Change(node.left, prev, node, true);
node.left = pair.max;
pp.min = pair.min;
}
if (node.right == null)
{
node.right = next;
pp.max = node;
}
else
{
Pair1 pair = Change(node.right, node, next, false);
node.right = pair.min;
pp.max = pair.max;
}
return pp;
}
}
class Pair1
{
Node min;
Node max;
public Pair1(Node _min, Node _max)
{
min = _min;
max = _max;
}
}
class Node
{
int value;
Node left;
Node right;
public Node(int v)
{
value = v;
}
}

w*x2014-05-15 07:05

19 楼

为啥总觉得你整地代码那么长呢...
用c做代码会短些

【在 p*****2 的大作中提到】

: 写了一下BT 到 linkedlist不好写呀。
: Node Convert(Node node)
: {
: Node head;
: if (node.left == null)
: head = node;
: else
: {
: Pair1 pair = Change(node.left, null, node, true);
: node.left = pair.max;

y*u2014-05-15 07:05

20 楼

左括号占的行数比较多。。。

【在 w****x 的大作中提到】

:
: 为啥总觉得你整地代码那么长呢...
: 用c做代码会短些

p*22014-05-15 07:05

21 楼

算了。用C去面试吃了大亏了。用C当然是灵活很多了。有指针。

【在 w****x 的大作中提到】

:
: 为啥总觉得你整地代码那么长呢...
: 用c做代码会短些

b*h2014-05-15 07:05

22 楼

【在 w****x 的大作中提到】

p*22014-05-15 07:05

23 楼

我一直不习惯把左括号放到上一行，咋办呀。如果那样我看起程序来很费劲。

【在 y**********u 的大作中提到】

: 左括号占的行数比较多。。。

w*x2014-05-15 07:05

24 楼

除了这个括号外我还是觉得太多了

y*u2014-05-15 07:05

25 楼

其实我觉得不比你的长啊
而且你的参数传递是指针类型的引用。。。

【在 w****x 的大作中提到】

: 除了这个括号外我还是觉得太多了

b*h2014-05-15 07:05

26 楼

不能直接用树?为啥要转换成linked list呢?

【在 w****x 的大作中提到】

l*82014-05-15 07:05

27 楼

转换成linked list后是O(N)算法
直接从一个bst逐个取出node插入到另一个bst，是O(N*logN)算法

【在 b********h 的大作中提到】

: 不能直接用树?为啥要转换成linked list呢?