logo
Redian新闻
>未名空间
>pets - 心有所宠
>
刚带回家一只10周大的小猫.
avatar
刚带回家一只10周大的小猫.# pets - 心有所宠
S*n
1 楼
A binary search tree is given. Find the ceiling value present in the BST of
a given key. eg-
8
3 12
2 6 10 15
4
key - 13 => 15
key - 4 =>6
key - 8 =>10
自己写了一个
TreeNode* find(TreeNode* root, int target)
{
if(!root) return NULL;
TreeNode * result = NULL;
TreeNode* curr = root;
while( curr )
{
if(target >= curr->val)
curr = curr->right;
else
{
result = curr;
curr = curr->left;
}
}
return result;
}
谁帮我看看对不对，感觉离开leetcode的onlinejudge自己不会测试了
avatar
p*g
2 楼
avatar
h*3
3 楼
想请教一下.
我们按照宠物店的人说的,到家后把它自己关在一个屋子里面让它适应环境.白天还好,
到了晚上,我们关灯睡觉了.听到它在扑门.还在苗苗叫.是它害怕了吗?我们该怎么办?把
灯给它留着?还是放它来我们屋睡觉?还是关灯让它自己在那个屋子里睡觉?
这只小猫好像不太怕人.下午来了以后,到了晚上就从床底下爬出来了,到处闻,看到我们
也不躲,上来闻我们,而且也开始和我儿子玩了.我去抱它,它也没挠我.也让抱,就是好像
不太喜欢被关在一个屋子里,老想跑出来,我老公不小心,让它跑出来了一次,它也是各个
屋子到处闻.也不着急藏.被我老公抓回来也没太着急的样子.
想请教这里有经验的朋友,新的小猫到家都是怎样的过程.大概要多少天,什么表现才是
小猫适应了呢?
谢谢
avatar
p*2
4 楼

of
感觉curr变量可以不需要

【在 S******n 的大作中提到】
: A binary search tree is given. Find the ceiling value present in the BST of
: a given key. eg-
: 8
: 3 12
: 2 6 10 15
: 4
: key - 13 => 15
: key - 4 =>6
: key - 8 =>10
: 自己写了一个
avatar
i*a
5 楼
this girl is very cute. but I've never found out who she is

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

avatar
m*u
6 楼
他要是知道厕所在哪 就让他四处逛逛呗
我觉得先放一个屋子的主要目的就是熟悉使用厕所
avatar
S*n
7 楼
是不需要，这个题目是不是也可以转化
有duplicate的BST找lowerbound和upperbound？

【在 p*****2 的大作中提到】
:
: of
: 感觉curr变量可以不需要
avatar
b*2
8 楼
像越南人

【在 i****a 的大作中提到】
: this girl is very cute. but I've never found out who she is
avatar
N*t
9 楼
关屋子主要是怕他害怕给他一个可以躲的地方，如果不害怕不躲藏就不用隔离了
这么小的猫很需要人陪的，不能让他自己单独太久
还有宠物店卖猫的？
avatar
l*a
10 楼
为什么不是找previous/next node with inorder traverse

【在 S******n 的大作中提到】
: 是不需要，这个题目是不是也可以转化
: 有duplicate的BST找lowerbound和upperbound？
avatar
w*o
11 楼
Re

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

【在 m*******u 的大作中提到】
: 他要是知道厕所在哪 就让他四处逛逛呗
: 我觉得先放一个屋子的主要目的就是熟悉使用厕所
avatar
c*a
12 楼
我觉得正确。
若遇到小／相等的node，那肯定不是解，往右走。遇到大了的点，就拼命往它左边走。
走到走不动。
avatar
h*3
13 楼
我们这边的宠物店全有小猫.说是让人领养.

【在 N******t 的大作中提到】
: 关屋子主要是怕他害怕给他一个可以躲的地方，如果不害怕不躲藏就不用隔离了
: 这么小的猫很需要人陪的，不能让他自己单独太久
: 还有宠物店卖猫的？
avatar
c*a
14 楼
你这就O(n)了。楼主那个O(lgN)

