Resubmit I-485 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Immigration - 落地生根

Resubmit I-485

Resubmit I-485# Immigration - 落地生根

f*e2012-01-03 08:01

1 楼

给一个包含数字的数组，求该数组的最长的子数组（这里说的子数组是下标连续），要
求这个子数组中的数组是一个连续的序列（不需要排好序）。
例如，给一个数组[4,5,1,5,7,6,8,4,1]，最长的满足条件的子数组是[5,7,6,8,4]。因
为该子数组中，5,7,6,8,4是一个连续的序列。
求算法

a*12012-01-03 08:01

2 楼

2008年6月的Priority Date，12月中旬交的I-485被Reject了，Notice 上写着:"
Priority Date was not current"。2012 年1月的Visa Bulletin EB2 Cutting-off
Date 排到了2009年1月1日。现在 Resubmit I-485 需要重新填写所有的表格吗？I-485
上有问是否之前申请过绿卡，审批的结果如何？要把这次Rejection 写上吗？多谢！

p*22012-01-03 08:01

3 楼

。因
[4,5,5,7,6,8,4,1]
输出是什么？

【在 f*****e 的大作中提到】

: 给一个包含数字的数组，求该数组的最长的子数组（这里说的子数组是下标连续），要
: 求这个子数组中的数组是一个连续的序列（不需要排好序）。
: 例如，给一个数组[4,5,1,5,7,6,8,4,1]，最长的满足条件的子数组是[5,7,6,8,4]。因
: 为该子数组中，5,7,6,8,4是一个连续的序列。
: 求算法

c*j2012-01-03 08:01

4 楼

why did u submit last month

【在 a***1 的大作中提到】

: 2008年6月的Priority Date，12月中旬交的I-485被Reject了，Notice 上写着:"
: Priority Date was not current"。2012 年1月的Visa Bulletin EB2 Cutting-off
: Date 排到了2009年1月1日。现在 Resubmit I-485 需要重新填写所有的表格吗？I-485
: 上有问是否之前申请过绿卡，审批的结果如何？要把这次Rejection 写上吗？多谢！

f*e2012-01-03 08:01

5 楼

5,7,6,8,4

【在 p*****2 的大作中提到】

:
: 。因
: [4,5,5,7,6,8,4,1]
: 输出是什么？

l*g2012-01-03 08:01

6 楼

楼主的问题解决了吗？我遇到了相同的问题（ priority date 比排期早了一天），正
琢磨着如何 resubmit.
多谢！

p*22012-01-03 08:01

7 楼

BF要N^3.
这题复杂度什么要求？

a*y2012-01-03 08:01

8 楼

为什么N^3, 你拍好序做，排序O（nlogn）
然后有个map来存index

f*e2012-01-03 08:01

9 楼

没有要求，zz的。

【在 p*****2 的大作中提到】

: BF要N^3.
: 这题复杂度什么要求？

l*82012-01-03 08:01

10 楼

O(n^3) is for straightforward algorithm.
If you sort the array and use a map, you still need at least O(n^2), right?

【在 a*******y 的大作中提到】

: 为什么N^3, 你拍好序做，排序O（nlogn）
: 然后有个map来存index

f*e2012-01-03 08:01

11 楼

有重复元素怎么办？

【在 a*******y 的大作中提到】

: 为什么N^3, 你拍好序做，排序O（nlogn）
: 然后有个map来存index

f*e2012-01-03 08:01

12 楼

p*22012-01-03 08:01

13 楼

。因
[4,5,5,7,6,8,4,1]
输出是什么？

【在 f*****e 的大作中提到】

f*e2012-01-03 08:01

14 楼

5,7,6,8,4

【在 p*****2 的大作中提到】

:
: 。因
: [4,5,5,7,6,8,4,1]
: 输出是什么？

p*22012-01-03 08:01

15 楼

BF要N^3.
这题复杂度什么要求？

a*y2012-01-03 08:01

16 楼

为什么N^3, 你拍好序做，排序O（nlogn）
然后有个map来存index

f*e2012-01-03 08:01

17 楼

没有要求，zz的。

【在 p*****2 的大作中提到】

: BF要N^3.
: 这题复杂度什么要求？

l*82012-01-03 08:01

18 楼

O(n^3) is for straightforward algorithm.
If you sort the array and use a map, you still need at least O(n^2), right?

【在 a*******y 的大作中提到】

: 为什么N^3, 你拍好序做，排序O（nlogn）
: 然后有个map来存index

f*e2012-01-03 08:01

