|
w***o 发帖数: 109 | 2 看到很多解法都是in-order遍历两个BST,merge两个array,然后再重构BST,为什么这
么啰嗦?
不能这样直接merge吗?基本思想就是,比较root1和root2,如果root2大的话,把
root2断为两个子树,一个的根是root2的左孩子,另一个是root2及其右子树。把root2
及其右子树与root1的右子树合并,把root2的左孩子与root1继续合并:
Node mergeBST(Node root1, Node root2) {
if (root1 == null || root2 == null)
return root1 == null? root2 : root1;
if (root1.data <= root2.data)
{
Node left = root2.left;
root2.left = null;
root1.right = mergeBST(root1.right, root2);
root1 = mergeBST(roo... 阅读全帖 |
|
a*****y 发帖数: 22 | 3 bool IsIdenticalTree(const Node* root1, const Node* root2) {
if (root1 && !root2) {
return false;
} else if (!root1 && root2) {
return false;
} else if (!root1 && !root2) {
return true;
} else if (root1->data != root2->data) {
return false;
} else if (root1->next.size() != root2->next.size()) {
return false;
}
for (int i = 0; i < root1->next.size(); ++i) {
if (!IsIdenticalTree(root1->next[i], root2->next[i])) {
return false;
}
}
return true;
}
... 阅读全帖 |
|
n*****g 发帖数: 16 | 4 感觉你那个merge 2 BST的程序有点问题。看看下面这个code:
Node* MostLeft(Node *root)
{
if(root->left == NULL)
return root;
else
return MostLeft(root);
}
// Merge two BST in to one BST.
Node* MergeTwoBST(Node* root1, Node* root2)
{
Node *left, *right, *mostLeft;
if(root1 == NULL)
return root2;
if(root2 == NULL)
return root1;
if(root1->value > root2->value)
return MergeTwoBST(root2, root1);
if(root1->value < root2->value)
{
right = root1->r |
|
s******t 发帖数: 2374 | 5 Mmmm....let me write one:
list1:
1-> 2-> 3->4
list2:
5->6->3->4
int countlen(Node node){
int counter = 0;
while(node!=null) {node=node->next; counter++;}
return counter;
}
Node goNstep(Node root, int n){
while(n-->0) root=root->next;
return root;
}
Node getCommon(Node root1, Node root2){
int len1 = countlen(root1);
int len2 = countlen(root2);
if(len1 > len2) root1 = goNstep(root1, len1-len2);
else root2 = goNstep(root2, len2-len1);
while(root1!=NULL){
if(root1 == root2) brea |
|
g*********s 发帖数: 1782 | 6 2. 判断两二叉树全等(在可以交换左右子树的条件下),进一步给出需要多少次交换。
时间复杂度,如何优化。
recursion?
is_equal(root1, root1) ::= root1->dat == root2->dat &&
(is_equal(root1->left, root2.left) && is_equal(root1->right, root1-
>right || ... //swap case).
each node can at most trigger 2 swap ops. so worst case 2n? not sure if
a swap on one parent and a swap on its kid would cancel each other.
complexity exponential?
optimization: traverse the tree to calculate the size of each sub-tree.
check the sub-tree size before recursive call.
3.... 阅读全帖 |
|
s******n 发帖数: 226 | 7 void merge(node* root1, node* root2){
int count =0;
node* cur = root1;
for(;cur;cur = cur->right, count++)
while(rightRotate(cur));
cur = root2;
for(;cur;cur = cur->right, count++)
while(rightRotate(cur));
// Merge 2 linked list in place
for(int i=count/2;i;i = i/2){
cur = root;
for(int j=0;j
leftRotate(cur);
cur = cur->right;
}
}
} |
|
g****y 发帖数: 240 | 8 你这样解法不对。你不能保证root2左树中的所有node比root1小。
root2 |
|
|
y***k 发帖数: 9459 | 10 发信人: root002 (root), 信区: Military
标 题: Re: 喜欢本族人不喜欢黑人犯了哪个错????
发信站: BBS 未名空间站 (Sun May 29 22:12:44 2016, 美东)
老子早就说过,菌斑是一个种族主义分子横行的地方,一帮傻逼整天看不上黑幕三,但
人家白人有一点不尊重华人的,就连哭带闹,要上街游行。
人家黑幕三不需要你喜欢,但如果白人也公开歧视黄皮,黄皮也就别鸡巴抱怨了,人家
不喜欢还不许人家说?
当年西班牙篮球队弄了个 slit-eyed gestures "Ching Chong Chinaman!,一帮老中愤
怒的要求人家道歉,照菌斑逻辑,你他妈的本来就是slit-eyed,为啥不让人家说? |
|
|
h****g 发帖数: 11365 | 12
诉。
说的很好。任何歧视都要回过去,但也不能给自己挖坑。精白就是一群逃避现实的傻逼
,下回被共和党再涮一次,又该吹嘘民主党了。 |
|
h******i 发帖数: 21077 | 13 支持芦根。
芦根嘴巴脏、礼貌差,历史和文化都一塌糊涂。但是评论美国现实还是靠谱的。 |
|
r*****2 发帖数: 3513 | 14 不说别的,就是因为美国讲政治正确,华人小孩在学校才能混下去,要是不讲政治正确
,小黄皮们早被白人黑人小孩bully成二逼了。
老中自己不够牛逼彪悍,还反对政治正确,你问问你家孩子同意吗? |
|
r*****2 发帖数: 3513 | 15 尼玛,老子不论是历史和文化,经济政治地理天文,都比你丫强。 |
|
h******i 发帖数: 21077 | 16 比我强不算本事啊,我本来就没有文化。
你要是能骂过海日,才算你勉强有文化,哈哈 |
|
r*****2 发帖数: 3513 | 17 海日是奇人,没有人能赢他,丫从来都是自说自话。 |
|
l****p 发帖数: 27354 | 18 序号 ID 杀伤力 努力程度
1 tgbqaz 10 5
2 stoppingtime 9 10
3 ldlxk 8 3
4 Root2 7 9
5 xiaxianyue 7 8
6 hairi 7 8
7 yugong 7 5
8 juanxi 6 2
9 gshjj 6 2
10 attain79 6 7
11 nickmj 6 7
12 Coralreef 6 5
13 ... 阅读全帖 |
|
l****p 发帖数: 27354 | 19 【 以下文字转载自 Military 讨论区 】
发信人: lulupp (木有昵称), 信区: Military
标 题: 本版一些ID某些指标排行榜
发信站: BBS 未名空间站 (Tue Jun 7 12:56:59 2016, 美东)
序号 ID 杀伤力 努力程度
1 tgbqaz 10 5
2 stoppingtime 9 10
3 ldlxk 8 3
4 Root2 7 9
5 xiaxianyue 7 8
6 hairi 7 8
7 yugong 7 5
8 juanxi 6 2
9 gshjj 6 2... 阅读全帖 |
|
s******t 发帖数: 2374 | 20 这个主要是要比较reference儿不是比较content吧。
while(root1 == root2) |
|
l***m 发帖数: 339 | 21 我会你这么解,肯定不会merge两个array。
root2 |
|
h*****n 发帖数: 188 | 22 wrong.
try a few sample cases.
root2 |
|
l*****r 发帖数: 393 | 23 Wrong, check the BST definition again.
root2 |
|
d**e 发帖数: 6098 | 24 post order遍历tree2,逐个逐个insert到tree1也可行吧。
root2 |
|
w***o 发帖数: 109 | 25 当然没有假定root2左树中的所有node比root1小.
所以我才用
root1 = mergeBST(root1, left);
而不是:
root1.left = mergeBST(root1.left, left); |
|
P*******b 发帖数: 1001 | 26 来自主题: JobHunting版 - G 家面经 bless!
第一题intersection的函数应该长什么样?
TreeNode* intersection(TreeNode* root1, TreeNode* root2)
返回新的树,这样对吗?
的。 |
|
P*******b 发帖数: 1001 | 27 来自主题: JobHunting版 - G 家面经 bless!
第一题intersection的函数应该长什么样?
TreeNode* intersection(TreeNode* root1, TreeNode* root2)
返回新的树,这样对吗?
的。 |
|
a****a 发帖数: 15 | 28 应该是两个size为m的min-heap(这样能确保min再其中一个heap里面)
heap 1 负责 file 1, heap 2 负责 file 2
每次extract min(root1, root2) 写到 f3, 然后insert new value into the heap
直到file读完 heaps 都为空
至于内存限制.... f3 写的差不多了 就存到disk一下 |
|
a********8 发帖数: 1625 | 29 第一步是计算query point到root1的距离,把它作为best_value,然后搜索root1的两边
,此时不能排除右边。
先搜左边,发现query point到root2的距离更小,update,但是并不能小于query point
到root1所划分的分割线,所有root1的右边还得接着搜(否则可以直接扔掉右边)
这样可以达到LogN的时间复杂度 |
|
c******a 发帖数: 16 | 30 请问在WinEdt里面怎么设啊,我用Texify编译通过了后在弹出来的Yap中不停地报错,
什么invalid argument、Some PostScript specials could not be rendered:
MiKTeX Problem Report
Message: Some PostScript specials could not be rendered.
Data: Error: /undefined in H.S
Operand stack:
--nostringval-- PermitFileReading --nostringval-- PermitFileWriting
--nostringval--
Execution stack:
%interp_exit .runexec2 --nostringval-- --nostringval-- --
nostringval-- 2 %stopped_push --nostringval-- --nostringval-- --
nostr... 阅读全帖 |
|