logo
Redian新闻
>未名空间
>PDA - 掌中宝
>
gtalk现在怎么必须用WIFI才能视频了？
avatar
gtalk现在怎么必须用WIFI才能视频了？# PDA - 掌中宝
B*1
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.
如果不要求保持order，ihas1337上面有解法，如果要保持order，怎么做才最好呢。
是不是最好应该是O(n)呢？
avatar
c*g
2 楼
公司有个小印，H1B第五年了，还没开始办140。他老板是老印，把小印当畜生使，加班
是常事，有时加班到午夜。小印郁闷透顶，又不敢跳。因为现在找个收H1B的也不容易
。
avatar
z*r
3 楼
这不历史倒退吗？俺LTE的信号，速度比大多数人家里的HSI都快，这个限制真是无语。
avatar
d*d
4 楼
看上去像string match了.

of

【在 B*******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.
: 如果不要求保持order，ihas1337上面有解法，如果要保持order，怎么做才最好呢。
: 是不是最好应该是O(n)呢？
avatar
n*r
5 楼
烙印内部也分阶层的
avatar
B*1
7 楼
大牛，但是这个src string里面的sub string可以不连续的，怎么做string match 呢
？
avatar
s*d
8 楼
我们公司的小印，H1B第四年，公司早就同意帮他办绿卡（自己掏钱），他嫌贵嫌队排
的太长，不愿意办，这两天跟我说可靠消息欧巴的移民法马上要通过了，半年就能拿绿
卡，不用公司办，自己办就行了。

【在 c*****g 的大作中提到】
: 公司有个小印，H1B第五年了，还没开始办140。他老板是老印，把小印当畜生使，加班
: 是常事，有时加班到午夜。小印郁闷透顶，又不敢跳。因为现在找个收H1B的也不容易
: 。
avatar
d*d
10 楼
不是的skip掉,这里面还有问题,我再想想.
avatar
c*g
11 楼
哈哈。140都没办，半年拿绿卡？
欧巴吗连他自己的医改都顾不及，呵呵。
avatar
p*c
12 楼
tango我觉得最好用
avatar
B*1
13 楼
我也这么想的，但是这样子要另外locate一个array去纪录 skip掉的字符数。
avatar
l*i
14 楼
烙印强奸的大都是自己人

【在 c*****g 的大作中提到】
: 公司有个小印，H1B第五年了，还没开始办140。他老板是老印，把小印当畜生使，加班
: 是常事，有时加班到午夜。小印郁闷透顶，又不敢跳。因为现在找个收H1B的也不容易
: 。
avatar
z*r
15 楼
不太流行啊，gtalk的视频质量不错，在俺这里大部分情况下比skype要好

【在 p***c 的大作中提到】
: tango我觉得最好用
avatar
g*g
17 楼
which carrier

【在 z**r 的大作中提到】
: 这不历史倒退吗？俺LTE的信号，速度比大多数人家里的HSI都快，这个限制真是无语。
avatar
d*d
18 楼
ok,我想出来了,和那个不用顺序相同的方法类似,大概O(n)可以搞定.
等我有空了来写code.

of

【在 B*******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.
: 如果不要求保持order，ihas1337上面有解法，如果要保持order，怎么做才最好呢。
: 是不是最好应该是O(n)呢？
avatar
m*r
19 楼
Verizon上还可以LTE视频
avatar
b*y
20 楼

of
1337上面是哪题? 找不到，能否给个链接？

【在 B*******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.
: 如果不要求保持order，ihas1337上面有解法，如果要保持order，怎么做才最好呢。
: 是不是最好应该是O(n)呢？
avatar
B*1
22 楼
牛人，你的code写好了吗？

【在 d*******d 的大作中提到】
: ok,我想出来了,和那个不用顺序相同的方法类似,大概O(n)可以搞定.
: 等我有空了来写code.
:
: of
avatar
k*n
23 楼
like the merging of posting lists in IR
build invert index of the integers
let the shortest posting list length be m
can be done in m*(k-1)logn
practically will usually be much faster, I think...

