搞生物的这么悲催啊。。。 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Biology - 生物学

搞生物的这么悲催啊。。。

搞生物的这么悲催啊。。。# Biology - 生物学

t*e2017-07-13 07:07

1 楼

how to design a queue, in addition to insert(), delete(), also has a
function min() which returns the minumum element? Can you do all functions
in O(1) time?
careercup上有一道关于stack的类似的题，很容易就做到O(1)了，但是这个queue的比
较难想……
请大虾赐教……

r*k2017-07-13 07:07

2 楼

【以下文字转载自 SanFrancisco 讨论区】
发信人: realshrek (shrek), 信区: SanFrancisco
标题: 搞生物的这么悲催啊。。。
发信站: BBS 未名空间站 (Thu Jul 13 22:13:10 2017, 美东)
老婆国内生物硕士
来这边，终于找到一个工作
在旧金山半岛区，年薪5万。。。
这怎么能活啊
不知道邮局送信能挣多少
这的房价都是1.5m的啊

S*t2017-07-13 07:07

3 楼

Just use two stacks to implement the queue.

c*12017-07-13 07:07

4 楼

湾区捷运一名张姓华裔清洁工2015年的薪金27万1243元

s*n2017-07-13 07:07

5 楼

keep another queue V.
when append a new element to queue, pops elements from V's end until find
element is less or equal than the new one, then append new element to the
end of V.
when remove first element from the queue, if front item of V is equal to the
first element of the queue, then remove first element of V.
the smallest element is the first element of V.

a*r2017-07-13 07:07

6 楼

邮局大概20
不过人见还要晒太阳跑来跑去呢

s*n2017-07-13 07:07

7 楼

class DataStructure {
protected:
deque q;
deque v;
public:
void push_back(int data)
{
while (v.size()>0) {
if (v.back()>data) v.pop_back();
else break;
}
q.push_back(data);
v.push_back(data);
}
int pop_front() {
int ret = q.pop_front();
if (ret==v.front()) v.pop_front();
return ret;
}
int size() {
return q.size();
}
int minValue() {
assert(v.size()>0);
return v.front();
}
}

r*k2017-07-13 07:07

8 楼

20万？
还是时薪20？

【在 a******r 的大作中提到】

: 邮局大概20
: 不过人见还要晒太阳跑来跑去呢

p*22017-07-13 07:07

9 楼

the
不是要求0（1）吗

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

: keep another queue V.
: when append a new element to queue, pops elements from V's end until find
: element is less or equal than the new one, then append new element to the
: end of V.
: when remove first element from the queue, if front item of V is equal to the
: first element of the queue, then remove first element of V.
: the smallest element is the first element of V.

r*k2017-07-13 07:07

10 楼

国内年薪十五万，没买房啊。。。

t*e2017-07-13 07:07

11 楼

这个“pops elements from V's end until find
element is less or equal than the new one”
不是O(n)了么

the

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

a*n2017-07-13 07:07

12 楼

你确定？北京工资现在基本都要50万了
三线也基本20w+
博后的标准是18w

s*n2017-07-13 07:07

13 楼

看怎么理解阿，插入N个元素操作的过中，V最多push N次，pop N次，平分到N个元素每个元素还是O(1)

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

:
: the
: 不是要求0（1）吗

t*e2017-07-13 07:07

14 楼

这样delete()就是O（n）吧

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

: Just use two stacks to implement the queue.

S*t2017-07-13 07:07

15 楼

No, delete() is still amortized O(1)

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

: 这样delete()就是O（n）吧

o*o2017-07-13 07:07

16 楼

从来没听说过big O可以平分的。

每个元素还是O(1)

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

: 看怎么理解阿，插入N个元素操作的过中，V最多push N次，pop N次，平分到N个元素每个元素还是O(1)

s*o2017-07-13 07:07

17 楼

use a double-linked list L
for insert, if it's smaller than end of L, append to L;
for delete, if it's same as front of L, remove front of L;
for min, return end of L.

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