19 楼

有重复元素怎么办？

【在 a*******y 的大作中提到】

: 为什么N^3, 你拍好序做，排序O（nlogn）
: 然后有个map来存index

Y*f2012-01-03 08:01

20 楼

O(N^2)算法：
先算出对所有i>j, i到j的区间的最大最小值，需要二维数组。这个可以O(N^2)做到
然后计算一个一维数组，其值是到该位置为止最长的无重复元素的子数组元素个数。这
个可以O(N)做到。
再利用如果一个数组没有重复元素，其最大值-最小值=元素的个数-1 算出最长的子数
组。
不知道有没有更快的算法。

。因

【在 f*****e 的大作中提到】

f*t2012-01-03 08:01

21 楼

如果没有重复数字，这题是子序列构成最长连续数字的变种吧，想了一下应该能用相同
的方法，O(n)时间+O(n)空间的复杂度

b*e2012-01-03 08:01

22 楼

稍微聪明一点的BF应该是n*log(n):
固定k, 长度为k的valid substring的存在性可以用O(n)判断。对k做二分。

【在 p*****2 的大作中提到】

: BF要N^3.
: 这题复杂度什么要求？

Y*f2012-01-03 08:01

23 楼

"长度为k的valid substring的存在性可以用O(n)判断"
这个怎么弄？

【在 b***e 的大作中提到】

: 稍微聪明一点的BF应该是n*log(n):
: 固定k, 长度为k的valid substring的存在性可以用O(n)判断。对k做二分。

d*x2012-01-03 08:01

24 楼

RMQ, O(nlogn)预处理，O(1)查询区间最大最小值
只是我对那个二分查找存疑

【在 Y********f 的大作中提到】

: "长度为k的valid substring的存在性可以用O(n)判断"
: 这个怎么弄？

S*t2012-01-03 08:01

25 楼

不能二分。。。
这个题目很久很久以前我在blog上写过一次……=_=
http://computationalpuzzles.wordpress.com/2011/12/05/algorithms

【在 d**********x 的大作中提到】

: RMQ, O(nlogn)预处理，O(1)查询区间最大最小值
: 只是我对那个二分查找存疑

d*x2012-01-03 08:01

26 楼

nice...
我就满足于RMQ好了。。

【在 S******t 的大作中提到】

: 不能二分。。。
: 这个题目很久很久以前我在blog上写过一次……=_=
: http://computationalpuzzles.wordpress.com/2011/12/05/algorithms

j*y2012-01-03 08:01

27 楼

rmq 是啥啊？

【在 d**********x 的大作中提到】

: nice...
: 我就满足于RMQ好了。。

d*x2012-01-03 08:01

28 楼

http://baike.baidu.com/view/1536346.htm

【在 j*****y 的大作中提到】

: rmq 是啥啊？

x*02012-01-03 08:01

29 楼

mark

G*A2012-01-03 08:01

30 楼

我怎么觉得你这个O(n^2)内搞不定

【在 Y********f 的大作中提到】

: O(N^2)算法：
: 先算出对所有i>j, i到j的区间的最大最小值，需要二维数组。这个可以O(N^2)做到
: 然后计算一个一维数组，其值是到该位置为止最长的无重复元素的子数组元素个数。这
: 个可以O(N)做到。
: 再利用如果一个数组没有重复元素，其最大值-最小值=元素的个数-1 算出最长的子数
: 组。
: 不知道有没有更快的算法。
:
: 。因

c*t2012-01-03 08:01

31 楼

如果是允许重复的，既[4,5,6,5,7,6,8]可以是解，能不能循环切割？
1）扫一遍求出所有 min到max中的区间，例子中 [1],[4,5,6,7,8]
2) 扫第二遍，不同区间的切割开成不同的数组[4,5] [1] [5,7,6,8,4] [1]
3）对2）的每个结果,调用1，recursion.如果1）的结果只有一个区间，既找到了一个。
最后返回最长的，当然3)中，如果区间长度小于等于已经找到的最长数组，就不用处理
了。
这个算法复杂度最坏好像是O(n^2)（都不连续），但实际应该很快吧。O(n) space, 好
处是容易写 :D

。因

【在 f*****e 的大作中提到】

b*e2012-01-03 08:01

32 楼

对，不能二分。k有解不能退出(k-1)有解。

【在 S******t 的大作中提到】

: 不能二分。。。
: 这个题目很久很久以前我在blog上写过一次……=_=
: http://computationalpuzzles.wordpress.com/2011/12/05/algorithms