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);
}
}
相关阅读
千人计划失败十周年祭看卫纪委和生命医学腐烂推荐一个简便好用的文献追踪软件~~~有些蜂蜜在室温时凝固（变粘稠），有些还呈现液体状。那种是真(转载)paper thanks变态PI二三事老板非让用Bioruptor做ChIP，结果给bug啦，求教啊啊啊。。。发包子，求paper一篇，谢谢！AACR2016 找室友哪里能查到老鼠的proinflammatory cytokine的正常和病理状态下的血清浓度industry position avaialbe : Cancer Biology生物信息招人从地狱十八层地狱爬到地狱17层，可喜可贺！冷冻电镜技术龙虎榜zzpaper thanksRate My Lab发包子，求paper一篇，谢谢！弱问，怎么retrieve cummeRbund generate的 Gene ID(Cuff ID)paper ask同一个蛋白用两种抗体为什么WB条带不重叠paper help, thanks
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。