w*x
2 楼
Given an input array of integers of size n, and a query array of
integers of size k, find the smallest window of input array that
contains all the elements of query array and also in the same order
integers of size k, find the smallest window of input array that
contains all the elements of query array and also in the same order
J*S
3 楼
是随机抽的。
p*2
4 楼
什么复杂度要求，感觉就是一道DP吧。
【在 w****x 的大作中提到】
: Given an input array of integers of size n, and a query array of
: integers of size k, find the smallest window of input array that
: contains all the elements of query array and also in the same order
L*1
5 楼
我收到第3个fb 的时候给我的
l*a
6 楼
为什么不是两指针
为什么不是slide window
就是slide windows然后要求有序吧
【在 p*****2 的大作中提到】
:
: 什么复杂度要求，感觉就是一道DP吧。
为什么不是slide window
就是slide windows然后要求有序吧
【在 p*****2 的大作中提到】
:
: 什么复杂度要求，感觉就是一道DP吧。
b*8
7 楼
我买了10000$以上，他给了。。。
p*2
8 楼
没序就是two pointer 和 sliding window了。
有序你怎么搞？
【在 l*****a 的大作中提到】
: 为什么不是两指针
: 为什么不是slide window
: 就是slide windows然后要求有序吧
J*S
9 楼
想起来了，我过45岁生日的时候给我的。
w*x
10 楼
这题DP??我怎么感觉是reverse indexing?
【在 p*****2 的大作中提到】
:
: 没序就是two pointer 和 sliding window了。
: 有序你怎么搞？
s*k
11 楼
大叔你生日也告诉EBAY了？
【在 J**S 的大作中提到】
: 想起来了，我过45岁生日的时候给我的。
【在 J**S 的大作中提到】
: 想起来了，我过45岁生日的时候给我的。
l*a
12 楼
HashMap 存query array value,query array index
然后每次循环初始currentIndex=-1;意思是准备先找query array的第0个
if(!map.containsKey(input[index])) {end++;}
if(map.containsKey(input[index]) {
if(map.get(input[index])==currentIndex）{end++;}
else if (map.get(input[index])==currentIndex+1){end++; currentIndex++;}
else {break;}
}
找到currentIndex==Query array size 算是找到一组
###第一个的出现次数还得计数。。
【在 p*****2 的大作中提到】
:
: 没序就是two pointer 和 sliding window了。
: 有序你怎么搞？
然后每次循环初始currentIndex=-1;意思是准备先找query array的第0个
if(!map.containsKey(input[index])) {end++;}
if(map.containsKey(input[index]) {
if(map.get(input[index])==currentIndex）{end++;}
else if (map.get(input[index])==currentIndex+1){end++; currentIndex++;}
else {break;}
}
找到currentIndex==Query array size 算是找到一组
###第一个的出现次数还得计数。。
【在 p*****2 的大作中提到】
:
: 没序就是two pointer 和 sliding window了。
: 有序你怎么搞？
l*r
13 楼
ebay真是一团糟啊.
p*2
14 楼
你的算法是啥样的？
【在 w****x 的大作中提到】
:
: 这题DP??我怎么感觉是reverse indexing?
t*e
15 楼
都没见过ebuck长什么样子
【在 l***r 的大作中提到】
: 需要一个quarter买多少东东?
【在 l***r 的大作中提到】
: 需要一个quarter买多少东东?
w*x
16 楼
短的在长的那个做reverse indexing,
比如按顺序是如下的：
1 3 5 8 13 17
0 2 4 6 9
7 10 14 21
那么第一条是1 2 7
然后第二条是3, 4, 10
然后5, 6, 10
8, 9, 10
然后就没了
【在 p*****2 的大作中提到】
:
: 你的算法是啥样的？
n*n
17 楼
一直以为大家都有的
【在 J**S 的大作中提到】
: 是随机抽的。
【在 J**S 的大作中提到】
: 是随机抽的。
p*2
18 楼
这个可行，不过太麻烦了。为什么不用DP呢？
【在 w****x 的大作中提到】
:
: 短的在长的那个做reverse indexing,
: 比如按顺序是如下的：
: 1 3 5 8 13 17
: 0 2 4 6 9
: 7 10 14 21
: 那么第一条是1 2 7
: 然后第二条是3, 4, 10
: 然后5, 6, 10
: 8, 9, 10
P*r
19 楼
据说是随机的。。碰运气
p*2
20 楼
能不能说说算法呢？发现我现在java太弱了。
【在 l*****a 的大作中提到】
: HashMap
: 然后每次循环初始currentIndex=-1;意思是准备先找query array的第0个
: if(!map.containsKey(input[index])) {end++;}
: if(map.containsKey(input[index]) {
: if(map.get(input[index])==currentIndex）{end++;}
: else if (map.get(input[index])==currentIndex+1){end++; currentIndex++;}
: else {break;}
: }
: 找到currentIndex==Query array size 算是找到一组
: ###第一个的出现次数还得计数。。
e*i
21 楼
wait
b*n
22 楼
这题跟leetcode OJ上的minimum window substring有什么区别？我感觉好像是一模一
样的。
【在 w****x 的大作中提到】
: Given an input array of integers of size n, and a query array of
: integers of size k, find the smallest window of input array that
: contains all the elements of query array and also in the same order
样的。
【在 w****x 的大作中提到】
: Given an input array of integers of size n, and a query array of
: integers of size k, find the smallest window of input array that
: contains all the elements of query array and also in the same order
l*a
23 楼
我就会滑动窗口的算法啊，dp/reverse index都不会
【在 p*****2 的大作中提到】
:
: 能不能说说算法呢？发现我现在java太弱了。
【在 p*****2 的大作中提到】
:
: 能不能说说算法呢？发现我现在java太弱了。
p*2
24 楼
那你说说滑动窗口吧。找到之后怎么继续处理？
【在 l*****a 的大作中提到】
: 我就会滑动窗口的算法啊，dp/reverse index都不会
w*x
25 楼
这题怎么DP?
【在 p*****2 的大作中提到】
:
: 那你说说滑动窗口吧。找到之后怎么继续处理？
l*a
26 楼
第一个要计数，
如果只有一个，这一块全跳过,start=end+1;重新开始
如果有多个，start++,直到最后一个 query array的第一项，然后跳过。
每次碰上乱序，也跳过
【在 p*****2 的大作中提到】
:
: 那你说说滑动窗口吧。找到之后怎么继续处理？
如果只有一个，这一块全跳过,start=end+1;重新开始
如果有多个，start++,直到最后一个 query array的第一项，然后跳过。
每次碰上乱序，也跳过
【在 p*****2 的大作中提到】
:
: 那你说说滑动窗口吧。找到之后怎么继续处理？
p*2
27 楼
我好像给你讲过吧？你有没有test case，我做做试试
【在 w****x 的大作中提到】
:
: 这题怎么DP?
w*x
28 楼
没test case，你先丢一个上来
【在 p*****2 的大作中提到】
:
: 我好像给你讲过吧？你有没有test case，我做做试试
b*n
29 楼
直接去OJ做啊
l*a
30 楼
你这个是query array有三个元素的例子吧
为什么 5，6，7不是呢？
【在 w****x 的大作中提到】
:
: 没test case，你先丢一个上来
为什么 5，6，7不是呢？
【在 w****x 的大作中提到】
:
: 没test case，你先丢一个上来
w*x
31 楼
因为我看走眼了 :P
【在 l*****a 的大作中提到】
: 你这个是query array有三个元素的例子吧
: 为什么 5，6，7不是呢？
l*a
32 楼
而且你这个多用了空间
时间上也没节省
没看出来比slide windows有什么优点啊，虽然解题思想很好
【在 w****x 的大作中提到】
:
: 因为我看走眼了 :P
时间上也没节省
没看出来比slide windows有什么优点啊，虽然解题思想很好
【在 w****x 的大作中提到】
:
: 因为我看走眼了 :P
s*1
33 楼
这题和leetcode上的Minimum Windwo Substring 差不多额，是吗？
p*2
34 楼
复杂度O(n)吗？
【在 l*****a 的大作中提到】
: 第一个要计数，
: 如果只有一个，这一块全跳过,start=end+1;重新开始
: 如果有多个，start++,直到最后一个 query array的第一项，然后跳过。
: 每次碰上乱序，也跳过
s*1
35 楼
amortized的情况下，是O(N)吧
l*a
36 楼
两个指针一起向前走，为什么还要amortized
【在 s*****1 的大作中提到】
: amortized的情况下，是O(N)吧
【在 s*****1 的大作中提到】
: amortized的情况下，是O(N)吧
w*x
37 楼
不懂，按顺序怎么滑动？
上个代码吧
【在 l*****a 的大作中提到】
: 第一个要计数，
: 如果只有一个，这一块全跳过,start=end+1;重新开始
: 如果有多个，start++,直到最后一个 query array的第一项，然后跳过。
: 每次碰上乱序，也跳过
l*a
38 楼
就是找到了第i个，旧可以继续向前找第i/i+1个，如果i到了array.size说明找到了
如果找到了地i个的时候，出现了第i+1或以后的，整个这段作废
start=end+1再开始
【在 w****x 的大作中提到】
:
: 不懂，按顺序怎么滑动？
: 上个代码吧
如果找到了地i个的时候，出现了第i+1或以后的，整个这段作废
start=end+1再开始
【在 w****x 的大作中提到】
:
: 不懂，按顺序怎么滑动？
: 上个代码吧
l*a
39 楼
HashMap 存query array value,query array index
然后每次循环初始currentIndex=-1;意思是准备先找query array的第0个
if(!map.containsKey(input[index])) {end++;}
if(map.containsKey(input[index]) {
if(map.get(input[index])==currentIndex）{end++;}
else if (map.get(input[index])==currentIndex+1){end++; currentIndex++;}
else {break;}
}
找到currentIndex==Query array size 算是找到一组
###第一个的出现次数还得计数。。
【在 w****x 的大作中提到】
:
: 不懂，按顺序怎么滑动？
: 上个代码吧
然后每次循环初始currentIndex=-1;意思是准备先找query array的第0个
if(!map.containsKey(input[index])) {end++;}
if(map.containsKey(input[index]) {
if(map.get(input[index])==currentIndex）{end++;}
else if (map.get(input[index])==currentIndex+1){end++; currentIndex++;}
else {break;}
}
找到currentIndex==Query array size 算是找到一组
###第一个的出现次数还得计数。。
【在 w****x 的大作中提到】
:
: 不懂，按顺序怎么滑动？
: 上个代码吧
p*2
40 楼
他已经给了代码了
【在 w****x 的大作中提到】
:
: 不懂，按顺序怎么滑动？
: 上个代码吧
w*x
41 楼
逻辑好复杂
时间复杂度是O(n^2)感觉
【在 l*****a 的大作中提到】
: 第一个要计数，
: 如果只有一个，这一块全跳过,start=end+1;重新开始
: 如果有多个，start++,直到最后一个 query array的第一项，然后跳过。
: 每次碰上乱序，也跳过
p*2
42 楼
void minWindows(int[] S, int[] T)
{
int m=S.length;
int n=T.length;
int[][] dp=new int[m+1][n+1];
int minindex=-1;
for(int i=0;i<=m;i++)
{
Arrays.fill(dp[i], -1);
dp[i][n]=0;
}
for(int i=m-1;i>=0;i--)
{
for(int j=n-1;j>=Math.max(0, n-(m-i));j--)
if(S[i]==T[j] && dp[i+1][j+1]>=0)
dp[i][j]=dp[i+1][j+1]+1;
else if(dp[i+1][j]>=0)
dp[i][j]=dp[i+1][j]+1;
if(dp[i][0]>=0 && (minindex==-1 || dp[i][0]
}
if(minindex>=0)
{
System.out.println("start:"+minindex);
System.out.println("len:"+dp[minindex][0]);
}
}
{
int m=S.length;
int n=T.length;
int[][] dp=new int[m+1][n+1];
int minindex=-1;
for(int i=0;i<=m;i++)
{
Arrays.fill(dp[i], -1);
dp[i][n]=0;
}
for(int i=m-1;i>=0;i--)
{
for(int j=n-1;j>=Math.max(0, n-(m-i));j--)
if(S[i]==T[j] && dp[i+1][j+1]>=0)
dp[i][j]=dp[i+1][j+1]+1;
else if(dp[i+1][j]>=0)
dp[i][j]=dp[i+1][j]+1;
if(dp[i][0]>=0 && (minindex==-1 || dp[i][0]
}
if(minindex>=0)
{
System.out.println("start:"+minindex);
System.out.println("len:"+dp[minindex][0]);
}
}
l*a
43 楼
我明明每次start,end一起向前走，你非说O(n2)
无语了
【在 w****x 的大作中提到】
:
: 逻辑好复杂
: 时间复杂度是O(n^2)感觉
无语了
【在 w****x 的大作中提到】
:
: 逻辑好复杂
: 时间复杂度是O(n^2)感觉
p*2
44 楼
真没看明白，能不能举个例子？这题如果能O(n)还是挺牛逼的。
【在 l*****a 的大作中提到】
: 就是找到了第i个，旧可以继续向前找第i/i+1个，如果i到了array.size说明找到了
: 如果找到了地i个的时候，出现了第i+1或以后的，整个这段作废
: start=end+1再开始
l*a
45 楼
query array [A,B,C,D]
a b c A B D D a b c A b A d d B C D
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
start=0; end=start;
a not in query array ,OK end++
b end++
c end++
A first one in query array,OK end++
B met 1st before, now 2nd ,OK end++
D met 2nd before, now 4th,wrong
so [0,5] is illegal,we have to start from 6.
D in current slide windows, we met the 4th of query array, illegal
skip
start=7;end=start;
a not in query array ,OK end++
b end++
c end++
A first one in query array,OK end++
b end++
A met 1st before, now still 1st ,OK end++
d end++
d end++
B met 1st before, now 2nd ,OK end++
C met 2nd before, now 3rd ,OK end++
D met 3rd before, now 4th,ok, end++
since we meet the final one of query array,
we know we got the result as what we want.
7->17
since there is more A in this windows, we can move start until the end of
1st, so 12-17 will be the shortest in this part.
then start=end++;end=start;判断下一段
简单说，对有序用一个index判断。
index=-1
if current is Query[index] or Query[index+1]
都是有序，否则就是illegal的
【在 p*****2 的大作中提到】
:
: 真没看明白，能不能举个例子？这题如果能O(n)还是挺牛逼的。
a b c A B D D a b c A b A d d B C D
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
start=0; end=start;
a not in query array ,OK end++
b end++
c end++
A first one in query array,OK end++
B met 1st before, now 2nd ,OK end++
D met 2nd before, now 4th,wrong
so [0,5] is illegal,we have to start from 6.
D in current slide windows, we met the 4th of query array, illegal
skip
start=7;end=start;
a not in query array ,OK end++
b end++
c end++
A first one in query array,OK end++
b end++
A met 1st before, now still 1st ,OK end++
d end++
d end++
B met 1st before, now 2nd ,OK end++
C met 2nd before, now 3rd ,OK end++
D met 3rd before, now 4th,ok, end++
since we meet the final one of query array,
we know we got the result as what we want.
7->17
since there is more A in this windows, we can move start until the end of
1st, so 12-17 will be the shortest in this part.
then start=end++;end=start;判断下一段
简单说，对有序用一个index判断。
index=-1
if current is Query[index] or Query[index+1]
都是有序，否则就是illegal的
【在 p*****2 的大作中提到】
:
: 真没看明白，能不能举个例子？这题如果能O(n)还是挺牛逼的。
p*2
46 楼
感觉这个有问题
D met 2nd before, now 4th,wrong
so [0,5] is illegal,we have to start from 6.
【在 l*****a 的大作中提到】
: query array [A,B,C,D]
: a b c A B D D a b c A b A d d B C D
: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
: start=0; end=start;
: a not in query array ,OK end++
: b end++
: c end++
: A first one in query array,OK end++
: B met 1st before, now 2nd ,OK end++
: D met 2nd before, now 4th,wrong
l*a
47 楼
why?ABD乱序，肯定要淘汰啊
丢掉了什么？
注意每次match 到query array的相应项目，index++
【在 p*****2 的大作中提到】
:
: 感觉这个有问题
: D met 2nd before, now 4th,wrong
: so [0,5] is illegal,we have to start from 6.
丢掉了什么？
注意每次match 到query array的相应项目，index++
【在 p*****2 的大作中提到】
:
: 感觉这个有问题
: D met 2nd before, now 4th,wrong
: so [0,5] is illegal,we have to start from 6.
w*x
48 楼
逻辑太复杂了，怎么想出来的，放弃了
【在 l*****a 的大作中提到】
: why?ABD乱序，肯定要淘汰啊
: 丢掉了什么？
: 注意每次match 到query array的相应项目，index++
l*a
49 楼
我哭了，明明就是slide windows
那你slide windows怎么做？那题是包含所有query array的item
现在就多了一个有序吗，用index判断一下就好了
【在 w****x 的大作中提到】
:
: 逻辑太复杂了，怎么想出来的，放弃了
那你slide windows怎么做？那题是包含所有query array的item
现在就多了一个有序吗，用index判断一下就好了
【在 w****x 的大作中提到】
:
: 逻辑太复杂了，怎么想出来的，放弃了
p*2
50 楼
题目有歧义。我的理解是
ABDCD是有效的。如果算无效的，slide window确实可以。
【在 l*****a 的大作中提到】
: 我哭了，明明就是slide windows
: 那你slide windows怎么做？那题是包含所有query array的item
: 现在就多了一个有序吗，用index判断一下就好了
w*x
51 楼
ABDCD 当然有效
【在 p*****2 的大作中提到】
:
: 题目有歧义。我的理解是
: ABDCD是有效的。如果算无效的，slide window确实可以。
l*a
52 楼
contains all the elements of query array and also in the same order
如果这个叫 in the same order
那什么叫 not in the same order呢？
【在 w****x 的大作中提到】
:
: ABDCD 当然有效
如果这个叫 in the same order
那什么叫 not in the same order呢？
【在 w****x 的大作中提到】
:
: ABDCD 当然有效
w*x
53 楼
只要有sub sequence in the same order就算
【在 l*****a 的大作中提到】
: contains all the elements of query array and also in the same order
: 如果这个叫 in the same order
: 那什么叫 not in the same order呢？
p*2
54 楼
d*g
55 楼
想到这个计算DP的公式还真不太容易~~感觉主要是dp[i][j]表示什么含义这个比较难想
，把它想明白之后公式就比较好想出来了~
【在 p*****2 的大作中提到】
: 我放到我的博客里了。
: http://blog.sina.com.cn/s/blog_b9285de20101h6jx.html
M*n
56 楼
这道题最简单的思想是build一个状态机吧
相关阅读
如何O(1)复杂度比较两个Hashmap相等Re: 其实各行业都有聪明人，数学物理傻子多了去了 (转载)怎麽搞， Vim， Emacs，還是？【北美职业论坛视频】雇主不能再问你过往薪水Re: 码农的最大福利 (转载)Word ladder 2这种题目很吃力Foursquare这公司还有可能翻身吗？现在弯曲装逼的公司越来越多了蚂蚁金服内推，国内职位！求明尼苏达ee专业内推DoorDash这公司现状如何？LinkedIn 是默剧吗请问码农onsite穿西装吗每天一发 我们的目标是用刷题绑架所有公司的面试厂花这词儿谁他妈发明的新雇主要求签字拿到receipt才能辞职，请问该怎么办？先不秀包裹了，来秀一下refresh【工作机会】 Software and Electronics Engineer每天一发 我们的目标是用刷题绑架所有公司的面试有为了Sign on bonus一年换一个公司的吗？