of

【在 B*******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.
: 如果不要求保持order，ihas1337上面有解法，如果要保持order，怎么做才最好呢。
: 是不是最好应该是O(n)呢？
avatar
k*n
24 楼

actually, we will traverse all the posting list at most once,
so it's O(n)
like this:
record all the occurrence positions in the longer array in the following
posting list
a[0]: 1 5 7 8 13 19
a[1]: 2 9 20
a[2]: 13 15 17
...
keep a cursor in each posting list.
firstly locate the 1st ordered positions
then move the a[0] cursor forward and check if there is need to update.
the number of updates is at most sum of all posting lists lenghts
the number of checks is complicated, but seems also O(n)

【在 k****n 的大作中提到】
: like the merging of posting lists in IR
: build invert index of the integers
: let the shortest posting list length be m
: can be done in m*(k-1)logn
: practically will usually be much faster, I think...
:
: of
avatar
B*1
25 楼
请问这个
a[0]: 1 5 7 8 13 19
a[1]: 2 9 20
a[2]: 13 15 17
怎么来的？
avatar
k*n
26 楼
preprocess the array once, append the position of the occurrence for each a[
i] to a list
visit long array once, append at most once, should be O(n)

【在 B*******1 的大作中提到】
: 请问这个
: a[0]: 1 5 7 8 13 19
: a[1]: 2 9 20
: a[2]: 13 15 17
: 怎么来的？
avatar
t*n
27 楼
bool
minWindowOrder(const char *S, const char *T,
int &minWindowBegin, int &minWindowEnd)
{
int sLen = strlen(S);
int tLen = strlen(T);
int minWindowLen = INT_MAX;
for (int i = 0; i <= sLen - tLen; i++) {
if (S[i] == T[0]) {
//greed now
int k = i;
int j = 1;
k ++;
while (k < sLen && j < tLen) {
if (S[k] == T[j]) {
j ++;
}
k ++;
}
if (j == tLen) {
int windowLen = j - i - 1;
if (windowLen < minWindowLen) {
minWindowLen = windowLen;
minWindowBegin = i;
minWindowEnd = k - 1;
}
}
}
}
return (minWindowLen != INT_MAX) ? true : false;
}
avatar
m*q
28 楼
Mark. 从最短的list查找的思路很不错，k个list，最短list的
最大长度是O(n/k),对于最短list中的每个元素同时在k-1个list中
查找相邻的元素，总时间应该可以保证O(n)
我开始是想从最后一个list开始找，这样假如最后一个list很长
(e.g. n/2)，总的复杂度就是O(kn)了
PS. 这个方法也可以用于短的字符串中有重复字符的情况
e.g. aabcbd

【在 k****n 的大作中提到】
: preprocess the array once, append the position of the occurrence for each a[
: i] to a list
: visit long array once, append at most once, should be O(n)
avatar
m*q
29 楼
这个ms最坏是O(n^2)啊

