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 楼
是随机抽的。
L*1
5 楼
我收到第3个fb 的时候给我的
b*8
7 楼
我买了10000$以上,他给了。。。
J*S
9 楼
想起来了,我过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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
:
: 没序就是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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
:
: 没序就是two pointer 和 sliding window了。
: 有序你怎么搞?
l*r
13 楼
ebay真是一团糟啊.
P*r
19 楼
据说是随机的。。碰运气
p*2
20 楼
能不能说说算法呢?发现我现在java太弱了。
【在 l*****a 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 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
29 楼
直接去OJ做啊
s*1
33 楼
这题和leetcode上的Minimum Windwo Substring 差不多额,是吗?
s*1
35 楼
amortized的情况下,是O(N)吧
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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
:
: 不懂,按顺序怎么滑动?
: 上个代码吧
然后每次循环初始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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
:
: 不懂,按顺序怎么滑动?
: 上个代码吧
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] minindex=i;
}
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
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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
:
: 真没看明白,能不能举个例子?这题如果能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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
:
: 真没看明白,能不能举个例子?这题如果能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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 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
p*2
54 楼
d*g
55 楼
想到这个计算DP的公式还真不太容易~~感觉主要是dp[i][j]表示什么含义这个比较难想
,把它想明白之后公式就比较好想出来了~
【在 p*****2 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 我放到我的博客里了。
: http://blog.sina.com.cn/s/blog_b9285de20101h6jx.html
M*n
56 楼
这道题最简单的思想是build一个状态机吧
相关阅读
老公去Uber onsite的expense不给报销,求助谷歌电面面筋,不知道会不会挂,忐忑哥替老婆的offer求个blessAdv H1B non PP CSCH1B pending, OPT还没过期,应该怎么换工作请问,骑驴找马的时候,怎样才能不让现在公司知道自己在找工作?泡沫要灭了?我在国内金鸡湖散步时新鲜G onsite 面经如何杀shopshop的浏览器pop-up ads, 买什么除adware软件? (转载)H1b ext REF可以这样绕开H1B,依靠L1直接搞绿卡么刚听小印同事说拿到多个包裹不拒绝至转行同学: 免费课程邀请你来上, 6/17开始, 限前10名 (转载 (转载)请问倒过来的OPT能批准吗?求助!关于ICC 的问题!求助,有没有人知道德国和瑞士的google咋面试的?大家如何看待wealthfront前景 (转载)请教一个问题 (facebook面试后)狗家 题 讨论