-3

我正在 InterviewStreet 进行练习程序，我有一个运行时间为 5.15xx 秒的解决方案，而 Java 解决方案允许的最长时间为 5 秒。我能用我在这里的东西做些什么来让它在 5 秒内完成吗？还有一个 256 MB 的限制，所以据我所知，这是解决问题的最节省时间和内存的方法......

编辑：N 和 K 的可能值是 N <= 10^9 和 K <= N，这就是为什么我选择使用 BigInteger 做所有事情的原因。最大试验次数为 10000。因此，基本上，您输入试验次数，然后输入每个试验次数的一对整数值，程序在第二个循环中计算方程的三个版本的二项式系数。我认为将所有内容读入数组，然后处理数组并将结果放入第三个数组以由第三个循环处理会更快，因为我认为这样可能会更快。我尝试在同一个循环中执行所有操作，但运行速度较慢。

我已经尝试了三种或四种不同的算法来计算二项式系数（nCr - 或 n 选择 r，都是说同一件事的不同方式）。一些算法涉及二维数组，如 c[n][k]。这是我提交的唯一没有出现某种内存错误的解决方案。答案需要输出 mod (10 ^ 6) + 3，因为 nCr * nCr 的答案非常庞大。该程序的示例运行是：

3

4 1
5 2
90 13

2
5
815483

不能在更快的机器上运行它，因为它需要通过他们的机器来计算，基本上我提交代码并针对他们的测试用例运行它，我不知道他们的测试用例是什么，只是输入是在上面给出的范围内。

和程序本身：

import java.math.BigInteger;
import java.util.Scanner;

public class Solution {

public BigInteger nCr(int n, int r) {
    if (r > n ) {
        return BigInteger.ZERO;
    }

    if (r > n / 2) {
        r = n - r;
    }
    BigInteger result = BigInteger.ONE;

    for (int i = 0; i < r; i++) {
        result = result.multiply(BigInteger.valueOf(n - i));
        result = result.divide(BigInteger.valueOf(i + 1));
    }
    return result;
}

public static void main(String[] args) {
    Scanner input = new Scanner( System.in );
    BigInteger m = BigInteger.valueOf(1000003);
    Solution p = new Solution();
    short T = input.nextShort(); // Number of trials
    BigInteger intermediate = BigInteger.ONE;
    int[] r = new int[T];
    int[] N = new int[T];
    int[] K = new int[T];

    short x = 0;

    while (x < T) {
    N[x] = input.nextInt();
    K[x] = input.nextInt();
    x++;
    }

    x = 0;
    while (x < T) {
    if (N[x] >= 3) { 
            r[x] = ((p.nCr(N[x] - 3, K[x]).multiply(p.nCr(N[x] + K[x], N[x] - 1))).divide(BigInteger.valueOf((N[x] + K[x]))).mod(m)).intValue();
        } else {
            r[x] = 0;
    }
    x++;
    }

    x = 0;
    while (x < T) {
    System.out.println(r[x]);
    x++;
    }
}

}

4

2 回答 2

0

不完全确定该算法试图完成什么，但我根据您对帖子的标记猜测二项式系数。

您需要检查我的建议是否修改了结果，但看起来您可以合并两个 while 循环：

原来的：

while (x < T) {
    N[x] = input.nextInt();
    K[x] = input.nextInt();
    x++;
}

x = 0;
while (x < T) {
if (N[x] >= 3) { 
        r[x] = ((p.nCr(N[x] - 3, K[x]).multiply(p.nCr(N[x] + K[x], N[x] - 1))).divide(BigInteger.valueOf((N[x] + K[x]))).mod(m)).intValue();
    } else {
        r[x] = 0;
    }
    x++;
}

新的：

x = 0;
while (x < T) {

//this has been moved from your first while loop
N[x] = input.nextInt();
K[x] = input.nextInt();

if (N[x] >= 3) { 
        r[x] = ((p.nCr(N[x] - 3, K[x]).multiply(p.nCr(N[x] + K[x], N[x] - 1))).divide(BigInteger.valueOf((N[x] + K[x]))).mod(m)).intValue();
    } else {
        r[x] = 0;
    }
    x++;
}
于 2012-05-11T22:07:07.503 回答
-1

尝试使用 profilerm 例如 jvisualvm 运行并运行此类

-Dcom.sun.management.jmxremote

附加到流程并启动配置文件。

于 2012-05-11T22:16:25.833 回答