气死我了 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Biology - 生物学

气死我了

气死我了# Biology - 生物学

c*u2011-11-08 08:11

1 楼

1. Algorithm (I think this question has appeared in this board multiple time
s before):
given n arrays of integers, each array represent the indices of a word in a
text, e.g.
hello: 5 14 19 35 52
world: 11 17 29 40
goodbye: 1 25 63 72
Find the smallest window that contains all words (in this case 17-25).
2. Coding: Given a text and a pattern, find if the elements of the pattern
appear in the text in the given order (but the elements don't have to be
contiguous), e.g.
text = hello world

f*w2011-11-08 08:11

2 楼

y*e2011-11-08 08:11

3 楼

贴了几个小时的初稿居然流传出去了
还被人转载到了水版
然后一堆人拍
我快受不了了

x*72011-11-08 08:11

4 楼

是用java还是c/c++?如果是java,我觉得用正则表达式很容易做第二题吧。

time
a

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

: 1. Algorithm (I think this question has appeared in this board multiple time
: s before):
: given n arrays of integers, each array represent the indices of a word in a
: text, e.g.
: hello: 5 14 19 35 52
: world: 11 17 29 40
: goodbye: 1 25 63 72
: Find the smallest window that contains all words (in this case 17-25).
: 2. Coding: Given a text and a pattern, find if the elements of the pattern
: appear in the text in the given order (but the elements don't have to be

d*o2011-11-08 08:11

5 楼

你们都搞几个帐号，不怕上黑名单？

s*y2011-11-08 08:11

6 楼

拍拍，
作为才女的负担啊。呵呵

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

: 贴了几个小时的初稿居然流传出去了
: 还被人转载到了水版
: 然后一堆人拍
: 我快受不了了

c*u2011-11-08 08:11

7 楼

我用的是C++，state machine，正则的话有点取巧了吧

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

: 是用java还是c/c++?如果是java,我觉得用正则表达式很容易做第二题吧。
:
: time
: a

e*i2011-11-08 08:11

8 楼

what to buy?

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

: rt

c*b2011-11-08 08:11

9 楼

莫气莫气
买买提太多无聊的人了，呵呵

l*c2011-11-08 08:11

10 楼

why state machine? two pointers scan and match is enough

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

: 我用的是C++，state machine，正则的话有点取巧了吧

D*a2011-11-08 08:11

11 楼

哎，你要写余雨找了个好工作嫁了个好老公，照样一堆人拍你。

c*u2011-11-08 08:11

12 楼

essentialy the same I think

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

: why state machine? two pointers scan and match is enough

d*r2011-11-08 08:11

13 楼

it's normal, if you want be a famous writer.

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

: 贴了几个小时的初稿居然流传出去了
: 还被人转载到了水版
: 然后一堆人拍
: 我快受不了了

x*n2011-11-08 08:11

14 楼

agree :)

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

: why state machine? two pointers scan and match is enough

y*e2011-11-08 08:11

15 楼

不是
关键是那个是一稿
基本上属于半成品

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

: it's normal, if you want be a famous writer.

l*c2011-11-08 08:11

16 楼

maybe when character repeats andmust reset, then state machine, I guess

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

: agree :)

d*r2011-11-08 08:11

17 楼

oh, it will never be 成品.
you will have 余雨之死 1.0, 余雨之死 2.0, 余雨之死 3.0, 余雨之死 2012, 余雨
之死 4S...

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

: 不是
: 关键是那个是一稿
: 基本上属于半成品

a*n2011-11-08 08:11

18 楼

第一题哪里有？

D*a2011-11-08 08:11

19 楼

余雨之死去活来
余雨之他杀完全手册

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

: oh, it will never be 成品.
: you will have 余雨之死 1.0, 余雨之死 2.0, 余雨之死 3.0, 余雨之死 2012, 余雨
: 之死 4S...

c*u2011-11-08 08:11

20 楼

