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 为四的时候就满足条件了。
|
