请问现在H4签证的有效期是 1 年多次往返吗？# Immigration - 落地生根
j*2
1 楼
2分法是O(m*log(n))，
如果数组长度变化很大，可以先用O(n)把最小的选出来，总的复杂度就可以是O(n+min(
m)*log(n))。
如果n很大而m不大，就不要选min(m)。
大家觉得呢？
如果数组长度变化很大，可以先用O(n)把最小的选出来，总的复杂度就可以是O(n+min(
m)*log(n))。
如果n很大而m不大，就不要选min(m)。
大家觉得呢？
f*h
2 楼
现在H1 有效期是 1 年多次往返了，有人知道H4 也是吗？ 多谢！
h*n
3 楼
二分的复杂度也是O（n×m）吧
两两比较 N/2 + N/4 + N/8 + ...+ 1 = N
复杂度还是O（N×M）啊
你怎么个二分的
两两比较 N/2 + N/4 + N/8 + ...+ 1 = N
复杂度还是O（N×M）啊
你怎么个二分的
e*r
4 楼
去visa版问问？
【在 f********h 的大作中提到】
: 现在H1 有效期是 1 年多次往返了，有人知道H4 也是吗？ 多谢！
【在 f********h 的大作中提到】
: 现在H1 有效期是 1 年多次往返了，有人知道H4 也是吗？ 多谢！
j*2
5 楼
是我想错了。土了。那就在扫的时候自动检测了最短的了，所以直接就是O(n*min(m))
了。对吗？还有更简便的方法吗？
【在 h****n 的大作中提到】
: 二分的复杂度也是O（n×m）吧
: 两两比较 N/2 + N/4 + N/8 + ...+ 1 = N
: 复杂度还是O（N×M）啊
: 你怎么个二分的
了。对吗？还有更简便的方法吗？
【在 h****n 的大作中提到】
: 二分的复杂度也是O（n×m）吧
: 两两比较 N/2 + N/4 + N/8 + ...+ 1 = N
: 复杂度还是O（N×M）啊
: 你怎么个二分的
h*n
6 楼
这个其实只能叫divide and conquer
二分一般都是指binary search。。。
好像没法优化了，要非得说优化就按照你说的先找到最短的然后开始一个一个比
【在 j******2 的大作中提到】
: 是我想错了。土了。那就在扫的时候自动检测了最短的了，所以直接就是O(n*min(m))
: 了。对吗？还有更简便的方法吗？
二分一般都是指binary search。。。
好像没法优化了，要非得说优化就按照你说的先找到最短的然后开始一个一个比
【在 j******2 的大作中提到】
: 是我想错了。土了。那就在扫的时候自动检测了最短的了，所以直接就是O(n*min(m))
: 了。对吗？还有更简便的方法吗？
j*2
7 楼
那就在扫的时候自动检测了最短的了，所以直接就是O(n*min(m))
了。对吗
【在 h****n 的大作中提到】
: 这个其实只能叫divide and conquer
: 二分一般都是指binary search。。。
: 好像没法优化了，要非得说优化就按照你说的先找到最短的然后开始一个一个比
了。对吗
【在 h****n 的大作中提到】
: 这个其实只能叫divide and conquer
: 二分一般都是指binary search。。。
: 好像没法优化了，要非得说优化就按照你说的先找到最短的然后开始一个一个比
h*n
8 楼
恩。不过我觉得复杂度应该是O（N×avg（M））
【在 j******2 的大作中提到】
: 那就在扫的时候自动检测了最短的了，所以直接就是O(n*min(m))
: 了。对吗
【在 j******2 的大作中提到】
: 那就在扫的时候自动检测了最短的了，所以直接就是O(n*min(m))
: 了。对吗
j*2
9 楼
每检测一个元素时不是同时也看了它是不是到队尾了吗？所以不会扫超过min(m)轮。
另外我在想：divide and conquer是不是只能把quadratic变成log linear，对本身
linear的问题没有帮助啊？
【在 h****n 的大作中提到】
: 恩。不过我觉得复杂度应该是O（N×avg（M））
另外我在想：divide and conquer是不是只能把quadratic变成log linear，对本身
linear的问题没有帮助啊？
【在 h****n 的大作中提到】
: 恩。不过我觉得复杂度应该是O（N×avg（M））
d*i
10 楼
对啊，这个怎么能用到二分查找呢？
逐个头比较吧，O(N * M)
逐个头比较吧，O(N * M)
h*n
11 楼
你的M是指什么呀，我的M是指字符串的长度 avg M是指字符串的平均长度
具体M是多少和你字符串的排列是有关系的
考虑两种极端的情况，假设所有字符串的字符都是同一个字符，
第一种所有字符按照长度从长排到短，那么比较下来的长度就是AVG M
第二种就是所有字符按照长度从短到长排，那么比较下来的长度就是MIN M
divide conquer的复杂度可以用主定理来分析的，主要看最终的复杂度看分支数量，子
问题规模和合并操作的开销
T（n）=a(T/b) + O(n^d)
T（n）= n^d if d > logb a
= n^(logb a) if d < logb a
= n^d * lgn if d == logb a
【在 j******2 的大作中提到】
: 每检测一个元素时不是同时也看了它是不是到队尾了吗？所以不会扫超过min(m)轮。
: 另外我在想：divide and conquer是不是只能把quadratic变成log linear，对本身
: linear的问题没有帮助啊？
具体M是多少和你字符串的排列是有关系的
考虑两种极端的情况，假设所有字符串的字符都是同一个字符，
第一种所有字符按照长度从长排到短，那么比较下来的长度就是AVG M
第二种就是所有字符按照长度从短到长排，那么比较下来的长度就是MIN M
divide conquer的复杂度可以用主定理来分析的，主要看最终的复杂度看分支数量，子
问题规模和合并操作的开销
T（n）=a(T/b) + O(n^d)
T（n）= n^d if d > logb a
= n^(logb a) if d < logb a
= n^d * lgn if d == logb a
【在 j******2 的大作中提到】
: 每检测一个元素时不是同时也看了它是不是到队尾了吗？所以不会扫超过min(m)轮。
: 另外我在想：divide and conquer是不是只能把quadratic变成log linear，对本身
: linear的问题没有帮助啊？
d*i
12 楼
写的一个c++代码。 worst case O(N * M)
string longestCommonPrefix(vector &strs) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(strs.size() == 0) return "";
int longest = 0;
while(longest < strs[0].size())
{
for(int i = 1; i
if(longest == strs[i].size() || strs[i][longest] != strs[0][
longest])
return strs[0].substr(0, longest);
}
++longest;
}
return strs[0];
}
string longestCommonPrefix(vector
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(strs.size() == 0) return "";
int longest = 0;
while(longest < strs[0].size())
{
for(int i = 1; i
if(longest == strs[i].size() || strs[i][longest] != strs[0][
longest])
return strs[0].substr(0, longest);
}
++longest;
}
return strs[0];
}
j*2
13 楼
咱们的M是一个意思。不管你咋么排，一旦扫到最短串的末梢，就终结了啊？
【在 h****n 的大作中提到】
: 你的M是指什么呀，我的M是指字符串的长度 avg M是指字符串的平均长度
: 具体M是多少和你字符串的排列是有关系的
: 考虑两种极端的情况，假设所有字符串的字符都是同一个字符，
: 第一种所有字符按照长度从长排到短，那么比较下来的长度就是AVG M
: 第二种就是所有字符按照长度从短到长排，那么比较下来的长度就是MIN M
: divide conquer的复杂度可以用主定理来分析的，主要看最终的复杂度看分支数量，子
: 问题规模和合并操作的开销
: T（n）=a(T/b) + O(n^d)
: T（n）= n^d if d > logb a
: = n^(logb a) if d < logb a
【在 h****n 的大作中提到】
: 你的M是指什么呀，我的M是指字符串的长度 avg M是指字符串的平均长度
: 具体M是多少和你字符串的排列是有关系的
: 考虑两种极端的情况，假设所有字符串的字符都是同一个字符，
: 第一种所有字符按照长度从长排到短，那么比较下来的长度就是AVG M
: 第二种就是所有字符按照长度从短到长排，那么比较下来的长度就是MIN M
: divide conquer的复杂度可以用主定理来分析的，主要看最终的复杂度看分支数量，子
: 问题规模和合并操作的开销
: T（n）=a(T/b) + O(n^d)
: T（n）= n^d if d > logb a
: = n^(logb a) if d < logb a
h*n
14 楼
假如从最长M排到最短1，那么最坏情况下 第一次需要比较M-1次，第二次需要比较M-2
次 以此类推
【在 j******2 的大作中提到】
: 咱们的M是一个意思。不管你咋么排，一旦扫到最短串的末梢，就终结了啊？
次 以此类推
【在 j******2 的大作中提到】
: 咱们的M是一个意思。不管你咋么排，一旦扫到最短串的末梢，就终结了啊？
d*i
15 楼
worst case = N * M, N 是元素个数，M是最后结果长度。
j*2
16 楼
是N次不是M次吧？
2
【在 h****n 的大作中提到】
: 假如从最长M排到最短1，那么最坏情况下 第一次需要比较M-1次，第二次需要比较M-2
: 次 以此类推
2
【在 h****n 的大作中提到】
: 假如从最长M排到最短1，那么最坏情况下 第一次需要比较M-1次，第二次需要比较M-2
: 次 以此类推
h*n
17 楼
不对吧。。
考虑这样的例子
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
...
a
最后一行只有一个a，前面都是这么一大串
最后的结果长度是1 显然worst case不是N*1
【在 d******i 的大作中提到】
: worst case = N * M, N 是元素个数，M是最后结果长度。
考虑这样的例子
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
...
a
最后一行只有一个a，前面都是这么一大串
最后的结果长度是1 显然worst case不是N*1
【在 d******i 的大作中提到】
: worst case = N * M, N 是元素个数，M是最后结果长度。
h*n
18 楼
我表达不清吧
我指的是下面这样子的一个例子
aaaaa
aaaa
aaa
aa
a
第一次需要比较4次，第二次需要比较3次，以此类推
【在 j******2 的大作中提到】
: 是N次不是M次吧？
:
: 2
我指的是下面这样子的一个例子
aaaaa
aaaa
aaa
aa
a
第一次需要比较4次，第二次需要比较3次，以此类推
【在 j******2 的大作中提到】
: 是N次不是M次吧？
:
: 2
j*2
19 楼
这种情况第二次扫完就结束拉。
【在 h****n 的大作中提到】
: 我表达不清吧
: 我指的是下面这样子的一个例子
: aaaaa
: aaaa
: aaa
: aa
: a
: 第一次需要比较4次，第二次需要比较3次，以此类推
【在 h****n 的大作中提到】
: 我表达不清吧
: 我指的是下面这样子的一个例子
: aaaaa
: aaaa
: aaa
: aa
: a
: 第一次需要比较4次，第二次需要比较3次，以此类推
d*i
20 楼
错了，worst case = N *(M + 1)
h*n
21 楼
恩我们的扫法不一样 我是一个字符串一个字符串扫 你是一个字符一个字符扫 你那种
更好点
【在 j******2 的大作中提到】
: 这种情况第二次扫完就结束拉。
更好点
【在 j******2 的大作中提到】
: 这种情况第二次扫完就结束拉。
相关阅读
看NSC的140处理进度不寒而栗啊【求助】拿AP在国内，现在I-131 reopened for reconsideration请问有人了解DC的移民律所Wasserman, Mancini & Chang, P.C.吗？combo卡pending超过75天，需要SR吗有沒有最近提及I140的朋友加個微信群互動的啊？绿卡申请过程中出现合约中未出现情况，被律师追加讹钱，怎么办？【2017年1月第21绿】NSC RD06222016NSC 打指纹和Combo卡的问题EB1B NSC pp approved审稿转让【Gone!】请大家看看我这种background适合申请EB1A 吗NIW 申请--数学专业，求大神赐教刚发现485申请费涨了。。。EB1B 140在纠结是否追加pp 求建议 求bless准备EB1A二进宫了。。报个绿NSC rd 6-27-16议员和SR回复都是extended review，是不是表示掉进了黑洞请问新版NIW DIY4月NSC掉进黑洞了？？求助 NSC 485 package 退回