申请绿卡推荐人的推荐信一定要电子签名吗？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Biology - 生物学

申请绿卡推荐人的推荐信一定要电子签名吗？

申请绿卡推荐人的推荐信一定要电子签名吗？# Biology - 生物学

g*y2014-05-06 07:05

1 楼

Given a number N, print all the ways (combinations) to represent the number
from the given set of integers.
Ex: Given set is {2,3,7,8,9} and given number N = 7, then the combinations
are:
7,2+2+3. Repetitions are not allowed, hence 3+2+2 or 2+3+2 are not allowed.
是个典型的递归搜索。
面试的人问他能不能O(n^2)或者O(n^3), 这个不可能吧？允许一个数重复用的话，答案
就是指数级的。
有什么想法？

l*02014-05-06 07:05

2 楼

推荐人写的信一定要电子签名吗？还是只要署名打字上去就行？

d*o2014-05-06 07:05

3 楼

use DP.
sort the array first, then use two dimensional array
a[k][N] to calculate the result.
k -- the length of the set (k is 5 in the example)
N -- target value (N is 7 in the example)
The complexity is O(K*N)

M*u2014-05-06 07:05

4 楼

how about:
{2, 3, 4, 6} to get N=8
when k=3, you can have {2,3,3}, {2,2,4}

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

: use DP.
: sort the array first, then use two dimensional array
: a[k][N] to calculate the result.
: k -- the length of the set (k is 5 in the example)
: N -- target value (N is 7 in the example)
: The complexity is O(K*N)

g*s2014-05-06 07:05

5 楼

参考完全背包问题

g*y2014-05-06 07:05

6 楼

完全背包问题，是求一个解，这个我相信可以O(kN)解。
A的问题是列出所有解。所有解本身是指数级，怎么可能在O(kN)算得出来呢？

c*p2014-05-06 07:05

7 楼

因为解集随着递规深度的增加坍缩得很快吧？

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

: 完全背包问题，是求一个解，这个我相信可以O(kN)解。
: A的问题是列出所有解。所有解本身是指数级，怎么可能在O(kN)算得出来呢？

g*y2014-05-06 07:05

8 楼

对{2, 3, 5, 7, 11, 13}， N=100, 有6898种解。
把解集打印出来就已经不可能k*N级别的了。

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

: 因为解集随着递规深度的增加坍缩得很快吧？

g*s2014-05-06 07:05

9 楼

前面用DP建立状态数组，打印结果的时候递归求解。但因为状态数组已经建立，所以递
归的时候不会访
问到任何无效结果。复杂度和结果数目也有关系。

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

: 完全背包问题，是求一个解，这个我相信可以O(kN)解。
: A的问题是列出所有解。所有解本身是指数级，怎么可能在O(kN)算得出来呢？

f*42014-05-06 07:05

10 楼

你这的2可以取两次？
可能的combinations是
2,3,7,23
还是，我理解错了？
谢谢

number

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

: Given a number N, print all the ways (combinations) to represent the number
: from the given set of integers.
: Ex: Given set is {2,3,7,8,9} and given number N = 7, then the combinations
: are:
: 7,2+2+3. Repetitions are not allowed, hence 3+2+2 or 2+3+2 are not allowed.
: 是个典型的递归搜索。
: 面试的人问他能不能O(n^2)或者O(n^3), 这个不可能吧？允许一个数重复用的话，答案
: 就是指数级的。
: 有什么想法？

d*o2014-05-06 07:05

11 楼

Are you sure there are 6898?
I got 1141.
I verified it works for small N and K but did not verify it for 6898
Here is my code (in java)

d*o2014-05-06 07:05

12 楼

Code correction:

public static int findWays(int[] a, int target)
{
int K = a.length;
int N = target;
int[][] DP = new int[K][N];
for(int i=0; i < K; i++)
for(int j = 0; j < N; j++)
DP[i][j] = 0;
for(int i = 0; i < K; i++)
DP[i][0] = 1;
for(int i=0; i < K; i++)
for(int j = 0; j < N; j++)
{
if(i>=1)
DP[i][j] += DP[i-1][j];
if(j-a[i] >= 0)
DP[i][j] += DP[i][j-a[i]];
}
return DP[K-1][N-1];
}

g*e2014-05-06 07:05

13 楼

try a={2}, target=1 or 2

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

