请教一道经典的面试真题 - 未名空间MITBBS历史存档

y*82015-08-06 07:08

1 楼

【以下文字转载自 SanFrancisco 讨论区】
发信人: yan2008 (yan), 信区: SanFrancisco
标题: 没有绿卡,只有学生身份或工作身份的人,可以在美国开小公司吗
发信站: BBS 未名空间站 (Thu Dec 30 21:01:35 2010, 美东)
没有绿卡,只有学生身份或工作身份的人,可以在美国开小公司吗? 如果可以开,需要什
么条件(人数,注册资金等)
谢谢啦！

x*02015-08-06 07:08

2 楼

给你一个int N，然后给你一个int[]，数组里每个元素只能用一次，要求通过加法得到
从1到N的所有数字，返回最少需要添加元素的个数
比如：N = 6，arr = [1, 3]。最少需要添加的元素个数就是1，因为我们只用添加2就
可以了, arr = [1,2,3]。这样所有1到6的元素都能被arr这个数组的subset相加得到。
注意不能使用产生的元素啊。比如说：arr = [1,3] 咱们可以产生4=1+3。但是不能产
生5（5=4+1），这是非法的。
大家有什么想法吗，最没有效率的方法都想不出来。sad！

n*n2015-08-06 07:08

3 楼

Yes. Check the state's commerce department website for details for different
types of corps.

l*s2015-08-06 07:08

4 楼

try this. The idea is from that for each N, the minimum set of nums are from
1 to x, where x is to make sure Sigma(1,x) == N or just greater than N.
public int minAddition(int N, int[] nums)
{
int i = 1, sum = 0, result = 0;
for(i = 0; sum < N; i++) sum += (result = i + 1);
Array.Sort(nums);
for(int j = 0; j < nums.Length; j++)
if((j == 0 || (j > 0 && nums[j] != nums[j-1])) && nums[j] <= i &&
nums[j] > 0)
result--;
return result;
}

d*u2015-08-06 07:08

5 楼

but no payroll for yourself...
IRS will doubt the purpose behind!

b*b2015-08-06 07:08

6 楼

don't think it's correct, e.g. for N=7, and nums=[1,4], the correct answer
is 1, you just need to add 2 to the array: [1, 2, 4] which can form any
number 1-7.

from

【在 l******s 的大作中提到】

