|
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... 阅读全帖 |
|