: Code correction:
:
: public static int findWays(int[] a, int target)
: {
: int K = a.length;
: int N = target;
: int[][] DP = new int[K][N];
: for(int i=0; i < K; i++)
: for(int j = 0; j < N; j++)
: DP[i][j] = 0;

d*d2014-05-06 07:05

14 楼

可dp和recursive都没解决重复问题阿？

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

g*y2014-05-06 07:05

15 楼

public class SplitNumber {
private int count;

public int countWays(int sum, int[] numbers) {
int N = sum/numbers[0] + 1;
int[] a = new int[N];
count = 0;
for (int i=0; ia[0] = numbers[i];
split(sum, numbers, a, i, 1, a[0]);
}
return count;
}

private void split(int sum, int[] numbers, int[] a, int low, int len,
int curSum) {
if (curSum == sum) {
count++;
for (int i=0; iSystem.out.print(a[i] + " ");
}
System.out.println();
return;
}

for (int i=low; iif (curSum + numbers[i] > sum) break;
a[len] = numbers[i];
split(sum, numbers, a, i, len+1, curSum+numbers[i]);
}
}
}

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

: 可dp和recursive都没解决重复问题阿？

g*y2014-05-06 07:05

16 楼

I am not 100% sure, but from print out result, it looks right.
Code is posted, print out is in sorted order.

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

: Are you sure there are 6898?
: I got 1141.
: I verified it works for small N and K but did not verify it for 6898
: Here is my code (in java)

d*o2014-05-06 07:05

17 楼

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

: try a={2}, target=1 or 2

d*o2014-05-06 07:05

18 楼

Sorry,
Your code is correct, my code has got more results and there are some
duplicates.

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

: I am not 100% sure, but from print out result, it looks right.
: Code is posted, print out is in sorted order.

d*d2014-05-06 07:05

19 楼

yeah, 我想出来了。
不过dp要记下每一步的解，也够麻烦的。

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

: public class SplitNumber {
: private int count;
:
: public int countWays(int sum, int[] numbers) {
: int N = sum/numbers[0] + 1;
: int[] a = new int[N];
: count = 0;
: for (int i=0; i: a[0] = numbers[i];
: split(sum, numbers, a, i, 1, a[0]);

n*z2014-05-06 07:05

20 楼

if(i>=1)
DP[i][j] += DP[i-1][j];
if(j-a[i] >= 0)
DP[i][j] += DP[i][j-a[i]];
DP 不大熟悉。能解释以下这几行吗 THANKS.

g*s2014-05-06 07:05

21 楼

他的代码有点小错误，应该是：
public static int findWays(int[] a, int target) {
int K = a.length;
int N = target;
int[][] DP = new int[K][N+1];
DP[0][0] = 1;
for (int i = 0; i < K; i++)
for (int j = 0; j < N+1; j++) {
if (i >= 1)
DP[i][j] += DP[i - 1][j];
if (j - a[i] >= 0)
DP[i][j] += DP[i][j - a[i]];
}
return DP[K - 1][N];
}

【在 n**z 的大作中提到】

: if(i>=1)
: DP[i][j] += DP[i-1][j];
: if(j-a[i] >= 0)
: DP[i][j] += DP[i][j-a[i]];
: DP 不大熟悉。能解释以下这几行吗 THANKS.

g*s2014-05-06 07:05

22 楼

你的思路也是对的。有点小错误而已。

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

: Sorry,
: Your code is correct, my code has got more results and there are some
: duplicates.

s*y2014-05-06 07:05

23 楼

But still. How to print out the result from this DP table?
Thanks

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

: 你的思路也是对的。有点小错误而已。

s*d2014-05-06 07:05

24 楼

这个题跟careecup上那道找硬币组合的题实际上是一个意思。

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

: But still. How to print out the result from this DP table?
: Thanks

g*s2014-05-06 07:05

25 楼

递归。但有了这个DP table，所有的访问节点都是有效的。【在 speeddy (Wade) 的
大作中提
到: 】

s*y2014-05-06 07:05

26 楼

Can you give out the link.

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

: 这个题跟careecup上那道找硬币组合的题实际上是一个意思。

s*d2014-05-06 07:05

27 楼

你这个代码里面开始的时候，是不是要首先初始化dp数组全部为0，
然后将dp[0][0]=1这行换成下面的代码？
for (int i = 0; i < len; ++i)
{
if (a[i] <= target) dp[i][a[i]] = 1;
}
这样运行程序，按照前面的测试，出来的结果是6898
我怎么都想不明白你这个dp[0][0]=1是个啥意思? 请指教。

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

: 他的代码有点小错误，应该是：
: public static int findWays(int[] a, int target) {
: int K = a.length;
: int N = target;
: int[][] DP = new int[K][N+1];
: DP[0][0] = 1;
: for (int i = 0; i < K; i++)
: for (int j = 0; j < N+1; j++) {
: if (i >= 1)
: DP[i][j] += DP[i - 1][j];

n*z2014-05-06 07:05

28 楼

不对，那个数字代表已知的和为该j的组合。最初的时候只有和为零的有一种组合。

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

: 你这个代码里面开始的时候，是不是要首先初始化dp数组全部为0，
: 然后将dp[0][0]=1这行换成下面的代码？
: for (int i = 0; i < len; ++i)
: {
: if (a[i] <= target) dp[i][a[i]] = 1;
: }
: 这样运行程序，按照前面的测试，出来的结果是6898
: 我怎么都想不明白你这个dp[0][0]=1是个啥意思? 请指教。

g*s2014-05-06 07:05

29 楼

java默认0.
没必要改dp[0][0]=1就够了，这样出来的也就是6898.
这个表示只取第一个数字，和为0的数目，显然是1，就是一个不取。

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

s*d2014-05-06 07:05

30 楼

yes, you are right. Now I understand.
dp[i][j] means the number of ways to get the sum j using a[0]..a[i]
so for dp[0][0] is the number of ways to get the sum 0 using a[0],
which is 1 that picks up nothing.

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

: java默认0.
: 没必要改dp[0][0]=1就够了，这样出来的也就是6898.
: 这个表示只取第一个数字，和为0的数目，显然是1，就是一个不取。

h*i2014-05-06 07:05

31 楼

set里面的数可以是负数。

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

g*s2014-05-06 07:05

32 楼

i dont think so. if there are negative numbers, there is unlimit output.

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

: set里面的数可以是负数。