r*******l 发帖数: 511 | 1 Coding: A long string text, given some characters, find the shortest
substring covering all given characters.
貌似DP.可想不出公式来. |
s*******3 发帖数: 134 | 2 这貌似还是那道经典的移动windows的题目吧,你翻翻paul大牛之前关于这个的帖子~ |
r*******l 发帖数: 511 | 3 能不能给个LINK
找了半天没找到
是个新手,不知道谁是Paul大牛
【在 s*******3 的大作中提到】 : 这貌似还是那道经典的移动windows的题目吧,你翻翻paul大牛之前关于这个的帖子~
|
h**********d 发帖数: 4313 | |
r*******l 发帖数: 511 | 5 还有人知道答案吗
【在 h**********d 的大作中提到】 : ding
|
i**********e 发帖数: 1145 | 6 这题蛮有意思的,我刚写完。
其实 idea 挺容易明白,我说一次给你听就明白了,但是没图解释起来比较费劲。这题
最复杂的地方其实就是选择怎么把数据结构结合起来。
一开始我以为要用 dp,其实 greedy 就可以了。
总复杂度是 O(N lg M),N 为 str 的长度,M 为 pattern 的长度。
主要原因有个 lg M 是因为 STL map 里的 find() 函数复杂度为 O(lg M).
我用的是 map + queue + hashtable (有点吓人呵呵,可能我想太复杂了)。
我暂时还没想到怎么提升到 O(N),应该是利用一个更好的数据结构吧。如果有高人知
道怎么提升到 O(N),请指点一下吧~
这是我做的 test cases:
第一行是 string 和 pattern,
第二行是函数 return 的 start and end position,然后是 shortest substring。
cabeca cae
3 5 eca
cfabeca cae
4 6 eca
cabefgecdaecf cae
9 11 aec
cabwefgewcwaefcf cae
9 12 cwae
abcabdebac cda
2 5 cabd
abcabdebac cea
6 9 ebac
acbdbaab aabd
3 6 dbaa
caaec cae
2 4 aec
caae cae
0 3 caae
acbbaab aab
3 5 baa
acbba aab
0 4 acbba
acbba aab
贴个代码吧,
void findMinWindow(char str[], char pattern[], int &start, int &end) {
int len1 = strlen(str);
int len2 = strlen(pattern);
int minLen = 2147483647;
// hash table init all to 0s
// is used to check how many letters left
// in the pattern to be filled
char patHash[256] = {0};
// we keep an array of queues
// for each letter
queue q[256];
// a map that maps an int to char
// the reason an array is not used
// is because we want to find the
// minimum and maximum index with
// valid character from pattern
map m;
for (int i = 0; i < len2; i++)
patHash[pattern[i]]++;
// set the rest to -1 so that we know
// that letter does not exist in pattern
for (int i = 0; i < 256; i++)
if (patHash[i] == 0)
patHash[i] = -1;
for (int i = 0; i < len1; i++) {
// replace the character in the queue
if (patHash[str[i]] == 0) {
int idxToErase = q[str[i]].front();
map::iterator it = m.find(idxToErase);
m.erase(it);
m[i] = str[i];
q[str[i]].pop();
q[str[i]].push(i);
}
// push character to queue
if (patHash[str[i]] > 0) {
q[str[i]].push(i);
m[i] = str[i];
patHash[str[i]]--;
} // end if
// found a window, check for minimum
if (m.size() == len2) {
int lastIndex = m.rbegin()->first;
int firstIndex = m.begin()->first;
int len = lastIndex - firstIndex + 1;
if (len < minLen) {
minLen = len;
start = firstIndex;
end = lastIndex;
}
} // end if
} // end for
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
x**y 发帖数: 70 | 7 面试题不会要求这么复杂的CODE的... 应该有简单写的.
【在 i**********e 的大作中提到】 : 这题蛮有意思的,我刚写完。 : 其实 idea 挺容易明白,我说一次给你听就明白了,但是没图解释起来比较费劲。这题 : 最复杂的地方其实就是选择怎么把数据结构结合起来。 : 一开始我以为要用 dp,其实 greedy 就可以了。 : 总复杂度是 O(N lg M),N 为 str 的长度,M 为 pattern 的长度。 : 主要原因有个 lg M 是因为 STL map 里的 find() 函数复杂度为 O(lg M). : 我用的是 map + queue + hashtable (有点吓人呵呵,可能我想太复杂了)。 : 我暂时还没想到怎么提升到 O(N),应该是利用一个更好的数据结构吧。如果有高人知 : 道怎么提升到 O(N),请指点一下吧~ : 这是我做的 test cases:
|
s*******e 发帖数: 93 | 8 我也写了一个code. 有测试ihasleetcode的所有test case答案都一样。
如果没有想错的话应该是O(n)
因为begin和end两个值都最多扫过每一个字母一次
假设都是ascii字符
typedef struct range
{
int begin;
int end;
} Range;
Range shortestSubstring(const char* str, int strLen, const char* characters,
int charCount)
{
int* needToFind=new int[256];
int* hasFound=new int[256];
for(int i=0;i<256;i++)
{
needToFind[i]=0;
hasFound[i]=0;
}
for(int i=0;i
{
int index=(int)characters[i];
needToFind[index]++;
}
int count=0;
// count is used to judge if the range satisfies the requirement
// the criterion is count==charCount
int begin=0;
int end=-1;
int index=0;
Range minRange;
minRange.begin=-1;
minRange.end=-1;
int minLength=strLen+1;
int length=0;
while(end+1
{
end++;
index=(int)str[end];
if(needToFind[index]>0)
{
hasFound[index]++;
if(hasFound[index]<=needToFind[index])
{
count++;
}
}
while(begin
{
index=(int)str[begin];
if(needToFind[index]==0)
{
begin++;
}
else if(hasFound[index]>needToFind[index])
{
begin++;
hasFound[index]--;
}
else
{
break;
}
}
// cout<<"begin:"<
if(count==charCount)
{
length=end-begin+1;
if(length
{
minLength=length;
minRange.begin=begin;
minRange.end=end;
}
}
}
return minRange;
} |
s*******e 发帖数: 93 | 9 为什么code 贴出来显得这么长。。我本来觉得思路挺简单的。
基本上就是,两个map,
一个存每个字母须要出现多少次(needToFind),
一个存每个字母出现了多少次(hasFound),
查询修改都是O(1)
两个pointer,一个begin,一个end,一开始都在开头。
每轮end往后移动一格。对应的hasFound加一。
然后再看begin, 只要begin
begin就不断往后移。
只要满足都包含的条件,就看总长度有没有小于之前找到的最小长度。
characters,
【在 s*******e 的大作中提到】 : 我也写了一个code. 有测试ihasleetcode的所有test case答案都一样。 : 如果没有想错的话应该是O(n) : 因为begin和end两个值都最多扫过每一个字母一次 : 假设都是ascii字符 : typedef struct range : { : int begin; : int end; : } Range; : Range shortestSubstring(const char* str, int strLen, const char* characters,
|
i**********e 发帖数: 1145 | 10 你的代码 有两个while loop。
while(end+1
.....
while(begin
...
}
}
可以解释下为什么 O(N) 吗?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
characters,
【在 s*******e 的大作中提到】 : 我也写了一个code. 有测试ihasleetcode的所有test case答案都一样。 : 如果没有想错的话应该是O(n) : 因为begin和end两个值都最多扫过每一个字母一次 : 假设都是ascii字符 : typedef struct range : { : int begin; : int end; : } Range; : Range shortestSubstring(const char* str, int strLen, const char* characters,
|
|
|
i**********e 发帖数: 1145 | 11 啊!
你的思路我明白了,真的很简洁,简单,根本不用很复杂的数据结构!
没错,你的复杂度是 O(N)的。
应该更清楚的说,是 2*N。
因为 begin 指针最多只能循环 N 次,而 end 指针也是最多只能循环 N 次,加起来就
是 2N.
我总结了一下,主要是我把问题想的太复杂了。
我的思路一直纠结于 begin 和 end 之间的字符串,其实根本没这个必要。
再次赞叹你的思路!
学习了~
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*******e 的大作中提到】 : 为什么code 贴出来显得这么长。。我本来觉得思路挺简单的。 : 基本上就是,两个map, : 一个存每个字母须要出现多少次(needToFind), : 一个存每个字母出现了多少次(hasFound), : 查询修改都是O(1) : 两个pointer,一个begin,一个end,一开始都在开头。 : 每轮end往后移动一格。对应的hasFound加一。 : 然后再看begin, 只要begin: begin就不断往后移。 : 只要满足都包含的条件,就看总长度有没有小于之前找到的最小长度。
|
s*******r 发帖数: 47 | 12 stormrage的解法看不懂 ,可不可以解释解释? |
G****o 发帖数: 155 | 13 通过两个map来记录需要找到pattern(NeedtoFind)和暂时找到到pattern(HasFound)。
每次end往前移动一步后,都坚持当前到条件是否满足要求。
题目要求到是,最小长度,通过检查两个map。。。
不知道解释清楚了没有。。。
please correct me if wrong. thx
【在 s*******r 的大作中提到】 : stormrage的解法看不懂 ,可不可以解释解释?
|
s*******r 发帖数: 47 | 14 嗯,好像搞明白了。 就是再寻找最小substring过程中,从当前substring的开头
delete重复出现的字符和紧随后的不在pattern list中的字符。很符合常规思维的idea
,但实现得有技巧:)
【在 G****o 的大作中提到】 : 通过两个map来记录需要找到pattern(NeedtoFind)和暂时找到到pattern(HasFound)。 : 每次end往前移动一步后,都坚持当前到条件是否满足要求。 : 题目要求到是,最小长度,通过检查两个map。。。 : 不知道解释清楚了没有。。。 : please correct me if wrong. thx
|
f***g 发帖数: 214 | 15 牛帖:
http://www.mitbbs.com/article_t1/JobHunting/31696043_0_1.html
【在 i**********e 的大作中提到】 : 啊! : 你的思路我明白了,真的很简洁,简单,根本不用很复杂的数据结构! : 没错,你的复杂度是 O(N)的。 : 应该更清楚的说,是 2*N。 : 因为 begin 指针最多只能循环 N 次,而 end 指针也是最多只能循环 N 次,加起来就 : 是 2N. : 我总结了一下,主要是我把问题想的太复杂了。 : 我的思路一直纠结于 begin 和 end 之间的字符串,其实根本没这个必要。 : 再次赞叹你的思路! : 学习了~
|
c**s 发帖数: 43 | 16 怎样判断“满足都包含的条件”以及“不破坏条件”?
不用一个counter的话,每次判断都要O(M)。
用counter的话,对应的hasFound超过了needToFind的时候怎么处理?
算下面这个test case时,
当end分别到了C和最后一个B的时候,什么时候begin该停?
S1=ABAAAACAB
S2=AABC
有人解释一下吗?
另外,感觉用另外一个贴paul的链表的算法,在每个node上再加个双向链表,
来指向下一个重复字母,应该就能在O(N)内处理s2有重复字母的情况。
只是变得更复杂了。没这个简洁。
【在 s*******e 的大作中提到】 : 为什么code 贴出来显得这么长。。我本来觉得思路挺简单的。 : 基本上就是,两个map, : 一个存每个字母须要出现多少次(needToFind), : 一个存每个字母出现了多少次(hasFound), : 查询修改都是O(1) : 两个pointer,一个begin,一个end,一开始都在开头。 : 每轮end往后移动一格。对应的hasFound加一。 : 然后再看begin, 只要begin: begin就不断往后移。 : 只要满足都包含的条件,就看总长度有没有小于之前找到的最小长度。
|
s*******e 发帖数: 93 | 17 这里count是判断满足条件的唯一依据
我的code里面是这样控制count的:
if(hasFound[index]<=needToFind[index])
{
count++;
}
就是说,如果只需要两个A,当看到第3个A的时候就不管了。
然后count一旦满足条件,既count == S2的长度,之后就永远都是满足条件的状态了
你的例子是
当end移动到S1中的C的位置,count应该就到4。这是begin应该在1(B),end应该在6
(C)
关于舍弃前面的string,当end到3(第3个A)的时候,begin应该还在0,
这是就因hasFound[A]=3,needsToFind[A]=2,就可以知道第一个A就可以不要
但是B不能丢掉,因为目前只有一个B,所以现在begin就在1 (B的位置)
然后end移动到8(最后一个B),这是begin所在位置的B就可以丢掉了,然后之后的连续3个A
也可以丢掉,直到hasFound[A]==2,最终begin会在5(倒数第二个A) |
i**********e 发帖数: 1145 | 18 怎样判断“满足都包含的条件”以及“不破坏条件”?
>> 判断“满足都包含的条件”就是利用一个counter。当满足了包含的条件之后,就可
以确保“不破坏条件”了。
不用一个counter的话,每次判断都要O(M)。
>>对的。
用counter的话,对应的hasFound超过了needToFind的时候怎么处理?
>>hasFound 超过了 needToFind counter 就不要加一,否则应该加一。
假设S1=ABAAAACAB,S2=AABC,当你遇到两个 A 的时候就 hasFound['a'] 加两次,值
为二。但是第三次你遇到 A 的时候就不必加了,因为这不帮助于满足条件。当
counter 为四的时候就满足条件了。
算下面这个test case时,
当end分别到了C和最后一个B的时候,什么时候begin该停?
S1=ABAAAACAB
S2=AABC
有人解释一下吗?
>>当end到了 C 的时候,就意味着刚满足条件,因为那时候 counter = 4.这时候就应
该开始移动 begin 指针,往右边挪。这时候 hasFound['a']=5, hasFound['b']=1,
hasFound['c']=1.这时候就比较 hasFound[S1[begin]] (5) 是否大于 needToFind[S1[
begin]] (2).如果是的话,那么 begin 指针可以往右移并且不破坏条件。由于 5 > 2,
那就往右移一格。这时候 begin 指向 B 了。hasFound['b'] = 1 等于 needToFind['b
'] = 1,这意味着往右移的话即将破坏条件,所以这时候我们立即停止移动。
另外,感觉用另外一个贴paul的链表的算法,在每个node上再加个双向链表,
来指向下一个重复字母,应该就能在O(N)内处理s2有重复字母的情况。
只是变得更复杂了。没这个简洁。
>>我看了paul的链表算法,没怎么看明白怎样才可以 O(N),你可以解释一下吗?谢谢。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
c**s 发帖数: 43 | 19 嗯,你说得对。刚刚我在上班的路上想了一下,也是觉得这样算行。
以后要是真的面到这一题,就想假假说一个错的链表方法,
过一会儿就做恍然大悟状,一口气说出这个算法。。
6
【在 s*******e 的大作中提到】 : 这里count是判断满足条件的唯一依据 : 我的code里面是这样控制count的: : if(hasFound[index]<=needToFind[index]) : { : count++; : } : 就是说,如果只需要两个A,当看到第3个A的时候就不管了。 : 然后count一旦满足条件,既count == S2的长度,之后就永远都是满足条件的状态了 : 你的例子是 : 当end移动到S1中的C的位置,count应该就到4。这是begin应该在1(B),end应该在6
|
c**s 发帖数: 43 | 20 你解释的和上面storm说的是一样的。
关于paul的链表,我没看仔细,下面是我自己写的。
没想到要写这么久。真的面的时候应该就废了。
很长,有耐心就慢慢看吧。。不知道对了对,意思应该在那了。
早知道应该写成C,可以跑试试看。
这么长,只是为了比begin-end那个少扫一遍。。。
defrecord NodeType
ch char
pos int
prePos *NodeType
nxtPos *NodeType
preSameChar *NodeType
nxtSameChar *NodeType
// S2 char to first tracked S2 NodeType (pointing to the start of
// a linked list of same char NodeType by nxtSameChar)
nodesFoundFirst hashmap
// S2 char to last tracked S2 NodeType (pointing to the end of
// a linked list of same char NodeType by preSameChar)
nodesFoundLast hashmap
firstPos *NodeType = null // first tracked S2 char in S1
lastPos *NodeType = null // last tracked S2 char in S1
needToFind hashmap
hasFound hashmap
count = 0
minLen = 0
init needToFind and hasFound from s2
for i=0 to len(s1)
if s1[i] in s2
hasFound[s1[i]]++
newNode = new NodeType(s1[i], i, null, null, null, null)
if firstPos is null
firstPos = newNode
if nodesFoundFirst contains s1[i]
oriNodeFirst = nodesFoundFirst[s1[i]]
if hasFound[s1[i]]>needToFind[s1[i]]
hasFound[s1[i]]--
// delete it from pos linked list
if oriNodeFirst == firstPos
firstPos = oriNodefirst.nxtPos
else
oriNodeFirst.prePos.nxtPos = oriNodeFirst.nxtPos
if oriNodeFirst == lasPos
lastPos = oriNodeFirst.prePos
else
oriNodeFirst.nxtPos.prePos = oriNodeFirst.prePos
// delete it from same char linked list
if needToFind[s1[i]] > 1
nodesFoundFirst[s1[i]] = oriNodeFirst.nxtSameChar
nodesFoundFirst[s1[i]].preSameChar = null
// append to same char linked list
if needToFind[s1[i]] > 1
newNode.preSameChar = nodesFoundLast[s1[i]]
nodesFoundLast[s1[i]].nxtSameChar = newNode
nodesFoundLast[s1[i]] = newNode
else
nodesFoundFirst[s1[i]] = nodesFoundLast[s1[i]] = newNode
else
nodesFoundFirst[s1[i]] = nodesFoundLast[s1[i]] = newNode
if lastPos is not null
lastPos.nxtPos = newNode
newNode.prePos = lastPos
lastPos = newNode
// update min len
if count
count++
else
if lastPos.pos - firstPos.pos < minLen
minLen = lastPos.pos - firstPos.pos
【在 i**********e 的大作中提到】 : 怎样判断“满足都包含的条件”以及“不破坏条件”? : >> 判断“满足都包含的条件”就是利用一个counter。当满足了包含的条件之后,就可 : 以确保“不破坏条件”了。 : 不用一个counter的话,每次判断都要O(M)。 : >>对的。 : 用counter的话,对应的hasFound超过了needToFind的时候怎么处理? : >>hasFound 超过了 needToFind counter 就不要加一,否则应该加一。 : 假设S1=ABAAAACAB,S2=AABC,当你遇到两个 A 的时候就 hasFound['a'] 加两次,值 : 为二。但是第三次你遇到 A 的时候就不必加了,因为这不帮助于满足条件。当 : counter 为四的时候就满足条件了。
|