Redian新闻
>
ipad还有什么好的deal?
avatar
ipad还有什么好的deal?# Apple - 家有苹果
r*l
1
Coding: A long string text, given some characters, find the shortest
substring covering all given characters.
貌似DP.可想不出公式来.
avatar
j*u
2
target有买ipad送100刀gift card的deal,看上去很不错。不知道在新的ipad发布之前
,会不会还有更好的ipad air的deal?谢谢。
avatar
s*3
3
这貌似还是那道经典的移动windows的题目吧,你翻翻paul大牛之前关于这个的帖子~
avatar
z*e
4
差不多了,知足吧。
avatar
r*l
5
能不能给个LINK
找了半天没找到
是个新手,不知道谁是Paul大牛

【在 s*******3 的大作中提到】
: 这貌似还是那道经典的移动windows的题目吧,你翻翻paul大牛之前关于这个的帖子~
avatar
r*n
6

等着吧

【在 j**u 的大作中提到】
: target有买ipad送100刀gift card的deal,看上去很不错。不知道在新的ipad发布之前
: ,会不会还有更好的ipad air的deal?谢谢。

avatar
h*d
7
ding
avatar
r*l
8
还有人知道答案吗

【在 h**********d 的大作中提到】
: ding
avatar
i*e
9
这题蛮有意思的,我刚写完。
其实 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
avatar
x*y
10
面试题不会要求这么复杂的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:

avatar
s*e
11
我也写了一个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<
if(count==charCount)
{
length=end-begin+1;
if(length{
minLength=length;
minRange.begin=begin;
minRange.end=end;
}
}

}

return minRange;
}
avatar
s*e
12
为什么code 贴出来显得这么长。。我本来觉得思路挺简单的。
基本上就是,两个map,
一个存每个字母须要出现多少次(needToFind),
一个存每个字母出现了多少次(hasFound),
查询修改都是O(1)
两个pointer,一个begin,一个end,一开始都在开头。
每轮end往后移动一格。对应的hasFound加一。
然后再看begin, 只要beginbegin就不断往后移。
只要满足都包含的条件,就看总长度有没有小于之前找到的最小长度。

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,

avatar
i*e
13
你的代码 有两个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,

avatar
i*e
14
啊!
你的思路我明白了,真的很简洁,简单,根本不用很复杂的数据结构!
没错,你的复杂度是 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就不断往后移。
: 只要满足都包含的条件,就看总长度有没有小于之前找到的最小长度。

avatar
s*r
15
stormrage的解法看不懂 ,可不可以解释解释?
avatar
G*o
16
通过两个map来记录需要找到pattern(NeedtoFind)和暂时找到到pattern(HasFound)。
每次end往前移动一步后,都坚持当前到条件是否满足要求。
题目要求到是,最小长度,通过检查两个map。。。
不知道解释清楚了没有。。。
please correct me if wrong. thx

【在 s*******r 的大作中提到】
: stormrage的解法看不懂 ,可不可以解释解释?
avatar
s*r
17
嗯,好像搞明白了。 就是再寻找最小substring过程中,从当前substring的开头
delete重复出现的字符和紧随后的不在pattern list中的字符。很符合常规思维的idea
,但实现得有技巧:)

【在 G****o 的大作中提到】
: 通过两个map来记录需要找到pattern(NeedtoFind)和暂时找到到pattern(HasFound)。
: 每次end往前移动一步后,都坚持当前到条件是否满足要求。
: 题目要求到是,最小长度,通过检查两个map。。。
: 不知道解释清楚了没有。。。
: please correct me if wrong. thx

avatar
f*g
18
牛帖:
http://www.mitbbs.com/article_t1/JobHunting/31696043_0_1.html

【在 i**********e 的大作中提到】
: 啊!
: 你的思路我明白了,真的很简洁,简单,根本不用很复杂的数据结构!
: 没错,你的复杂度是 O(N)的。
: 应该更清楚的说,是 2*N。
: 因为 begin 指针最多只能循环 N 次,而 end 指针也是最多只能循环 N 次,加起来就
: 是 2N.
: 我总结了一下,主要是我把问题想的太复杂了。
: 我的思路一直纠结于 begin 和 end 之间的字符串,其实根本没这个必要。
: 再次赞叹你的思路!
: 学习了~

avatar
c*s
19
怎样判断“满足都包含的条件”以及“不破坏条件”?
不用一个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就不断往后移。
: 只要满足都包含的条件,就看总长度有没有小于之前找到的最小长度。

avatar
s*e
20
这里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)
avatar
i*e
21
怎样判断“满足都包含的条件”以及“不破坏条件”?
>> 判断“满足都包含的条件”就是利用一个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
avatar
c*s
22
嗯,你说得对。刚刚我在上班的路上想了一下,也是觉得这样算行。
以后要是真的面到这一题,就想假假说一个错的链表方法,
过一会儿就做恍然大悟状,一口气说出这个算法。。

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

avatar
c*s
23
你解释的和上面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 countcount++
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 为四的时候就满足条件了。

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。