i**********e
发帖数: 1145 | 1 怎样判断“满足都包含的条件”以及“不破坏条件”？
>> 判断“满足都包含的条件”就是利用一个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['... 阅读全帖 |
|
s*******e
发帖数: 93 | 2 我也写了一个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];
... 阅读全帖 |
|
c**s
发帖数: 43 | 3 你解释的和上面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 ... 阅读全帖 |
|
s*******e
发帖数: 93 | 4 这里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) |
|
s*******e
发帖数: 93 | 5 为什么code 贴出来显得这么长。。我本来觉得思路挺简单的。
基本上就是，两个map，
一个存每个字母须要出现多少次（needToFind），
一个存每个字母出现了多少次（hasFound）,
查询修改都是O(1)
两个pointer,一个begin,一个end,一开始都在开头。
每轮end往后移动一格。对应的hasFound加一。
然后再看begin, 只要begin
begin就不断往后移。
只要满足都包含的条件，就看总长度有没有小于之前找到的最小长度。
characters, |
|
G****o
发帖数: 155 | 6 通过两个map来记录需要找到pattern(NeedtoFind)和暂时找到到pattern(HasFound)。
每次end往前移动一步后，都坚持当前到条件是否满足要求。
题目要求到是，最小长度，通过检查两个map。。。
不知道解释清楚了没有。。。
please correct me if wrong. thx |
|
c**s
发帖数: 43 | 7 怎样判断“满足都包含的条件”以及“不破坏条件”？
不用一个counter的话，每次判断都要O(M)。
用counter的话，对应的hasFound超过了needToFind的时候怎么处理？
算下面这个test case时，
当end分别到了C和最后一个B的时候，什么时候begin该停？
S1=ABAAAACAB
S2=AABC
有人解释一下吗？
另外，感觉用另外一个贴paul的链表的算法，在每个node上再加个双向链表，
来指向下一个重复字母，应该就能在O(N)内处理s2有重复字母的情况。
只是变得更复杂了。没这个简洁。 |
|
