c*********u 发帖数: 361 | 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 |
x*******7 发帖数: 223 | 2 是用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
|
c*********u 发帖数: 361 | 3 我用的是C++,state machine,正则的话有点取巧了吧
【在 x*******7 的大作中提到】 : 是用java还是c/c++?如果是java,我觉得用正则表达式很容易做第二题吧。 : : time : a
|
l******c 发帖数: 2555 | 4 why state machine? two pointers scan and match is enough
【在 c*********u 的大作中提到】 : 我用的是C++,state machine,正则的话有点取巧了吧
|
c*********u 发帖数: 361 | 5 essentialy the same I think
【在 l******c 的大作中提到】 : why state machine? two pointers scan and match is enough
|
x****n 发帖数: 74 | 6 agree :)
【在 l******c 的大作中提到】 : why state machine? two pointers scan and match is enough
|
l******c 发帖数: 2555 | 7 maybe when character repeats andmust reset, then state machine, I guess
【在 x****n 的大作中提到】 : agree :)
|
a****n 发帖数: 70 | |
c*********u 发帖数: 361 | 9 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 的大作中提到】 : 第一题哪里有?
|
x****n 发帖数: 74 | 10 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
|
|
|
c*********u 发帖数: 361 | 11 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)
|
x****n 发帖数: 74 | 12 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;
|
c*********u 发帖数: 361 | 13 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****n 发帖数: 70 | 14 怎么没有人讨论第一题? 这个比第二题难吧
用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*********u 发帖数: 361 | 15 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****n 发帖数: 74 | 16 有编程之美的话,上面有类似的题。应该不是binary search,对于这种输入应该是用
三个指针遍
历,只是行进策略有些特殊,纯粹瞎猜的:)
【在 a****n 的大作中提到】 : 怎么没有人讨论第一题? 这个比第二题难吧 : 用binary search合适吗? : 这里应该在每个有序数组里 拿出一个数,组成集合,让集合的range最小。还没想出跟 : binary search的关系。 : : bound
|
c*********u 发帖数: 361 | 17 指针遍历时间复杂度太高,而且3个只是例子,如果有n个array呢?
【在 x****n 的大作中提到】 : 有编程之美的话,上面有类似的题。应该不是binary search,对于这种输入应该是用 : 三个指针遍 : 历,只是行进策略有些特殊,纯粹瞎猜的:)
|
x****n 发帖数: 74 | 18 不好意思,不是很明白,如果是n, 你的方法确定下一个要搜索的新range时好像也需
要O(n)的时
间,能不能再细讲一下
【在 c*********u 的大作中提到】 : 指针遍历时间复杂度太高,而且3个只是例子,如果有n个array呢?
|
c*********u 发帖数: 361 | 19 貌似是,不知道有没有其它解法
【在 x****n 的大作中提到】 : 不好意思,不是很明白,如果是n, 你的方法确定下一个要搜索的新range时好像也需 : 要O(n)的时 : 间,能不能再细讲一下
|
l******c 发帖数: 2555 | 20 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;
|
|
|
c*********u 发帖数: 361 | 21 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******c 发帖数: 2555 | 22 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****n 发帖数: 74 | 23 我觉得我们理解题目上有些偏差,你的例子我的理解应该是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*********u 发帖数: 361 | 24 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******n 发帖数: 3 | 25 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********t 发帖数: 5415 | 26 同意,并没要求最短。例如:
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***g 发帖数: 252 | 27 对于第一题,如果有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***p 发帖数: 221 | 28 第二题的一个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);
}
} |