don't know just think I've thought it before.
One way to solve this is to do a binary search regarding to the lower bound
and upper bound.

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

: 第一题哪里有？

d*r2011-11-08 08:11

21 楼

we should hear more good news for bio PhDs.
actually, there're several good news for job hunting for bio PhDs on this
board recently.

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

: 余雨之死去活来
: 余雨之他杀完全手册

x*n2011-11-08 08:11

22 楼

Not sure. Just my two cents. May have missed some special cases you
mentioned
bool DoesStringMatchPatternOrder(char* pString, char* pPattern)
{
if( !pString && !pPattern)
return false;
char* pCursorS = pString;
char* pCursorP = pPattern;
while(*pCursorS && *pCursorP){
while( *pCursorS && *pCursorS != *pCursorP)
pCursorS++;
pCursorP++;
}
return (*pCursorS) && (!*pCursorP);
}

guess

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

: maybe when character repeats andmust reset, then state machine, I guess

s*y2011-11-08 08:11

23 楼

最后作者出来说这一切的一切都是一个inception

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

: 余雨之死去活来
: 余雨之他杀完全手册

c*u2011-11-08 08:11

24 楼

Mine:
bool findPattern(const string& text, const string& pattern)
{
int n = strlen(pattern);
int count = 0;
for (int i = 0; i < strlen(text); i++) {
if (text[i] == pattern[count]) {
count++;
if (count == n)
return true;
}
}
return false;
}

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