: try this. The idea is from that for each N, the minimum set of nums are from
: 1 to x, where x is to make sure Sigma(1,x) == N or just greater than N.
: public int minAddition(int N, int[] nums)
: {
: int i = 1, sum = 0, result = 0;
: for(i = 0; sum < N; i++) sum += (result = i + 1);
: Array.Sort(nums);
: for(int j = 0; j < nums.Length; j++)
: if((j == 0 || (j > 0 && nums[j] != nums[j-1])) && nums[j] <= i &&
: nums[j] > 0)

y*82015-08-06 07:08

7 楼

thanks for all!

b*b2015-08-06 07:08

8 楼

I feel this is a searching algorithm, so first you generate all the possible
combinations of with the given array, e.g. for [1,4], the possible numbers
can generate is 1, 4, 5 (4+1). now we go through it in order, let's say
number i is missing, then we add number i to the array, and add all existing
numbers +i to the possible values, e.g. in that example, we add 2, and add
3 (1+2), 6 (4+2), 7 (5+2) to the list, then check what's the next missing
number.
use the bitvector to check what's the next missing number should make it
more space efficient.

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

: don't think it's correct, e.g. for N=7, and nums=[1,4], the correct answer
: is 1, you just need to add 2 to the array: [1, 2, 4] which can form any
: number 1-7.
:
: from

l*s2015-08-06 07:08

9 楼

Great catch. I guess just need small modification to handle the case of "
Right Sum + 1". "Right Sum" means 6 (1-3), 10(1-4), 55(1-10), etc.

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

: don't think it's correct, e.g. for N=7, and nums=[1,4], the correct answer
: is 1, you just need to add 2 to the array: [1, 2, 4] which can form any
: number 1-7.
:
: from

x*02015-08-06 07:08

10 楼

seems that this is a correct solution. Let me think about it.

possible
numbers
existing
add

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

: I feel this is a searching algorithm, so first you generate all the possible
: combinations of with the given array, e.g. for [1,4], the possible numbers
: can generate is 1, 4, 5 (4+1). now we go through it in order, let's say
: number i is missing, then we add number i to the array, and add all existing
: numbers +i to the possible values, e.g. in that example, we add 2, and add
: 3 (1+2), 6 (4+2), 7 (5+2) to the list, then check what's the next missing
: number.
: use the bitvector to check what's the next missing number should make it
: more space efficient.

x*02015-08-06 07:08

11 楼

seems that this is a correct solution. Let me think about it.

possible
numbers
existing
add

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

: I feel this is a searching algorithm, so first you generate all the possible
: combinations of with the given array, e.g. for [1,4], the possible numbers
: can generate is 1, 4, 5 (4+1). now we go through it in order, let's say
: number i is missing, then we add number i to the array, and add all existing
: numbers +i to the possible values, e.g. in that example, we add 2, and add
: 3 (1+2), 6 (4+2), 7 (5+2) to the list, then check what's the next missing
: number.
: use the bitvector to check what's the next missing number should make it
: more space efficient.

x*02015-08-06 07:08

12 楼

Let me think about this algorithm. Seems pretty ingenious

from

【在 l******s 的大作中提到】

: try this. The idea is from that for each N, the minimum set of nums are from
: 1 to x, where x is to make sure Sigma(1,x) == N or just greater than N.
: public int minAddition(int N, int[] nums)
: {
: int i = 1, sum = 0, result = 0;
: for(i = 0; sum < N; i++) sum += (result = i + 1);
: Array.Sort(nums);
: for(int j = 0; j < nums.Length; j++)
: if((j == 0 || (j > 0 && nums[j] != nums[j-1])) && nums[j] <= i &&
: nums[j] > 0)

b*e2015-08-06 07:08

13 楼

: 给你一个int N，然后给你一个int[]，数组里每个元素只能用一次，要求通过加法得到
: 从1到N的所有数字，返回最少需要添加元素的个数
: 比如：N = 6，arr = [1, 3]。最少需要添加的元素个数就是1，因为我们只用添加2就
: 可以了, arr = [1,2,3]。这样所有1到6的元素都能被arr这个数组的subset相加得到。
: 注意不能使用产生的元素啊。比如说：arr = [1,3] 咱们可以产生4=1+3。但是不能产
: 生5（5=4+1），这是非法的。
: 大家有什么想法吗，最没有效率的方法都想不出来。sad！

b*b2015-08-06 07:08

14 楼

very good solution, nice!

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

: var missing = function(n, a) {
: var output = [];
: var sum = 0;
: var i = 0;
: while(true) {
: if (i >= a.length || a[i] > sum + 1) {
: output.push(sum + 1);
: sum += sum + 1;
: } else {
: sum += a[i];

h*l2015-08-06 07:08

15 楼

i think it should match 1 2 4 8 16 ....

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

: 给你一个int N，然后给你一个int[]，数组里每个元素只能用一次，要求通过加法得到
: 从1到N的所有数字，返回最少需要添加元素的个数
: 比如：N = 6，arr = [1, 3]。最少需要添加的元素个数就是1，因为我们只用添加2就
: 可以了, arr = [1,2,3]。这样所有1到6的元素都能被arr这个数组的subset相加得到。
: 注意不能使用产生的元素啊。比如说：arr = [1,3] 咱们可以产生4=1+3。但是不能产
: 生5（5=4+1），这是非法的。
: 大家有什么想法吗，最没有效率的方法都想不出来。sad！

x*02015-08-06 07:08

16 楼

can you give me a little bit description about this algorithm?
Seems pretty smart,but without comment, I did not understand.

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

: very good solution, nice!

x*02015-08-06 07:08

17 楼

can you give me a little bit description about this algorithm?
Seems pretty smart,but without comment, I did not understand.

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

: var missing = function(n, a) {
: var output = [];
: var sum = 0;
: var i = 0;
: while(true) {
: if (i >= a.length || a[i] > sum + 1) {
: output.push(sum + 1);
: sum += sum + 1;
: } else {
: sum += a[i];

x*02015-08-06 07:08

18 楼

not exactly.

【在 h***l 的大作中提到】

: i think it should match 1 2 4 8 16 ....

x*02015-08-06 07:08

19 楼

How about this case:
arr = [10, 28], N = 33.
Output: 5 ([1, 2, 4, 8, 26])?

from

【在 l******s 的大作中提到】

: try this. The idea is from that for each N, the minimum set of nums are from
: 1 to x, where x is to make sure Sigma(1,x) == N or just greater than N.
: public int minAddition(int N, int[] nums)
: {
: int i = 1, sum = 0, result = 0;
: for(i = 0; sum < N; i++) sum += (result = i + 1);
: Array.Sort(nums);
: for(int j = 0; j < nums.Length; j++)
: if((j == 0 || (j > 0 && nums[j] != nums[j-1])) && nums[j] <= i &&
: nums[j] > 0)