editor 的supporting letter上的地址该怎么写？# Immigration - 落地生根
b*b
1 楼
已知一个sorted的array，怎么找到第一个pair的两个数，其之和为N。
我想到的使用hash，提示说binary search tree更好……没想到idea。
求教
我想到的使用hash，提示说binary search tree更好……没想到idea。
求教
I*1
2 楼
如果不写具体的center，就直接写：
U.S. Department of Homeland Security
U.S. Citizenship and Immigration Services
是不是可以？
还有看到有的人写的地址是：
United States Department of Justice
Immigration and Naturalization Service
到底哪个是正确的？
谢谢！
U.S. Department of Homeland Security
U.S. Citizenship and Immigration Services
是不是可以？
还有看到有的人写的地址是：
United States Department of Justice
Immigration and Naturalization Service
到底哪个是正确的？
谢谢！
i*h
3 楼
hash是O(N)
BST要O(NlgN)吧?
BST要O(NlgN)吧?
i*3
4 楼
In all letters, I used:
U.S. Department of Homeland Security
U.S. Citizenship and Immigration Services
U.S. Department of Homeland Security
U.S. Citizenship and Immigration Services
b*b
5 楼
为什么是nlgn， 已经sorted了。
我觉得关键他要求的是第一个。。。这个不知道该怎么处理
【在 i***h 的大作中提到】
: hash是O(N)
: BST要O(NlgN)吧?
我觉得关键他要求的是第一个。。。这个不知道该怎么处理
【在 i***h 的大作中提到】
: hash是O(N)
: BST要O(NlgN)吧?
c*g
6 楼
随便哪个都行
d*o
7 楼
输入和输出再定义清楚。
输入是什么，输出是什么？
给个例子。
【在 b******b 的大作中提到】
: 已知一个sorted的array，怎么找到第一个pair的两个数，其之和为N。
: 我想到的使用hash，提示说binary search tree更好……没想到idea。
: 求教
输入是什么，输出是什么？
给个例子。
【在 b******b 的大作中提到】
: 已知一个sorted的array，怎么找到第一个pair的两个数，其之和为N。
: 我想到的使用hash，提示说binary search tree更好……没想到idea。
: 求教
l*a
8 楼
他的提示也不对啊
已经有序就首尾找。。
【在 b******b 的大作中提到】
: 已知一个sorted的array，怎么找到第一个pair的两个数，其之和为N。
: 我想到的使用hash，提示说binary search tree更好……没想到idea。
: 求教
已经有序就首尾找。。
【在 b******b 的大作中提到】
: 已知一个sorted的array，怎么找到第一个pair的两个数，其之和为N。
: 我想到的使用hash，提示说binary search tree更好……没想到idea。
: 求教
i*h
9 楼
你在排序里面二分法找一个数不得 O(lgN)?
【在 b******b 的大作中提到】
: 为什么是nlgn， 已经sorted了。
: 我觉得关键他要求的是第一个。。。这个不知道该怎么处理
【在 b******b 的大作中提到】
: 为什么是nlgn， 已经sorted了。
: 我觉得关键他要求的是第一个。。。这个不知道该怎么处理
d*e
10 楼
这个不应该是一头一尾两个index移动吗？
【在 b******b 的大作中提到】
: 已知一个sorted的array，怎么找到第一个pair的两个数，其之和为N。
: 我想到的使用hash，提示说binary search tree更好……没想到idea。
: 求教
【在 b******b 的大作中提到】
: 已知一个sorted的array，怎么找到第一个pair的两个数，其之和为N。
: 我想到的使用hash，提示说binary search tree更好……没想到idea。
: 求教
b*b
11 楼
输入是一个sorted的数组
1,2,3,3,4,5.。。。
如果要求两个数之和为6，
输出为 3 ，3
【在 d****o 的大作中提到】
: 输入和输出再定义清楚。
: 输入是什么，输出是什么？
: 给个例子。
1,2,3,3,4,5.。。。
如果要求两个数之和为6，
输出为 3 ，3
【在 d****o 的大作中提到】
: 输入和输出再定义清楚。
: 输入是什么，输出是什么？
: 给个例子。
i*h
12 楼
哦是你对, 这样一来只要O(N)
还是和BST没关系
【在 d**e 的大作中提到】
: 这个不应该是一头一尾两个index移动吗？
还是和BST没关系
【在 d**e 的大作中提到】
: 这个不应该是一头一尾两个index移动吗？
h*y
13 楼
我也觉得如此，难道我题目没有看明白？
【在 d**e 的大作中提到】
: 这个不应该是一头一尾两个index移动吗？
【在 d**e 的大作中提到】
: 这个不应该是一头一尾两个index移动吗？
i*h
14 楼
为什么不是1,5?
【在 b******b 的大作中提到】
: 输入是一个sorted的数组
: 1,2,3,3,4,5.。。。
: 如果要求两个数之和为6，
: 输出为 3 ，3
【在 b******b 的大作中提到】
: 输入是一个sorted的数组
: 1,2,3,3,4,5.。。。
: 如果要求两个数之和为6，
: 输出为 3 ，3
b*b
15 楼
因为 相比于1,5,
3,3 是最早完整出现的
原谅我的表达吧。。。。实在是表述不清楚了
【在 i***h 的大作中提到】
: 为什么不是1,5?
3,3 是最早完整出现的
原谅我的表达吧。。。。实在是表述不清楚了
【在 i***h 的大作中提到】
: 为什么不是1,5?
i*h
16 楼
我知道了
用BST 找 6/2
然后中心开花向外找
【在 b******b 的大作中提到】
: 因为 相比于1,5,
: 3,3 是最早完整出现的
: 原谅我的表达吧。。。。实在是表述不清楚了
用BST 找 6/2
然后中心开花向外找
【在 b******b 的大作中提到】
: 因为 相比于1,5,
: 3,3 是最早完整出现的
: 原谅我的表达吧。。。。实在是表述不清楚了
d*e
17 楼
真的不是很明白
不过可以在于你从哪里数起
我觉得应该从1开始数
【在 b******b 的大作中提到】
: 因为 相比于1,5,
: 3,3 是最早完整出现的
: 原谅我的表达吧。。。。实在是表述不清楚了
不过可以在于你从哪里数起
我觉得应该从1开始数
【在 b******b 的大作中提到】
: 因为 相比于1,5,
: 3,3 是最早完整出现的
: 原谅我的表达吧。。。。实在是表述不清楚了
b*b
18 楼
恩，恩，就是从1开始数起
【在 d**e 的大作中提到】
: 真的不是很明白
: 不过可以在于你从哪里数起
: 我觉得应该从1开始数
【在 d**e 的大作中提到】
: 真的不是很明白
: 不过可以在于你从哪里数起
: 我觉得应该从1开始数
d*e
19 楼
我明白题目的意思了。
谢谢。
【在 b******b 的大作中提到】
: 恩，恩，就是从1开始数起
谢谢。
【在 b******b 的大作中提到】
: 恩，恩，就是从1开始数起
b*b
20 楼
这样是不是还得取决于建立一个结构良好的二叉树？
如果二叉树是个高度为n的二叉树，计算复杂度也不低啊
【在 i***h 的大作中提到】
: 我知道了
: 用BST 找 6/2
: 然后中心开花向外找
如果二叉树是个高度为n的二叉树，计算复杂度也不低啊
【在 i***h 的大作中提到】
: 我知道了
: 用BST 找 6/2
: 然后中心开花向外找
d*e
21 楼
我觉得前面有同学说的正确
用hash就是O(n)空间，O(n)时间
用bst是O(1)空间，O(nlgn)时间
【在 b******b 的大作中提到】
: 恩，恩，就是从1开始数起
用hash就是O(n)空间，O(n)时间
用bst是O(1)空间，O(nlgn)时间
【在 b******b 的大作中提到】
: 恩，恩，就是从1开始数起
i*h
22 楼
排序数组本身就是一个平衡BST啊
【在 b******b 的大作中提到】
: 这样是不是还得取决于建立一个结构良好的二叉树？
: 如果二叉树是个高度为n的二叉树，计算复杂度也不低啊
【在 b******b 的大作中提到】
: 这样是不是还得取决于建立一个结构良好的二叉树？
: 如果二叉树是个高度为n的二叉树，计算复杂度也不低啊
i*h
23 楼
对这个问题, 时间是 O(lgN + N), 也是O(N)
【在 d**e 的大作中提到】
: 我觉得前面有同学说的正确
: 用hash就是O(n)空间，O(n)时间
: 用bst是O(1)空间，O(nlgn)时间
【在 d**e 的大作中提到】
: 我觉得前面有同学说的正确
: 用hash就是O(n)空间，O(n)时间
: 用bst是O(1)空间，O(nlgn)时间
i*h
24 楼
不过最坏情况还没从头开始找好...
【在 i***h 的大作中提到】
: 对这个问题, 时间是 O(lgN + N), 也是O(N)
【在 i***h 的大作中提到】
: 对这个问题, 时间是 O(lgN + N), 也是O(N)
b*b
25 楼
对哦，一下糊涂了，汗……
【在 i***h 的大作中提到】
: 排序数组本身就是一个平衡BST啊
【在 i***h 的大作中提到】
: 排序数组本身就是一个平衡BST啊
y*u
26 楼
移动的过程可以用binary search
【在 d**e 的大作中提到】
: 这个不应该是一头一尾两个index移动吗？
【在 d**e 的大作中提到】
: 这个不应该是一头一尾两个index移动吗？
y*u
27 楼
hash 显然有worst case啊
【在 d**e 的大作中提到】
: 我觉得前面有同学说的正确
: 用hash就是O(n)空间，O(n)时间
: 用bst是O(1)空间，O(nlgn)时间
【在 d**e 的大作中提到】
: 我觉得前面有同学说的正确
: 用hash就是O(n)空间，O(n)时间
: 用bst是O(1)空间，O(nlgn)时间
d*e
28 楼
我好像跟我之前遇到的题混了一下，但这样似乎也是O(n)?
for each x in the array
map(x) = N-x
index_end = -1
for i in 0..n-1
if exists map(map(array_i))
if index_end == -1
index_end = n-1-i
else
index_end = min(index_end, n-1-i)
if index_end != -1
return (n-1-index_end, index_end)
【在 y**********u 的大作中提到】
: hash 显然有worst case啊
for each x in the array
map(x) = N-x
index_end = -1
for i in 0..n-1
if exists map(map(array_i))
if index_end == -1
index_end = n-1-i
else
index_end = min(index_end, n-1-i)
if index_end != -1
return (n-1-index_end, index_end)
【在 y**********u 的大作中提到】
: hash 显然有worst case啊
y*n
29 楼
头一个指针从左到右找。然后通过binary search 找另一个数。worse case是olgn.
d*y
30 楼
头一个指针从左到右找。然后通过binary search 找另一个数。
It makes sense, pointer + a sorted numbers
worse case是olgn.
How can get this?
It makes sense, pointer + a sorted numbers
worse case是olgn.
How can get this?
y*n
31 楼
＝ ＝刚刚二B了－ －worse case还是O（n）吧
【在 d******y 的大作中提到】
: 头一个指针从左到右找。然后通过binary search 找另一个数。
: It makes sense, pointer + a sorted numbers
: worse case是olgn.
: How can get this?
【在 d******y 的大作中提到】
: 头一个指针从左到右找。然后通过binary search 找另一个数。
: It makes sense, pointer + a sorted numbers
: worse case是olgn.
: How can get this?
y*n
32 楼
I made it wrong again, it should be nlog(n)
log(n-1)+log(n-2)+....log(1) = log((n-1)*log(n-2)*...log(1))
=O(nlog(n))
Hope it is right this time
【在 d******y 的大作中提到】
: 头一个指针从左到右找。然后通过binary search 找另一个数。
: It makes sense, pointer + a sorted numbers
: worse case是olgn.
: How can get this?
log(n-1)+log(n-2)+....log(1) = log((n-1)*log(n-2)*...log(1))
=O(nlog(n))
Hope it is right this time
【在 d******y 的大作中提到】
: 头一个指针从左到右找。然后通过binary search 找另一个数。
: It makes sense, pointer + a sorted numbers
: worse case是olgn.
: How can get this?
r*n
33 楼
O(N)
【在 b******b 的大作中提到】
: 已知一个sorted的array，怎么找到第一个pair的两个数，其之和为N。
: 我想到的使用hash，提示说binary search tree更好……没想到idea。
: 求教
【在 b******b 的大作中提到】
: 已知一个sorted的array，怎么找到第一个pair的两个数，其之和为N。
: 我想到的使用hash，提示说binary search tree更好……没想到idea。
: 求教
d*y
34 楼
log(n-1)+log(n-2)+....log(1) = log((n-1)*log(n-2)*...log(1))
=O(nlog(n))
this one should be
log(n-1)+log(n-2)+....log(1) = log((n-1)(n-2)...(1))
Is this right?
=O(nlog(n))
this one should be
log(n-1)+log(n-2)+....log(1) = log((n-1)(n-2)...(1))
Is this right?
b*u
35 楼
不好用吧？一个heap容易用数组表示，可用sorted array的话，root和child index的
关系不容易表达。
这题从左到右每个对后面进行binary search就行，找到N/2还没有就没了。O(nlogn).
【在 i***h 的大作中提到】
: 排序数组本身就是一个平衡BST啊
关系不容易表达。
这题从左到右每个对后面进行binary search就行，找到N/2还没有就没了。O(nlogn).
【在 i***h 的大作中提到】
: 排序数组本身就是一个平衡BST啊
g*u
36 楼
Imput:
array A, sum s.
Output:
pair (u,v)
Given an sorted array, choose the middle element m, then m is the root of a
balanced BST. If s-m>m, we search the right sub-tree, otherwise we search
the left sub-tree. Doing this recursively, we can find (u,v) in O(log(n)).
【在 b******b 的大作中提到】
: 输入是一个sorted的数组
: 1,2,3,3,4,5.。。。
: 如果要求两个数之和为6，
: 输出为 3 ，3
array A, sum s.
Output:
pair (u,v)
Given an sorted array, choose the middle element m, then m is the root of a
balanced BST. If s-m>m, we search the right sub-tree, otherwise we search
the left sub-tree. Doing this recursively, we can find (u,v) in O(log(n)).
【在 b******b 的大作中提到】
: 输入是一个sorted的数组
: 1,2,3,3,4,5.。。。
: 如果要求两个数之和为6，
: 输出为 3 ，3
g*u
37 楼
哦，不好意思，这个不对，有可能 u 在 left subtree,而 v 在 right subtree
a
【在 g**u 的大作中提到】
: Imput:
: array A, sum s.
: Output:
: pair (u,v)
: Given an sorted array, choose the middle element m, then m is the root of a
: balanced BST. If s-m>m, we search the right sub-tree, otherwise we search
: the left sub-tree. Doing this recursively, we can find (u,v) in O(log(n)).
a
【在 g**u 的大作中提到】
: Imput:
: array A, sum s.
: Output:
: pair (u,v)
: Given an sorted array, choose the middle element m, then m is the root of a
: balanced BST. If s-m>m, we search the right sub-tree, otherwise we search
: the left sub-tree. Doing this recursively, we can find (u,v) in O(log(n)).
y*u
38 楼
这个map是什么数据结构？
如果是array的话，小心越界。如果是hash或者bst的话，不止O(n)了
【在 d**e 的大作中提到】
: 我好像跟我之前遇到的题混了一下，但这样似乎也是O(n)?
: for each x in the array
: map(x) = N-x
: index_end = -1
: for i in 0..n-1
: if exists map(map(array_i))
: if index_end == -1
: index_end = n-1-i
: else
: index_end = min(index_end, n-1-i)
如果是array的话，小心越界。如果是hash或者bst的话，不止O(n)了
【在 d**e 的大作中提到】
: 我好像跟我之前遇到的题混了一下，但这样似乎也是O(n)?
: for each x in the array
: map(x) = N-x
: index_end = -1
: for i in 0..n-1
: if exists map(map(array_i))
: if index_end == -1
: index_end = n-1-i
: else
: index_end = min(index_end, n-1-i)
r*n
39 楼
这题牙根就不用神马BST
有一道很出名的题, 给一个2-d array, 冲右冲下都是递增的, 怎么找其中的某个
element...答案是从右上角开始一步一步走, O(n)时间
看着眼熟不?
【在 b******b 的大作中提到】
: 已知一个sorted的array，怎么找到第一个pair的两个数，其之和为N。
: 我想到的使用hash，提示说binary search tree更好……没想到idea。
: 求教
有一道很出名的题, 给一个2-d array, 冲右冲下都是递增的, 怎么找其中的某个
element...答案是从右上角开始一步一步走, O(n)时间
看着眼熟不?
【在 b******b 的大作中提到】
: 已知一个sorted的array，怎么找到第一个pair的两个数，其之和为N。
: 我想到的使用hash，提示说binary search tree更好……没想到idea。
: 求教
h*w
40 楼
mark
相关阅读
怎么给出证据说某杂志是领域内的top?exhibit上要写什么caption么？i485怎么支票到现在还没有兑现我最近一年才开始审稿，审了很多，IO会不会觉得太近了Cocurrent submission of I140 and 485请问现在485还要交无犯罪证明么？ 哪儿可以开啊请问一下Alien # 是不是EAD上的号？Opt Extension 期间可以申请NIW或EB1a吗？EB1A 485 pending换工作的问题EB1/NIW 律师的作用eb1b petition letter 谁签字的问题递交opt申请时是否必须在美国境内？这种情况应该算authorship还是contribution今天去Walk-in打指纹,不让打FYI: H1-B transferweb of science搜索以及citation各种分布地图的tricks【申精】急 刚递上485,131 父亲病重 可回国吗？有无影响国标GB参编人算哪类？EB1A greened申绿卡必须有老板的推荐信么？