地下室发现死老鼠，要找pest control吗？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Living

地下室发现死老鼠，要找pest control吗？

地下室发现死老鼠，要找pest control吗？# Living

y*62012-10-08 07:10

1 楼

Provide a data structure that can perform :
1. insert
2. delete
3. find min
4,. find max
5. delete min
6. delete max
all in O(1) time.
前面四个操作还好说，用一个hashtable和min stack, max stack就可以实现O(1)操作
，关键是operations 5&6，如果remove掉最小或者最大的元素，如何能找到second
smallest和second largest的元素？大牛们给一下提示？ ^__^

t*c2012-10-08 07:10

2 楼

今天工人来关浇水系统，结果在地下室那个小房间里发现一只死老鼠，已经发霉了。旁
边可能还有蛆的蛹什么的。把我恶心的，现在还全身发麻。
请问这种情况请pest control来，算不算小题大作？是请专门做rodent pest control
的么？

p*22012-10-08 07:10

3 楼

前边4个你说的方法可以O(1)吗？

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

: Provide a data structure that can perform :
: 1. insert
: 2. delete
: 3. find min
: 4,. find max
: 5. delete min
: 6. delete max
: all in O(1) time.
: 前面四个操作还好说，用一个hashtable和min stack, max stack就可以实现O(1)操作
: ，关键是operations 5&6，如果remove掉最小或者最大的元素，如何能找到second

t*c2012-10-08 07:10

4 楼

更新一下：叫了pest control，结果在那个小房间发现6只死老鼠，被告知是因为那个
房间是各种管道进来的地方。他们在地下室的天花板里发现有老鼠屎，阁楼也有老鼠活
动的痕迹。
现在pest control建议把siding和地基连接的地方拿小铁片封起来（总长130英尺左右
）,然后把各种管道的入口都封起来。所有这些包括disinfect他们要将近2000刀。请问
这个价格合理么？有什么需要注意的地方吗？
谢谢！

y*62012-10-08 07:10

5 楼

可以吧。拿findmin来说，有一个min stack,栈顶存的是当前所有元素的最小值。每次
insertion的时候，新的元素跟栈顶的元素比较,如果小于栈顶元素，push进栈，否则只
是插入到hash表中就可以了。delete元素的时候，被delete的元素跟栈顶的元素比较，
如果比栈顶的大，那么只将元素从hash表中delete即可，否则还要minstack.pop().

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

:
: 前边4个你说的方法可以O(1)吗？

A*D2012-10-08 07:10

6 楼

siding离地面要有1英尺高，就是为了防止这类问题。你这个属于买房的时候没有做好
功课。

p*22012-10-08 07:10

7 楼

insert和delete的复杂度多少？

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

:
: 可以吧。拿findmin来说，有一个min stack,栈顶存的是当前所有元素的最小值。每次
: insertion的时候，新的元素跟栈顶的元素比较,如果小于栈顶元素，push进栈，否则只
: 是插入到hash表中就可以了。delete元素的时候，被delete的元素跟栈顶的元素比较，
: 如果比栈顶的大，那么只将元素从hash表中delete即可，否则还要minstack.pop().

C*K2012-10-08 07:10

8 楼

什麼原因? 1英尺高老鼠就爬不了了?

【在 A******D 的大作中提到】

: siding离地面要有1英尺高，就是为了防止这类问题。你这个属于买房的时候没有做好
: 功课。

y*62012-10-08 07:10

9 楼

insert和delete用hash的话，应该是O(1)吧。每次insert或者delete的时候维持min
stack和max stack的复杂度也是O(1)

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

:
: insert和delete的复杂度多少？

t*c2012-10-08 07:10

10 楼

第一次住house,没经验啊。
在网上搜了一下，很多地方提到"use expanding foam to seal crack or holes"。请
问有人用过么？这个和金属片比，貌似是更经济和方便的选择。但是有什么不好的地方
吗？每年要reseal？

A*i2012-10-08 07:10

11 楼

前四个要是O(1)了后俩就不能O(1)
如果要后俩O(1)必须在insert 和 delete的时候排序
想不出更好的法子了，呼唤高人

t*c2012-10-08 07:10

12 楼

哎，发现不可以把siding的下面密封起来，因为moisture需要从那里出来。
看来要从了pest control了。
版上没有大侠有类似的经验吗？想知道价格是不是合理。