: how to design a queue, in addition to insert(), delete(), also has a
: function min() which returns the minumum element? Can you do all functions
: in O(1) time?
: careercup上有一道关于stack的类似的题，很容易就做到O(1)了，但是这个queue的比
: 较难想……
: 请大虾赐教……

z*82017-07-13 07:07

18 楼

经典教材上面就有这章 amortized analysis
现在听说过了吧

【在 o*o 的大作中提到】

: 从来没听说过big O可以平分的。
:
: 每个元素还是O(1)

g*x2017-07-13 07:07

19 楼

This has a problem:
For example,
Queue: 4 3 2 5 9 8 4
Double List: 4 3 2
After 3 deletion (4 3 2), the double list contains no min value of Queue.

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

: use a double-linked list L
: for insert, if it's smaller than end of L, append to L;
: for delete, if it's same as front of L, remove front of L;
: for min, return end of L.

d*l2017-07-13 07:07

20 楼

不错

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

: class DataStructure {
: protected:
: deque q;
: deque v;
: public:
: void push_back(int data)
: {
: while (v.size()>0) {
: if (v.back()>data) v.pop_back();
: else break;

m*P2017-07-13 07:07

21 楼

别乱说话 ...

【在 o*o 的大作中提到】

: 从来没听说过big O可以平分的。
:
: 每个元素还是O(1)

w*g2017-07-13 07:07

22 楼

我来试一下看对不对。。。
队列+链表
队列就是正常存储的数据， FIFO，只不过队列中的数据要额外多添加一个指针域，指向其在链表对应的位置，
入队：如果新加入的数比链表首要小或者相等（注意相等的细节），添加该数值到队列尾部和链表的首部，在队列中的那个指针指向其在链表中的位置；否则，指针设置为空就好了
出队：如果要出队列的数值与链表头部的一样大（这种情况下对应的指针域不为空），同时删除链表首部的数据（通过指针）和出队列，否则，只出队列
最小：就在链表首部
不知道讲清楚了没有。。。

t*e2017-07-13 07:07

23 楼

clear to me

指向其在链表对应的位置，
队列尾部和链表的首部，在队列中的那个指针指向其在链表中的位置；否则，指针设置
为空就好了
），同时删除链表首部的数据（通过指针）和出队列，否则，只出队列

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

: 我来试一下看对不对。。。
: 队列+链表
: 队列就是正常存储的数据， FIFO，只不过队列中的数据要额外多添加一个指针域，指向其在链表对应的位置，
: 入队：如果新加入的数比链表首要小或者相等（注意相等的细节），添加该数值到队列尾部和链表的首部，在队列中的那个指针指向其在链表中的位置；否则，指针设置为空就好了
: 出队：如果要出队列的数值与链表头部的一样大（这种情况下对应的指针域不为空），同时删除链表首部的数据（通过指针）和出队列，否则，只出队列
: 最小：就在链表首部
: 不知道讲清楚了没有。。。

w*o2017-07-13 07:07

24 楼

你的这个有点儿问题，
比如队列
头 3 8 5 尾
链表: 3
如果3从队列里出队后，链表就成空了。这就不对了。链表应该是5

指向其在链表对应的位置，
队列尾部和链表的首部，在队列中的那个指针指向其在链表中的位置；否则，指针设置
为空就好了
），同时删除链表首部的数据（通过指针）和出队列，否则，只出队列

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

w*g2017-07-13 07:07

25 楼

恩还是个大问题。。。进入胡同了。。。谢谢提出问题！
开始倾向于上面均摊分析的方法了。。。

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

: 你的这个有点儿问题，
: 比如队列
: 头 3 8 5 尾
: 链表: 3
: 如果3从队列里出队后，链表就成空了。这就不对了。链表应该是5
:
: 指向其在链表对应的位置，
: 队列尾部和链表的首部，在队列中的那个指针指向其在链表中的位置；否则，指针设置
: 为空就好了
: ），同时删除链表首部的数据（通过指针）和出队列，否则，只出队列

a*s2017-07-13 07:07

26 楼

保留原始FIFO队列，再要一个栈，专门存最小值。
第一个元素直接进栈，后面来一个元素，跟栈顶比大小，大的不管，小于等于的进
栈顶。
min的时候直接取栈顶。队列delete（）的时候要检查是否是最小元素，若是则栈
也pop一个，保持同步。
没说不让用栈啊。

s*n2017-07-13 07:07

27 楼

Wrong:
add
5,4,3,6,7
your stack is 5, 4, 3
then remove
5,4,3
your stack is
5, 4
min() return 4, which is wrong, should return 6

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

: 保留原始FIFO队列，再要一个栈，专门存最小值。
: 第一个元素直接进栈，后面来一个元素，跟栈顶比大小，大的不管，小于等于的进
: 栈顶。
: min的时候直接取栈顶。队列delete（）的时候要检查是否是最小元素，若是则栈
: 也pop一个，保持同步。
: 没说不让用栈啊。

j*j2017-07-13 07:07

28 楼

这不是一般的队列，这是双端队列，不合题意吧？

the

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

t*r2017-07-13 07:07

29 楼

可不可以这么来做
用一个队列来保存数据(设为q)，一个环型数组保存最小值（设为v），环形数组有两个
指针，start和end
1. v刚开始为空，start=end=0, 设 v[start] = MAX
2. 如果此时入队列的元素为value，如果value < v[end] 那么v[end]=value
3. 如果value >= v[end], 那么 v[++end] = value (由于是环形数组，需要对start
和end下标进行处理
4.遇到队列pop_front()的时候，只有当 q.top() == v[start] 才将 start++
用例子来说明，比如队列是 5,4,3,6,7
那么此时 v中是 3,6,7
pop出5,4的时候，队列中最小值是3， v[start]也是3
pop 3的时候，队列中最小值是6， v[start]也是6
不知道这种方法如何？
可以用deque来代替这个环形数组的实现

d*a2017-07-13 07:07

30 楼

正解，看编程之美里有这个的

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

: Just use two stacks to implement the queue.

t*h2017-07-13 07:07

31 楼

恩，很好的想法，每个node多一个min变量，压第一个盏的时候，检查top的min，决定
要压入的node的min。第一个盏往第二个盏灌的时候，同样的做法。
多谢。

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

: Just use two stacks to implement the queue.

z*i2017-07-13 07:07

32 楼

有细节吗？网上搜了一下，有些怀疑是否可能。

【在 d*******a 的大作中提到】

: 正解，看编程之美里有这个的

l*72017-07-13 07:07

33 楼

基于比较的sort算法，average最少需要O(nlogn)。
反证法：
假设存在这样一个queue, insert(), delete(), min() cost O(1).
then for a given unsorted numbers, we can first insert all numbers into the
queue. cost is O(n).
repeated use min() and delete(), we can get a sorted sequence of the
original numbers. the cost is O(n).
so to sort, the total cost is O(n). Contradiction. (qed)

p*a2017-07-13 07:07

34 楼

the
Note that queue is different from heap. delete() only removes the head, not
the minimum. So you cannot use this queue to sort.

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

: 基于比较的sort算法，average最少需要O(nlogn)。
: 反证法：
: 假设存在这样一个queue, insert(), delete(), min() cost O(1).
: then for a given unsorted numbers, we can first insert all numbers into the
: queue. cost is O(n).
: repeated use min() and delete(), we can get a sorted sequence of the
: original numbers. the cost is O(n).
: so to sort, the total cost is O(n). Contradiction. (qed)

z*t2017-07-13 07:07

35 楼

我有一篇博客讨论关于queue中最大值的问题：
http://codercareer.blogspot.com/2012/02/no-33-maximums-in-slidi
欢迎批评指正。

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

h*e2017-07-13 07:07

36 楼

这位就是何海涛大牛啊。

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

: 我有一篇博客讨论关于queue中最大值的问题：
: http://codercareer.blogspot.com/2012/02/no-33-maximums-in-slidi
: 欢迎批评指正。

z*i2017-07-13 07:07

37 楼

queue and stack are different for min: (1) min of queue is dynamic,
depending on futher insertion of numbers, while (2) min of stack is "static"
--is determined by current numbers in stack.
For example：both queue and stack have numbers 10 20 30 40. Then the min of
both queue and stack are 10. However，after 5 is inserted, the min of the
queue is 5(min of 10 20 30 40 5), while the min of the stack is still 10(min
of 10, 20, 30, 40)
Now let look at one example for min using auxiliary stack to implement queue
with min. Assume 1,2,3,4 and 5 are inserted. Then the data queue has 1 2 3
4 5, and the auxiliary queue has 1 1 1 1 1. Now min returns 1 currently.
However, after deleting 1, the data queue has 2 3 4 5, and the auxiliary
queue has 1 1 1 1. Now the min returns incorrect vlaue 1, which should be 2.
It seems that the second approach for stack with min(by computing "min"
carefully) still not working because of the different of the min between
queue and stack.

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

: 我有一篇博客讨论关于queue中最大值的问题：
: http://codercareer.blogspot.com/2012/02/no-33-maximums-in-slidi
: 欢迎批评指正。

z*i2017-07-13 07:07

38 楼

The following algorithm for queue with max is correct to me:
http://www.sureinterview.com/wiki/Shwqst/903001
idea:
1 用数据队列保存所有数据X[0]，X[1]，...
2 用辅助队列保存数据中的X[i1],X[i2],etc. such that
2.1 X[i1]>=X[i2]>=...。
2.2 X[i1]是从X[i1]开始最大的数。
3 enque的时候,删除辅助队列中比要插入的数据小（4 deque的时候，删除数据队列的第一个数据。同时，如果辅助队列的第一个数据等于数据队列的第一个数据，删除辅助队列的第一个数据。
5 max就是辅助队列的第一个数据
例子一。
数据队列：6 5 4。
辅助队列：6 5 4。
1) max: 辅助队列的第一个数据6.
2) deque：
数据队列：5 4。
辅助队列：5 4
max: 5
3) deque:
数据队列：4。
辅助队列：4
max: 4
例子二。
数据队列：4 5 6。
辅助队列：6。
1) max: 辅助队列的第一个数据6.
2) deque：
数据队列：5 6。
辅助队列：6
max: 6
3) deque:
数据队列：6。
辅助队列：6
max: 6
例子三。
数据队列：4 6 5。
辅助队列：6 5。
1) max: 辅助队列的第一个数据6.
2) deque：
数据队列：6 5。
辅助队列：6 5
max: 6
3) deque:
数据队列：5。
辅助队列：5
max: 5
复杂度：easy to see that O(1) for both deque and max.
enque: complexity is from the while loop(comparisons).
For some comparisons, each comparison corresponds to a deletion of an element from the auxiliary queue. Since each element can be deleted at most once from the auxiliary queue, such comparisons are in total O(n), thus amortized cost of O(1) per element insertion.
However, there are comparisons which do not correspond to deletion of elments from the auxiliary queue. For example, auxiliary queue has elements 6 5. when inserting 4, we compare 4 with 5. Since 5 not less than or equal to 4, 5 is not deleted from the auxiliary queue, though we have one comparison between 4 and 5. How many such comparisons withou deletion? An observation is that for each such comparison without deletion, we must insert an element into the auxiliary queue. So there are at most O(n) such comparisons without deletion, thus amortized cost of O(1) per element.

y*u2017-07-13 07:07

39 楼

把当前的min带着就行了
queue size double

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

z*i2017-07-13 07:07

40 楼

swanswan described the same algorithm.

于数据队列的第一个数据，删除辅助队列的第一个数据。

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

: The following algorithm for queue with max is correct to me:
: http://www.sureinterview.com/wiki/Shwqst/903001
: idea:
: 1 用数据队列保存所有数据X[0]，X[1]，...
: 2 用辅助队列保存数据中的X[i1],X[i2],etc. such that
: 2.1 X[i1]>=X[i2]>=...。
: 2.2 X[i1]是从X[i1]开始最大的数。
: 3 enque的时候,删除辅助队列中比要插入的数据小（: 4 deque的时候，删除数据队列的第一个数据。同时，如果辅助队列的第一个数据等于数据队列的第一个数据，删除辅助队列的第一个数据。
: 5 max就是辅助队列的第一个数据