【在 l*****a 的大作中提到】
: 为什么不是找previous/next node with inorder traverse
avatar
h*3
15 楼
我看他好像谁都不怕的样子.倒是我家老二,好像还很怕他.
老二还不到两岁.也不知道她什么时候能适应家里多了只小猫

【在 N******t 的大作中提到】
: 关屋子主要是怕他害怕给他一个可以躲的地方，如果不害怕不躲藏就不用隔离了
: 这么小的猫很需要人陪的，不能让他自己单独太久
: 还有宠物店卖猫的？
avatar
r*h
16 楼
感觉target=4的时候会走到4呀

of

【在 S******n 的大作中提到】
: A binary search tree is given. Find the ceiling value present in the BST of
: a given key. eg-
: 8
: 3 12
: 2 6 10 15
: 4
: key - 13 => 15
: key - 4 =>6
: key - 8 =>10
: 自己写了一个
avatar
d*e
17 楼
知道用沙盆就没事了，
avatar
l*a
18 楼
真的吗?

【在 c******a 的大作中提到】
: 你这就O(n)了。楼主那个O(lgN)
avatar
N*t
19 楼
凹这样阿，估计是rescue组织在那里摆摊吧，我家二毛也是petco领的～～

【在 h******3 的大作中提到】
: 我们这边的宠物店全有小猫.说是让人领养.
avatar
l*a
20 楼
result里面记的不是6?

【在 r**h 的大作中提到】
: 感觉target=4的时候会走到4呀
:
: of
avatar
N*t
21 楼
那就不用关拉，只要知道沙盆在哪，如果房子很大的话可能需要多放些沙盆，有时候沙
盆离活动区域太远的话小猫就找不回去了
小孩子适应很快拉，不过小猫和小孩都不知轻重，玩的时候大人还是得监督着好

【在 h******3 的大作中提到】
: 我看他好像谁都不怕的样子.倒是我家老二,好像还很怕他.
: 老二还不到两岁.也不知道她什么时候能适应家里多了只小猫
avatar
S*n
22 楼
往左走才update，应该是6啊

【在 l*****a 的大作中提到】
: result里面记的不是6?
avatar
l*d
23 楼
这个还比较容易改，只要把等于的判断分开：等于的时候找右子树最左边的节点。
不过他这个算法只能从上往下找。如果输入6，应该返回root 8，好像就没办法了。
我觉得最直观的做法是in order traversal 变成一个sorted array，然后binary
search

【在 S******n 的大作中提到】
: 往左走才update，应该是6啊
avatar
S*n
24 楼
如果是6的话会往右走，result并没有update还是会返回8

【在 l**d 的大作中提到】
: 这个还比较容易改，只要把等于的判断分开：等于的时候找右子树最左边的节点。
: 不过他这个算法只能从上往下找。如果输入6，应该返回root 8，好像就没办法了。
: 我觉得最直观的做法是in order traversal 变成一个sorted array，然后binary
: search
avatar
H*r
25 楼
key - 1
key - 16
应该返回啥？？？

of

【在 S******n 的大作中提到】
: A binary search tree is given. Find the ceiling value present in the BST of
: a given key. eg-
: 8
: 3 12
: 2 6 10 15
: 4
: key - 13 => 15
: key - 4 =>6
: key - 8 =>10
: 自己写了一个
avatar
l*d
26 楼
实现了一下，的确是对的。往左走存下result设计不错。

【在 S******n 的大作中提到】
: 如果是6的话会往右走，result并没有update还是会返回8
avatar
l*d
27 楼
1 返回 2阿
16我觉得可以返回Integer.MAXINT或者直接null

【在 H****r 的大作中提到】
: key - 1
: key - 16
: 应该返回啥？？？
:
: of
avatar
H*r
28 楼
这些edge case 需要确定吧，感觉1 返回2应该是不错， 16 可能直接throw error?

【在 l**d 的大作中提到】
: 1 返回 2阿
: 16我觉得可以返回Integer.MAXINT或者直接null
avatar
S*n
29 楼
难道不是返回NULL吗？因为不存在

【在 H****r 的大作中提到】
: 这些edge case 需要确定吧，感觉1 返回2应该是不错， 16 可能直接throw error?
avatar
H*r
30 楼
不存在就返回NULL? 那小于最小的那个值也是吧...

