我正在 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++;
}
}
}