给定一个将生成某个BST的整数数组,该数组的多少个变体将导致相同的BST?我在C ++和python中找到了一些解决方案,但是在Java中却找不到。我想我了解如何开发正确代码的概念。
我这样做是为了应对某些Google foobar挑战。当我抛出任何可能想到的数组时,我会得到正确的答案,但是当我尝试使用Google验证我的代码时,我会收到ArithmeticException。我无法在代码中找到这种情况。
我需要以字符串形式返回答案,并且该参数可以是最大50个整数的数组。
这是我目前拥有的代码:
public static String answer(int[] seq) {
if (seq.length <= 1) {
return Integer.toString(1);
}
ArrayList<Integer> rightList = new ArrayList<>();
ArrayList<Integer> leftList = new ArrayList<>();
int root = seq[0];
for (int i : seq) {
if (i > root) {
leftList.add(i);
} else if (i < root) {
rightList.add(i);
}
}
int[] rightArray = new int[rightList.size()];
int[] leftArray = new int[leftList.size()];
int i = 0;
for (int j : rightList) {
rightArray[i++] = j;
}
int k = 0;
for (int l : leftList) {
leftArray[k++] = l;
}
int recurseLeft = Integer.parseInt(answer(leftArray));
int recurseRight = Integer.parseInt(answer(rightArray));
return Integer.toString(recurseLeft * recurseRight
* interleave(leftList.size(), rightList.size()));
}
private static int interleave(int a, int b) {
return (factorial(a + b)) / ((factorial(a) * factorial(b)));
}
private static int factorial(int n) {
return (n <= 1 ? 1 : n * factorial(n - 1));
}
有人可以帮助您发现错误或可能导致ArithmeticException的整数数组吗?
有人可以帮助您发现错误或可能导致ArithmeticException的整数数组吗?
在ArithmeticException
很可能抛出,因为你0.分割数增加堆栈跟踪将有助于查明它发生,但你在表演的划分interleave
方法。
factorial(a) * factorial(b)
是整数乘法。如果结果太大而无法容纳整数可以包含的最大值,它将溢出。
例如34!mod 2 41 =0。因此,您有一个退化的BST,其中所有元素都优于根(这里是数组的第一个元素),其中有35个元素,从而获得了异常。
因此,以下数组:
int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35};
会扔掉它。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句