这是谁啊? - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

这是谁啊?

这是谁啊?# Joke - 肚皮舞运动

d*n2010-03-23 07:03

1 楼

Given a document and a query of K words, how do u find the smallest window
that covers all the words at least once in that document? (given you know
the inverted lists of all K words, that is, for each word, you have a list
of all its occurrrences). This one is really hard. Could someone propose an
algorithm in O(n)?

n*d2010-03-23 07:03

2 楼

吴秀波现在算是一线男明星，因为他可以有稳定的票房保证，所以投资方如果投2、3个
亿都没有关系，因为可以看到回头钱。男一号一般可以拿到30%以上的投资款，也就是
可以拿最少6千万，这还只是算他一年拍一两部电影，中国电影一般半年就拍完了，所
以一年他电影方面的收入就有1个亿了。其他比如他还参加选秀节目之类七七八八的，
这样算下来他单纯的工作收益就有1、2个亿了。对比下来，我们真的是穷成狗了！但是
每个行业都是呈金字塔形的，这种人也就那么10多号人。但是对比下来，女性的收入就
要低一些了，好莱坞也是这样的，女一号的薪酬就要比男一号的薪酬少很多。
吴秀波的收入不是只有今年有，他是年年有，只要他想，他会挣得更多。上去容易下去
难，估计这件事情会给他造成很大的影响。
从生物学方面来说，一个男的找多个女的可能性是非常大的。一个雄性有天然的本能去
跟多个的雌性交配，比如精子的数量就要比卵子要多得多，这是动物的本性。第二个，
从社会发展角度来说，资本主义和封建社会在性分配资源上也是差不多的，没钱就找不
到老婆，如果你是大财主，三妻四妾是没什么问题的。

p*a2010-03-23 07:03

3 楼

枪炮武术最早出现于贝尔早期演的equilibrium一片,视觉效果炫目
主要是把很多打击动作用开枪代替,并嵌入到格斗动作中去.
john这片把它更加现实化
护宅和独闯夜总会两幕都是精彩的枪炮武术的呈现
比equalizer好看.
equalizer只有酒吧的5分钟值钱.

m*d2010-03-23 07:03

4 楼

d*n2010-03-23 07:03

5 楼

I remember a similar problem was discussed not long ago. Any takers here?

an

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

: Given a document and a query of K words, how do u find the smallest window
: that covers all the words at least once in that document? (given you know
: the inverted lists of all K words, that is, for each word, you have a list
: of all its occurrrences). This one is really hard. Could someone propose an
: algorithm in O(n)?

t*02010-03-23 07:03

6 楼

妈的，只有生物本能了吗？

m*g2010-03-23 07:03

7 楼

前面贴过好象
for each work, maintain a queue
scan
if(doc[i]==word[j])
queue[j].push[doc[i]];
if( queue[0]...queue[i] all have 1 elem && queue[j] has 2 elem)
update smallestWindowSize;
dequeue queue[0]...queue[i] until every queue has only 1 elem.
endif
end scan.

B*t2010-03-23 07:03

8 楼

可以用堆来做，复杂度O(nlogk)
这题overlapping 的subproblems不好定义，DP好像不是很适合

smallest window
you know
have a list
propose an

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

d*n2010-03-23 07:03

9 楼

can you give some link or details?

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

: 可以用堆来做，复杂度O(nlogk)
: 这题overlapping 的subproblems不好定义，DP好像不是很适合
:
: smallest window
: you know
: have a list
: propose an

B*t2010-03-23 07:03

10 楼

维护一个最小堆和最大堆存储work的position，最小堆k个元素，最大堆的至少k个元
素，
1. 初始化的时候用k个word的最小position构造以上两个堆。
2. 检查是否已经处理了所有word，没有的话如果最大top-最小堆的topmin，否则输出min
3. 每次从min heap pop一个word的pos，并设置一个flag，标记已用，并把这个
work的下一个pos分别压入两个堆，
4. 检查max heap的top元素是否为已经标记，如果已经标记，就把它pop出来，go
back 4，否则go 2

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

: can you give some link or details?

d*n2010-03-23 07:03

11 楼

Good idea. So the time complexity is O(N*logK)? I was studying DP and
tempted to solve problem by it. For this one, I'm thinking of another way to
solve it. Complexity is O(N*K):
Assuming we sort all the positions into a new array A, where each element A[
i] contains two members (position, word), 0<= position < N, 0<=word < K; the
elements are sorted by the position in ascending order.
Elem {
int position,
int word
}

Elem A[] = sorted Elems by position
Elem B[K];

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

: 维护一个最小堆和最大堆存储work的position，最小堆k个元素，最大堆的至少k个元
: 素，
: 1. 初始化的时候用k个word的最小position构造以上两个堆。
: 2. 检查是否已经处理了所有word，没有的话如果最大top-最小堆的top: min，否则输出min
: 3. 每次从min heap pop一个word的pos，并设置一个flag，标记已用，并把这个
: work的下一个pos分别压入两个堆，
: 4. 检查max heap的top元素是否为已经标记，如果已经标记，就把它pop出来，go
: back 4，否则go 2

l*a2010-03-23 07:03

12 楼

O(n)
please read
http://www.mitbbs.com/article/JobHunting/31561927_3.html

way to
element A[
the

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

: Good idea. So the time complexity is O(N*logK)? I was studying DP and
: tempted to solve problem by it. For this one, I'm thinking of another way to
: solve it. Complexity is O(N*K):
: Assuming we sort all the positions into a new array A, where each element A[
: i] contains two members (position, word), 0<= position < N, 0<=word < K; the
: elements are sorted by the position in ascending order.
: Elem {
: int position,
: int word
: }

x*32010-03-23 07:03

13 楼

这题的解法是不是用k个指针，每个指针指向一个occurrence list (sorted), 然后每
次移动位置最小的指针，在这过程中update min window size
难道我理解错题意？

s*s2010-03-23 07:03

14 楼

Why can it give the minimum?

【在 x******3 的大作中提到】

: 这题的解法是不是用k个指针，每个指针指向一个occurrence list (sorted), 然后每
: 次移动位置最小的指针，在这过程中update min window size
: 难道我理解错题意？

x*32010-03-23 07:03

15 楼

证明不出来，只能说说我的理解
给定一个window，只能通过移动window的左边界来得到更小的window，所以通过不断调
整window的左边界（即最小的
position），总是能遇到最小的window

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

: Why can it give the minimum?

s*s2010-03-23 07:03

16 楼

直观上你的方法可行。试着证明一下：
最小的window符合以下特性的window中最小的：
A1：window的边界元素（左一个右一个）对应的keyword在该window中除了边界元素不能有其他
occurrence
证明：如果A1不符合，说明window还能够再挤扁一点。
所有符合A1的window：
a）或者能被你的算法直接hit到；
b）或者找到另一个符合A1的window w0具有相同的边界元素，而w0能被你的算法直接hit到。
证明：稍微有点麻烦，但是也是可以的。

【在 x******3 的大作中提到】

: 证明不出来，只能说说我的理解
: 给定一个window，只能通过移动window的左边界来得到更小的window，所以通过不断调
: 整window的左边界（即最小的
: position），总是能遇到最小的window