p*22012-10-08 07:10

13 楼

牛。

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

:
: insert和delete用hash的话，应该是O(1)吧。每次insert或者delete的时候维持min
: stack和max stack的复杂度也是O(1)

y*62012-10-08 07:10

14 楼

deletemin 和deletemax要在O(1)时间内进行肿木搞？

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

:
: 牛。

y*62012-10-08 07:10

15 楼

同问

【在 A*****i 的大作中提到】

: 前四个要是O(1)了后俩就不能O(1)
: 如果要后俩O(1)必须在insert 和 delete的时候排序
: 想不出更好的法子了，呼唤高人

s*n2012-10-08 07:10

16 楼

如果这个ds存在，是不是sort可以在O(n)解决了？
insert, ... insert
findmin, deletemin,
findmin, deletemin
...

y*62012-10-08 07:10

17 楼

是哦~~~ 帅气！

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

: 如果这个ds存在，是不是sort可以在O(n)解决了？
: insert, ... insert
: findmin, deletemin,
: findmin, deletemin
: ...

c*t2012-10-08 07:10

18 楼

delete是只能delete most recent insert吗？

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

:
: 是哦~~~ 帅气！

y*62012-10-08 07:10

19 楼

应该是任意一个元素吧所以肯定会有hash吧

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

: delete是只能delete most recent insert吗？

d*x2012-10-08 07:10

20 楼

insert 6 3 1 2
delete 1

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

:
: 应该是任意一个元素吧所以肯定会有hash吧

l*i2012-10-08 07:10

21 楼

你这个还是有点问题吧。如果minstack被pop为空了，就出错了吧。

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

:
: 应该是任意一个元素吧所以肯定会有hash吧

y*62012-10-08 07:10

22 楼

如果minstack为空的话，那么存储所有元素的hash表也是空的

【在 l****i 的大作中提到】

: 你这个还是有点问题吧。如果minstack被pop为空了，就出错了吧。

l*i2012-10-08 07:10

23 楼

incoming: 1,3,2
Hash: 1,3,2
Minstack: 1
Maxstack: 1,3
delete 1或者delete 3
这样是不是就有问题了？难道我理解错了？

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

:
: 如果minstack为空的话，那么存储所有元素的hash表也是空的

b*m2012-10-08 07:10

24 楼

new int[1]

y*62012-10-08 07:10

25 楼

这个方法跟150题上的那个min stack是类似的，只适用于findmix或者findmax。
你说的这个情况是deletemin或者deletemax。我不知道怎么做，不过看10楼网友的分析
，我觉得这道题在O(1)时间复杂度下完成所有的操作是impossible的

【在 l****i 的大作中提到】

: incoming: 1,3,2
: Hash: 1,3,2
: Minstack: 1
: Maxstack: 1,3
: delete 1或者delete 3
: 这样是不是就有问题了？难道我理解错了？

h*i2012-10-08 07:10

26 楼

不对吧，如果我insert的是一个比当前最小值大，但是比其他都小，你不会把它push到
stack里，如果这时我delete min，后面再找min都是错误的。

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

:
: 这个方法跟150题上的那个min stack是类似的，只适用于findmix或者findmax。
: 你说的这个情况是deletemin或者deletemax。我不知道怎么做，不过看10楼网友的分析
: ，我觉得这道题在O(1)时间复杂度下完成所有的操作是impossible的

c*t2012-10-08 07:10

27 楼

如果是任意一个，你的方法肯定不work啊，因为不是所有元素都入栈的。
试试连续运行下面的。
add 2 3
delete 2
getmin?

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

y*62012-10-08 07:10

28 楼

好像是的......
该用什么数据结构呢？

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

: 如果是任意一个，你的方法肯定不work啊，因为不是所有元素都入栈的。
: 试试连续运行下面的。
: add 2 3
: delete 2
: getmin?

e*s2012-10-08 07:10

29 楼

我不懂了
按楼主说的一个HashMap,一个MinStack,一个MaxStack
deleteMin的时候，不就是map.remove(MinStack.pop())吗？
下一个最小的不就在MinStack.peek（）吗？
要判断的是如果MinStack和MaxStack都只剩一个元素了（第一个插入的元素会push到两
个Stack中），要两个Stack都pop。