【在 t*****n 的大作中提到】
: bool
: minWindowOrder(const char *S, const char *T,
: int &minWindowBegin, int &minWindowEnd)
: {
: int sLen = strlen(S);
: int tLen = strlen(T);
: int minWindowLen = INT_MAX;
: for (int i = 0; i <= sLen - tLen; i++) {
: if (S[i] == T[0]) {
: //greed now
avatar
g*y
30 楼
有重复的时候还是O(n)吗？比如，"aaaabaaaac", 找"aaaac", 生成的数组：
a[0]: 0 1 2 3 5 6 7 8
a[1] = a[2] = a[3] = a[5] = a[6] = a[7] = a[8] = a[0]
a[4] = 4
a[9] = 9
总数是n^2级的。

【在 k****n 的大作中提到】
: preprocess the array once, append the position of the occurrence for each a[
: i] to a list
: visit long array once, append at most once, should be O(n)
avatar
m*q
31 楼
你举的例子也没问题啊
'a' -> a[0]: 0 1 2 3 5 6 7 8
'c' -> a[1]: 9
需要找4个a，一个c
a[1]比a[0]短，于是从a[1]开始，只有一个index 9，然后
从后往前扫描a[0],可以发现最短的是 5 6 7 8 9,复杂度
O(n)

【在 g**********y 的大作中提到】
: 有重复的时候还是O(n)吗？比如，"aaaabaaaac", 找"aaaac", 生成的数组：
: a[0]: 0 1 2 3 5 6 7 8
: a[1] = a[2] = a[3] = a[5] = a[6] = a[7] = a[8] = a[0]
: a[4] = 4
: a[9] = 9
: 总数是n^2级的。
avatar
d*l
32 楼
你这样似乎是对于相等的a[i]共用同一个list，否则产生list的过程就不止O(n)。另外
由于这题要求的是最小的那个窗口，我觉得还是很难做到O(n)。比如最直接的例子，
aaaaaaaaaa和aaaaa，a[0]的list长度为10，有5个指针同时指在这个list上，在它们都
走到list末尾之前，我们并不能确定我们找到的是最小窗口，所以还是需要O(kn)吧

【在 m**q 的大作中提到】
: 你举的例子也没问题啊
: 'a' -> a[0]: 0 1 2 3 5 6 7 8
: 'c' -> a[1]: 9
: 需要找4个a，一个c
: a[1]比a[0]短，于是从a[1]开始，只有一个index 9，然后
: 从后往前扫描a[0],可以发现最短的是 5 6 7 8 9,复杂度
: O(n)
avatar
m*q
33 楼

是的，是每个唯一的字符有一个list
另外
这种情况只有一个list啊，因为只有字符a

【在 d*******l 的大作中提到】
: 你这样似乎是对于相等的a[i]共用同一个list，否则产生list的过程就不止O(n)。另外
: 由于这题要求的是最小的那个窗口，我觉得还是很难做到O(n)。比如最直接的例子，
: aaaaaaaaaa和aaaaa，a[0]的list长度为10，有5个指针同时指在这个list上，在它们都
: 走到list末尾之前，我们并不能确定我们找到的是最小窗口，所以还是需要O(kn)吧
avatar
d*l
34 楼
是只有一个list，不过有k个指针指向它。k个指针都得移到末尾算法才能终止吧。在穷
尽所有情况前无法判断当前找到的是不是最优解吧

【在 m**q 的大作中提到】
:
: 是的，是每个唯一的字符有一个list
: 另外
: 这种情况只有一个list啊，因为只有字符a
avatar
m*q
35 楼
我的想法是这样的，这个list是对应每个字符的，所以如果只考虑a~z，
就相当于有一个长为26的数组，每个数组元素是一个list head （list可以是空），分
别对应a~z的字符，每个list记录对应字符在原串里出现的位置序列
我原来举的例子有问题，下面这个应该是对的
比如，"aaaadaaaac", 找"aaaac",
生成的position数组
p[0]: 0 1 2 3 5 6 7 8 (a)
p[1]: NULL (b)
p[2]: 9 (c)
p[3]: NULL (d) d在pattern里不存在
p[4]: NULL (e)
......
p[25]: NULL (z)
只有a和c对应的list非空，因为c对应的list短，所以先在
pattern里面找到c，因为c是pattern的最后一个字符，前一个
字符是a，所以在p[0]里面从后向前找第一个小于 9的值，
是8；然后pattern中前面一个字符还是a，继续找p[0]中的
前一个值，。。。直到pattern中的四个a都被匹配上，找到
的postion序列为 5 6 7 8 9
然后，继续看p[2]中前一个值，重新匹配pattern，因为p[2]
只包含一项，至此所有匹配结束
---
你的例子中， aaaaaaaaaa找aaaaa
只有p[0]: 0 1 2 3 4 5 6 7 8 9
如果只需要找一个最短的，那么找到5 6 7 8 9后判断一下长度
9 - 5 + 1 = 5 和pattern的长度相等，就知道已经找到最短的，
不需要再找了。如果是找所有最短的，那确实像你说的，最坏是O(mn)

【在 d*******l 的大作中提到】
: 是只有一个list，不过有k个指针指向它。k个指针都得移到末尾算法才能终止吧。在穷
: 尽所有情况前无法判断当前找到的是不是最优解吧
avatar
d*l
36 楼
算法正确性应该没问题，就是我觉得复杂度最坏还是kn。我举的例子比较朴素，你可以
通过判断当前window size等于pattern长度来知道已经最优了。对于更复杂些的情形，
在穷尽所有可能之前是无法确定最优的吧。

【在 m**q 的大作中提到】
: 我的想法是这样的，这个list是对应每个字符的，所以如果只考虑a~z，
: 就相当于有一个长为26的数组，每个数组元素是一个list head （list可以是空），分
: 别对应a~z的字符，每个list记录对应字符在原串里出现的位置序列
: 我原来举的例子有问题，下面这个应该是对的
: 比如，"aaaadaaaac", 找"aaaac",
: 生成的position数组
: p[0]: 0 1 2 3 5 6 7 8 (a)
: p[1]: NULL (b)
: p[2]: 9 (c)
: p[3]: NULL (d) d在pattern里不存在
avatar
e*l
37 楼
不管什么情况都可以是O(n)，只需要证明所有的指针移动的总次数是n1，这里n1<=n是
所有目标字符在原字符串里出现的次数之和。
首先是不重复字符的情况，即使是从最长的（比如n/2）的list开始找，其他的指针移
动的总次数也最多是n1-n/2。因为这个list是有序的，查找最"紧"的窗口的时候，指针
只需要顺着上一次的位置向后走（或者选择不走）。
短串里面有重复字符的情况复杂一点，但是可以"轮换"使用重复字符对应的指针，使得
总移动次数还是n1。例子：
短串是aab，在长串中出现的位置list是
a1=1,2,3,8,9
a2=1,2,3,8,9
b=6,10，
总次数n1=7，但是一般的做法要遍历a1和a2，一共12次。怎么减小到7次呢？
找到一个合适的a1,a2和b之后，让a1和a2轮换，a1指向直接从原a2的下一位开始找，跳
过了重复的指针移动。这样总移动次数可以保证还是n1。
avatar
e*l
38 楼
更清楚一点，以a1的不同位置为起点查找所有可能的window
正常做法：
1. (a1,a2,b)选择(1,2,6)，
2. (a1,a2,b)选择(2,3,6)，共移动共2步
3. (a1,a2,b)选择(3,8,10)，共移动共3步
4. (a1,a2,b)选择(8,9,10)，共移动共2步
避免重复移动的做法：
1. (a1,a2,b)选择(1,2,6)，
2. (a1,a2,b)选择(3,2,6)，移动1步，a1直接从2以后找，a2成为首匹配
3. (a1,a2,b)选择(3,8,10)，移动共2步，a2直接从3往后找，a1成为首匹配
4. (a1,a2,b)选择(9,8,10)，移动1步,a1直接从8以后找，a2成为首匹配
如此可保证总移动次数<=n。
多个重复字符的类似，每次shift这些同样字符的指针，只移动最后一个匹配。
avatar
d*l
39 楼
可能是可行的，不过算法过于精细的话，普遍性就差了，而且很难验证。如果短串是
ababbabbaabb之类的，我很难想象轮转之后如何维持和别的字母的相对顺序。我觉得大
多数情况下O(n)还有可能（虽然我认为最坏还是会kn），但严格小于等于n怎么也不太
可能吧。。

【在 e***l 的大作中提到】
: 更清楚一点，以a1的不同位置为起点查找所有可能的window
: 正常做法：
: 1. (a1,a2,b)选择(1,2,6)，
: 2. (a1,a2,b)选择(2,3,6)，共移动共2步
: 3. (a1,a2,b)选择(3,8,10)，共移动共3步
: 4. (a1,a2,b)选择(8,9,10)，共移动共2步
: 避免重复移动的做法：
: 1. (a1,a2,b)选择(1,2,6)，
: 2. (a1,a2,b)选择(3,2,6)，移动1步，a1直接从2以后找，a2成为首匹配
: 3. (a1,a2,b)选择(3,8,10)，移动共2步，a2直接从3往后找，a1成为首匹配
avatar
B*1
40 楼
很同意你的说法，我看了这么多帖子都晕倒了，不如哪位大牛上code吧，然后大家一起
纠bug，讨论。

【在 d*******l 的大作中提到】
: 可能是可行的，不过算法过于精细的话，普遍性就差了，而且很难验证。如果短串是
: ababbabbaabb之类的，我很难想象轮转之后如何维持和别的字母的相对顺序。我觉得大
: 多数情况下O(n)还有可能（虽然我认为最坏还是会kn），但严格小于等于n怎么也不太
: 可能吧。。
avatar
e*l
41 楼

间隔出现是有点问题，我再想想

【在 d*******l 的大作中提到】
: 可能是可行的，不过算法过于精细的话，普遍性就差了，而且很难验证。如果短串是
: ababbabbaabb之类的，我很难想象轮转之后如何维持和别的字母的相对顺序。我觉得大
: 多数情况下O(n)还有可能（虽然我认为最坏还是会kn），但严格小于等于n怎么也不太
: 可能吧。。
avatar
t*9
42 楼
用动态规划如何?
class FindMinWindow
{
private static readonly int[] A = { 1,1,1,1,2,1,1,1,1,3 };
private static readonly int[] Q = { 1,1,1,1,3 };

public static Point FindWindow(int startA, int startQ, bool
firstCall)
{
if (Q.Length <= startQ) return new Point(startA, 0);
if (A.Length <= startA) return new Point(startA, Int32.MaxValue);
List valueList = FindValue(startA, Q[startQ]);
if (valueList.Count == 0) return new Point(startA, Int32.
MaxValue);
int length = Int32.MaxValue;
int start = -1;
foreach (int valueIndex in valueList)
{
Point p = FindWindow(valueIndex + 1, startQ + 1, false);
if (!firstCall && p.Length != Int32.MaxValue) p.Length += (p
.Index - startA);
if (p.Length < length) {length = p.Length; start =
valueIndex; }
}
return new Point(start, length);
}
private static List FindValue(int startA, int value)
{
List list = new List();
for (int i = startA; i < A.Length; i++) { if (A[i] == value)
list.Add(i); }
return list;
}
static void Main(string[] args)
{
Point p = FindWindow(0, 0, true);
System.Console.WriteLine(string.Format("start {0}; length:{1}",
p.Index, p.Length));
}
}

【在 e***l 的大作中提到】
:
: 间隔出现是有点问题，我再想想
相关阅读
入手Note 8.0准备入一个ipad mini 4G去纠结:100刀的Nook HD还是200刀的Nook HD+？BBS宕机包子发给sector33 (陈友谅)同学Cisco也太看不起中国顾客了吧。。。。。thinkpad tablet 2 3/4G 版本为什么联想官网上没有呢外面逛了一圈, 发现SONY手机最好看.Galaxy S4的第一轮发布[推荐]android自带的browsernook hd+的deal又来了IRS高兴了也会翻翻你的email计算机不是金箍棒好吧？别等helix关心Z10的请看：黑莓Z10被指在美销售不佳退货多小小失望一下估计老邢用了锤子了升级4.1.2之后，觉得挺费电的N4可以带回国用吗？求教一个题目。。感觉Note 8.0挺好的
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。