w****x 发帖数: 2483 | 1 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 |
p*****2 发帖数: 21240 | 2
什么复杂度要求,感觉就是一道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*****a 发帖数: 14598 | 3 为什么不是两指针
为什么不是slide window
就是slide windows然后要求有序吧
【在 p*****2 的大作中提到】 : : 什么复杂度要求,感觉就是一道DP吧。
|
p*****2 发帖数: 21240 | 4
没序就是two pointer 和 sliding window了。
有序你怎么搞?
【在 l*****a 的大作中提到】 : 为什么不是两指针 : 为什么不是slide window : 就是slide windows然后要求有序吧
|
w****x 发帖数: 2483 | 5
这题DP??我怎么感觉是reverse indexing?
【在 p*****2 的大作中提到】 : : 没序就是two pointer 和 sliding window了。 : 有序你怎么搞?
|
l*****a 发帖数: 14598 | 6 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了。 : 有序你怎么搞?
|
p*****2 发帖数: 21240 | 7
你的算法是啥样的?
【在 w****x 的大作中提到】 : : 这题DP??我怎么感觉是reverse indexing?
|
w****x 发帖数: 2483 | 8
短的在长的那个做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 的大作中提到】 : : 你的算法是啥样的?
|
p*****2 发帖数: 21240 | 9
这个可行,不过太麻烦了。为什么不用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*****2 发帖数: 21240 | 10
能不能说说算法呢?发现我现在java太弱了。
【在 l*****a 的大作中提到】 : 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 算是找到一组 : ###第一个的出现次数还得计数。。
|
|
|
b*****n 发帖数: 482 | 11 这题跟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
|
l*****a 发帖数: 14598 | 12 我就会滑动窗口的算法啊,dp/reverse index都不会
【在 p*****2 的大作中提到】 : : 能不能说说算法呢?发现我现在java太弱了。
|
p*****2 发帖数: 21240 | 13
那你说说滑动窗口吧。找到之后怎么继续处理?
【在 l*****a 的大作中提到】 : 我就会滑动窗口的算法啊,dp/reverse index都不会
|
w****x 发帖数: 2483 | 14
这题怎么DP?
【在 p*****2 的大作中提到】 : : 那你说说滑动窗口吧。找到之后怎么继续处理?
|
l*****a 发帖数: 14598 | 15 第一个要计数,
如果只有一个,这一块全跳过,start=end+1;重新开始
如果有多个,start++,直到最后一个 query array的第一项,然后跳过。
每次碰上乱序,也跳过
【在 p*****2 的大作中提到】 : : 那你说说滑动窗口吧。找到之后怎么继续处理?
|
p*****2 发帖数: 21240 | 16
我好像给你讲过吧?你有没有test case,我做做试试
【在 w****x 的大作中提到】 : : 这题怎么DP?
|
w****x 发帖数: 2483 | 17
没test case,你先丢一个上来
【在 p*****2 的大作中提到】 : : 我好像给你讲过吧?你有没有test case,我做做试试
|
b*****n 发帖数: 482 | |
l*****a 发帖数: 14598 | 19 你这个是query array有三个元素的例子吧
为什么 5,6,7不是呢?
【在 w****x 的大作中提到】 : : 没test case,你先丢一个上来
|
w****x 发帖数: 2483 | 20
因为我看走眼了 :P
【在 l*****a 的大作中提到】 : 你这个是query array有三个元素的例子吧 : 为什么 5,6,7不是呢?
|
|
|
l*****a 发帖数: 14598 | 21 而且你这个多用了空间
时间上也没节省
没看出来比slide windows有什么优点啊,虽然解题思想很好
【在 w****x 的大作中提到】 : : 因为我看走眼了 :P
|
s*****1 发帖数: 134 | 22 这题和leetcode上的Minimum Windwo Substring 差不多额,是吗? |
p*****2 发帖数: 21240 | 23
复杂度O(n)吗?
【在 l*****a 的大作中提到】 : 第一个要计数, : 如果只有一个,这一块全跳过,start=end+1;重新开始 : 如果有多个,start++,直到最后一个 query array的第一项,然后跳过。 : 每次碰上乱序,也跳过
|
s*****1 发帖数: 134 | |
l*****a 发帖数: 14598 | 25 两个指针一起向前走,为什么还要amortized
【在 s*****1 的大作中提到】 : amortized的情况下,是O(N)吧
|
w****x 发帖数: 2483 | 26
不懂,按顺序怎么滑动?
上个代码吧
【在 l*****a 的大作中提到】 : 第一个要计数, : 如果只有一个,这一块全跳过,start=end+1;重新开始 : 如果有多个,start++,直到最后一个 query array的第一项,然后跳过。 : 每次碰上乱序,也跳过
|
l*****a 发帖数: 14598 | 27 就是找到了第i个,旧可以继续向前找第i/i+1个,如果i到了array.size说明找到了
如果找到了地i个的时候,出现了第i+1或以后的,整个这段作废
start=end+1再开始
【在 w****x 的大作中提到】 : : 不懂,按顺序怎么滑动? : 上个代码吧
|
l*****a 发帖数: 14598 | 28 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 的大作中提到】 : : 不懂,按顺序怎么滑动? : 上个代码吧
|
p*****2 发帖数: 21240 | 29
他已经给了代码了
【在 w****x 的大作中提到】 : : 不懂,按顺序怎么滑动? : 上个代码吧
|
w****x 发帖数: 2483 | 30
逻辑好复杂
时间复杂度是O(n^2)感觉
【在 l*****a 的大作中提到】 : 第一个要计数, : 如果只有一个,这一块全跳过,start=end+1;重新开始 : 如果有多个,start++,直到最后一个 query array的第一项,然后跳过。 : 每次碰上乱序,也跳过
|
|
|
p*****2 发帖数: 21240 | 31 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]);
}
} |
l*****a 发帖数: 14598 | 32 我明明每次start,end一起向前走,你非说O(n2)
无语了
【在 w****x 的大作中提到】 : : 逻辑好复杂 : 时间复杂度是O(n^2)感觉
|
p*****2 发帖数: 21240 | 33
真没看明白,能不能举个例子?这题如果能O(n)还是挺牛逼的。
【在 l*****a 的大作中提到】 : 就是找到了第i个,旧可以继续向前找第i/i+1个,如果i到了array.size说明找到了 : 如果找到了地i个的时候,出现了第i+1或以后的,整个这段作废 : start=end+1再开始
|
l*****a 发帖数: 14598 | 34 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)还是挺牛逼的。
|
p*****2 发帖数: 21240 | 35
感觉这个有问题
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 发帖数: 14598 | 36 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.
|
w****x 发帖数: 2483 | 37
逻辑太复杂了,怎么想出来的,放弃了
【在 l*****a 的大作中提到】 : why?ABD乱序,肯定要淘汰啊 : 丢掉了什么? : 注意每次match 到query array的相应项目,index++
|
l*****a 发帖数: 14598 | 38 我哭了,明明就是slide windows
那你slide windows怎么做?那题是包含所有query array的item
现在就多了一个有序吗,用index判断一下就好了
【在 w****x 的大作中提到】 : : 逻辑太复杂了,怎么想出来的,放弃了
|
p*****2 发帖数: 21240 | 39
题目有歧义。我的理解是
ABDCD是有效的。如果算无效的,slide window确实可以。
【在 l*****a 的大作中提到】 : 我哭了,明明就是slide windows : 那你slide windows怎么做?那题是包含所有query array的item : 现在就多了一个有序吗,用index判断一下就好了
|
w****x 发帖数: 2483 | 40
ABDCD 当然有效
【在 p*****2 的大作中提到】 : : 题目有歧义。我的理解是 : ABDCD是有效的。如果算无效的,slide window确实可以。
|
|
|
l*****a 发帖数: 14598 | 41 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 当然有效
|
w****x 发帖数: 2483 | 42
只要有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 发帖数: 21240 | |
d*********g 发帖数: 154 | 44
想到这个计算DP的公式还真不太容易~~感觉主要是dp[i][j]表示什么含义这个比较难想
,把它想明白之后公式就比较好想出来了~
【在 p*****2 的大作中提到】 : 我放到我的博客里了。 : http://blog.sina.com.cn/s/blog_b9285de20101h6jx.html
|
M*********n 发帖数: 4839 | |