: Not sure. Just my two cents. May have missed some special cases you
: mentioned
: bool DoesStringMatchPatternOrder(char* pString, char* pPattern)
: {
: if( !pString && !pPattern)
: return false;
: char* pCursorS = pString;
: char* pCursorP = pPattern;
: while(*pCursorS && *pCursorP){
: while( *pCursorS && *pCursorS != *pCursorP)

y*e2011-11-08 08:11

25 楼

写本在哈佛等你？在mit等你？

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

: we should hear more good news for bio PhDs.
: actually, there're several good news for job hunting for bio PhDs on this
: board recently.

x*n2011-11-08 08:11

26 楼

Then same idea :) So I guess I didn't miss special cases

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

: Mine:
: bool findPattern(const string& text, const string& pattern)
: {
: int n = strlen(pattern);
: int count = 0;
: for (int i = 0; i < strlen(text); i++) {
: if (text[i] == pattern[count]) {
: count++;
: if (count == n)
: return true;

l*12011-11-08 08:11

27 楼

在墙街等老张不错

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

: 写本在哈佛等你？在mit等你？

c*u2011-11-08 08:11

28 楼

For this one it doesn't matter I guess. But state machine is convenient for
string matching algorithms because it's hard to get wrong imo:)

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

: maybe when character repeats andmust reset, then state machine, I guess

a*n2011-11-08 08:11

29 楼

怎么没有人讨论第一题？这个比第二题难吧
用binary search合适吗？
这里应该在每个有序数组里拿出一个数，组成集合，让集合的range最小。还没想出跟
binary search的关系。

bound

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

: don't know just think I've thought it before.
: One way to solve this is to do a binary search regarding to the lower bound
: and upper bound.

c*u2011-11-08 08:11

30 楼

yes you can.
For the original set
hello: 5 14 19 35 52
world: 11 17 29 40
goodbye: 1 25 63 72
The range in the example is 1-72. You should have a recursive algorithm
to narrow down the range. The question is: do you move the lower or upper bo
und? It turns that you should consider both siutations (or you will miss som
e cases), you should should do new search for the range of 5-72 and 1-63, so
on and so forth.

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

: 怎么没有人讨论第一题？这个比第二题难吧
: 用binary search合适吗？
: 这里应该在每个有序数组里拿出一个数，组成集合，让集合的range最小。还没想出跟
: binary search的关系。
:
: bound

x*n2011-11-08 08:11

31 楼

有编程之美的话，上面有类似的题。应该不是binary search，对于这种输入应该是用
三个指针遍
历，只是行进策略有些特殊，纯粹瞎猜的:)

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

c*u2011-11-08 08:11

32 楼

指针遍历时间复杂度太高，而且3个只是例子，如果有n个array呢？

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

: 有编程之美的话，上面有类似的题。应该不是binary search，对于这种输入应该是用
: 三个指针遍
: 历，只是行进策略有些特殊，纯粹瞎猜的:)

x*n2011-11-08 08:11

33 楼

不好意思，不是很明白，如果是n，你的方法确定下一个要搜索的新range时好像也需
要O(n)的时
间，能不能再细讲一下

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

: 指针遍历时间复杂度太高，而且3个只是例子，如果有n个array呢？

c*u2011-11-08 08:11

34 楼

貌似是，不知道有没有其它解法

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

: 不好意思，不是很明白，如果是n，你的方法确定下一个要搜索的新range时好像也需
: 要O(n)的时
: 间，能不能再细讲一下

l*c2011-11-08 08:11

35 楼

I don't think it's so simple;
string : abac,
pattern: abc
return should be false, because a repeats again.

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

c*u2011-11-08 08:11

36 楼

by definition for this problem I think this one should return true.

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

: I don't think it's so simple;
: string : abac,
: pattern: abc
: return should be false, because a repeats again.

l*c2011-11-08 08:11

37 楼

3 pointers, minWindow = min{( max(abs(a-b), abs(b-c), abs(c-a)), ......}
I don'y know any other algorithm).
O(3n)

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

: 貌似是，不知道有没有其它解法

x*n2011-11-08 08:11

38 楼

我觉得我们理解题目上有些偏差，你的例子我的理解应该是return true，因为题目只
在乎出现的顺序

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

: I don't think it's so simple;
: string : abac,
: pattern: abc
: return should be false, because a repeats again.

c*u2011-11-08 08:11

39 楼

3 is only an example, consider the case for n arrays

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

: 3 pointers, minWindow = min{( max(abs(a-b), abs(b-c), abs(c-a)), ......}
: I don'y know any other algorithm).
: O(3n)

e*n2011-11-08 08:11

40 楼

If n >> x, I think it is better to do bottom up search.
consider the interval with length x. extend the interval to length x + 1,
if the interval contains all the arrays, return.

t*t2011-11-08 08:11

41 楼

同意，并没要求最短。例如：
string = hohowl
pattern = howl
如果只要求lz说的true or false，这个肯定是true，但是如果要求最短的话，state
machine就得加入针对pattern首字符的reset。时间上应该是O(len(string))就好了。
第一题给的arrays是sort好的吗？是的话是不是可以这么做：
造个数组ind[n]，每个元素初始化为某word第一次出现的index。然后记录ind[n]中最大/最小元素之差为distance。把最小元素move到该单词下一次出现的index，再算ind[n]中最大/最小元素之差，如果比distance小就替换掉。如此反复直到某次移动导致out of bound。（这个bound不是整个text的长度，而应该是某单词出现的次数）。如果有错还请指出

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

: 我觉得我们理解题目上有些偏差，你的例子我的理解应该是return true，因为题目只
: 在乎出现的顺序

d*g2011-11-08 08:11

42 楼

对于第一题，如果有n个array，每个array有m个元素，我能想到的时间复杂度是O(m*n*
lgn)，用堆来存最大和最小元素，取出最小元素，移到下一个，然后比较最大和最小元
素的差

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

: If n >> x, I think it is better to do bottom up search.
: consider the interval with length x. extend the interval to length x + 1,
: if the interval contains all the arrays, return.

c*p2011-11-08 08:11

43 楼

第二题的一个recursive解
int contains(char * text, char * pattern)
{
if (!*pattern){
return 1;
}

if ( !*text){
return 0;
}

if (* text != *pattern){
return contains(text+1, pattern);
} else {
return contains(text+1, pattern+1);
}
}