【在 S******n 的大作中提到】
: 难道不是返回NULL吗？因为不存在
avatar
g*x
31 楼
可以有O（lgN)的算法吗？
当BST为
1
2
3
4
...
如何O（lgN)呢？
在平均的情况下，in-order递归的方法也可以是O（lgN)，在worst情况下， 是O（N）。

【在 c******a 的大作中提到】
: 你这就O(n)了。楼主那个O(lgN)
avatar
c*a
32 楼
我不明白了，in-order怎么都要从最小node开始，一个个按顺序走到最后的。相当于一
个array去遍历，怎么lgN啊？
严密一点一个balanced BST，楼主解法我还是觉得是lgN。
avatar
S*n
33 楼
不平衡的bst怎么都是worst case O(n)
avatar
t*2
34 楼
也写了一个，欢迎大牛们挑错~~~
先assume全是正数，找不到就return -1了
－－－－－－－－－－－－－－－－－－－－－－－－－－－
public int ceiling (Node root, int key) {
if (root == null) { // if reached the bottom and no value is greater
than target
return -1; // ceiling is not found
}
if (root.val == key) { // if key is found, return key
return root.val;
}
if(root.val < key) { // if root is smaller than key
return ceiling(root.right, key); // ceiling can only be in
right sub tree
}
int ceil = ceiling(root.left, key); // else search in left sub tree
return ceil >= key? ceil : root.val; // if there is no such value in
left, root is the ceiling
}
avatar
g*x
35 楼
when root->val < target, ceiling is definitely not in subtree of root.
when root->val > target, ceiling is definitely not in right subtree of root.
so no 遍历.

【在 c******a 的大作中提到】
: 我不明白了，in-order怎么都要从最小node开始，一个个按顺序走到最后的。相当于一
: 个array去遍历，怎么lgN啊？
: 严密一点一个balanced BST，楼主解法我还是觉得是lgN。
avatar
g*x
36 楼
看不懂啊。自己写了个：
//
// return the pointer when a ceiling is found;
// otherwise, NULL;
//
TreeNode* find_ceiling(TreeNode* root, int target)
{
if (root==NULL) return NULL;
if (root->val > =target) {
TreeNode* temp = find_ceiling( root->left, target );
return (temp==NULL)? root: temp;
}
return find_ceiling( root->right, target );
}

greater

【在 t*******2 的大作中提到】
: 也写了一个，欢迎大牛们挑错~~~
: 先assume全是正数，找不到就return -1了
: －－－－－－－－－－－－－－－－－－－－－－－－－－－
: public int ceiling (Node root, int key) {
: if (root == null) { // if reached the bottom and no value is greater
: than target
: return -1; // ceiling is not found
: }
: if (root.val == key) { // if key is found, return key
: return root.val;
avatar
c*a
37 楼
哦！明白了，相当于binary search。那的确是lgN

root.

【在 g**x 的大作中提到】
: when root->val < target, ceiling is definitely not in subtree of root.
: when root->val > target, ceiling is definitely not in right subtree of root.
: so no 遍历.
avatar
c*a
38 楼
忽然觉得自己好迟钝，居然去怀疑lolhaha T_T
avatar
x*0
39 楼
mark
相关阅读
这个跳伞的猫怎么回事？带猫从上海飞三藩，2012，美联行版Re: miele吸尘器哪一款比较好？ (转载)小黑和愤怒的小鸟狗为什么对我叫？NND，每次带Jacob去vet看病就后悔！第五季开始了猫昨晚半夜既没走从我身上跨过的老路COLE（扣儿）接回家了。是不是折耳猫性情都比较温和亲人啊今天晚上照的无意中拍的一张Ben大家都用什么猫沙？狗狗为什么瘸了？大家帮我看看: Malti-poo求助：狗狗一到夏天身上就起红色小包，请推荐外用药下周一去见breeder，紧张的好似见公婆！宠物粮里的by product是不是就是4d?奔靓妞～～请教如何把小妞从国内运过来请问如何防止猫猫受伤？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。