logo
Redian新闻
>未名空间
>Biology - 生物学
>
气死我了
avatar
气死我了# Biology - 生物学
c*u
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
avatar
f*w
2 楼
rt
avatar
y*e
3 楼
贴了几个小时的初稿居然流传出去了
还被人转载到了水版
然后一堆人拍
我快受不了了
avatar
x*7
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
avatar
d*o
5 楼
你们都搞几个帐号，不怕上黑名单？
avatar
s*y
6 楼
拍拍，
作为才女的负担啊。呵呵

【在 y********e 的大作中提到】
: 贴了几个小时的初稿居然流传出去了
: 还被人转载到了水版
: 然后一堆人拍
: 我快受不了了
avatar
c*u
7 楼
我用的是C++，state machine，正则的话有点取巧了吧

【在 x*******7 的大作中提到】
: 是用java还是c/c++?如果是java,我觉得用正则表达式很容易做第二题吧。
:
: time
: a
avatar
e*i
8 楼
what to buy?

【在 f******w 的大作中提到】
: rt
avatar
c*b
9 楼
莫气莫气
买买提太多无聊的人了，呵呵
avatar
l*c
10 楼
why state machine? two pointers scan and match is enough

【在 c*********u 的大作中提到】
: 我用的是C++，state machine，正则的话有点取巧了吧
avatar
D*a
11 楼
哎，你要写余雨找了个好工作嫁了个好老公，照样一堆人拍你。
avatar
c*u
12 楼
essentialy the same I think

【在 l******c 的大作中提到】
: why state machine? two pointers scan and match is enough
avatar
d*r
13 楼
it's normal, if you want be a famous writer.

【在 y********e 的大作中提到】
: 贴了几个小时的初稿居然流传出去了
: 还被人转载到了水版
: 然后一堆人拍
: 我快受不了了
avatar
x*n
14 楼
agree :)

【在 l******c 的大作中提到】
: why state machine? two pointers scan and match is enough
avatar
y*e
15 楼
不是
关键是那个是一稿
基本上属于半成品

【在 d*****r 的大作中提到】
: it's normal, if you want be a famous writer.
avatar
l*c
16 楼
maybe when character repeats andmust reset, then state machine, I guess

【在 x****n 的大作中提到】
: agree :)
avatar
d*r
17 楼
oh, it will never be 成品.
you will have 余雨之死 1.0, 余雨之死 2.0, 余雨之死 3.0, 余雨之死 2012, 余雨
之死 4S...

【在 y********e 的大作中提到】
: 不是
: 关键是那个是一稿
: 基本上属于半成品
avatar
a*n
18 楼
第一题哪里有？
avatar
D*a
19 楼
余雨之死去活来
余雨之他杀完全手册

【在 d*****r 的大作中提到】
: oh, it will never be 成品.
: you will have 余雨之死 1.0, 余雨之死 2.0, 余雨之死 3.0, 余雨之死 2012, 余雨
: 之死 4S...
avatar
c*u
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 的大作中提到】
: 第一题哪里有？
avatar
d*r
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 的大作中提到】
: 余雨之死去活来
: 余雨之他杀完全手册
avatar
x*n
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
avatar
s*y
23 楼
最后作者出来说这一切的一切都是一个inception

【在 D*a 的大作中提到】
: 余雨之死去活来
: 余雨之他杀完全手册
avatar
c*u
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)
avatar
y*e
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.
avatar
x*n
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;
avatar
l*1
27 楼
在墙街等老张 不错

【在 y********e 的大作中提到】
: 写本在哈佛等你？在mit等你？
avatar
c*u
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
avatar
a*n
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.
avatar
c*u
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
avatar
x*n
31 楼
有编程之美的话，上面有类似的题。应该不是binary search，对于这种输入应该是用
三个指针遍
历，只是行进策略有些特殊，纯粹瞎猜的:)

【在 a****n 的大作中提到】
: 怎么没有人讨论第一题？ 这个比第二题难吧
: 用binary search合适吗？
: 这里应该在每个有序数组里 拿出一个数，组成集合，让集合的range最小。还没想出跟
: binary search的关系。
:
: bound
avatar
c*u
32 楼
指针遍历时间复杂度太高，而且3个只是例子，如果有n个array呢？

【在 x****n 的大作中提到】
: 有编程之美的话，上面有类似的题。应该不是binary search，对于这种输入应该是用
: 三个指针遍
: 历，只是行进策略有些特殊，纯粹瞎猜的:)
avatar
x*n
33 楼
不好意思，不是很明白，如果是n， 你的方法确定下一个要搜索的新range时好像也需
要O(n)的时
间，能不能再细讲一下

【在 c*********u 的大作中提到】
: 指针遍历时间复杂度太高，而且3个只是例子，如果有n个array呢？
avatar
c*u
34 楼
貌似是，不知道有没有其它解法

【在 x****n 的大作中提到】
: 不好意思，不是很明白，如果是n， 你的方法确定下一个要搜索的新range时好像也需
: 要O(n)的时
: 间，能不能再细讲一下
avatar
l*c
35 楼
I don't think it's so simple;
string : abac,
pattern: abc
return should be false, because a repeats again.

【在 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;
avatar
c*u
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.
avatar
l*c
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 的大作中提到】
: 貌似是，不知道有没有其它解法
avatar
x*n
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.
avatar
c*u
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)
avatar
e*n
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.
avatar
t*t
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，因为题目只
: 在乎出现的顺序
avatar
d*g
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.
avatar
c*p
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);
}
}
相关阅读
大家看到Nature上总写着“日本语要约”这几个字有什么感受?求片全文， 有包子Urgent helppaper help (baozi)毛主席万岁，保佑我的核弹炸出蘑菇云尼玛，NIH房顶该全部砍了，就再不会有千老，再也不会有人跳火坑有人用过GeneJET的Midiprep的kit吗？质量如何？什么叫fly napping?做lentivirus失败，来请教troubleshootingEconomist报道的钱路路和Winfree的研究问大伙儿一个CO-IP的问题麻烦不断啊mES cell embronic body differentiation美国大多数生物PI也就是包工头，你可以什么都不懂，都不会，但是有钱招懂的人就行SDS-PAGE 蛋白电泳的问题。PI的进来看下 JSMF Grant 2012 application deadlines soon求文章pdf 。谢啦！【视频】郎咸平谈转基因 (转载)Bioinformatics F1签证 check乎？该考international还是national certificate in molecular biololy （ASCP）？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。