Java

Question

给定一个将生成特定 BST 的整数数组，该数组的多少种变体将导致相同的 BST？我在 C++ 和 python 中找到了一些解决方案，但在 Java 中没有发现任何解决方案。我想我了解如何开发正确代码的概念。

我这样做是为了某个 Google foobar 挑战。当我抛出我能想到的任何可能的数组时，我得到了正确的答案，但是当我尝试使用 Google 验证我的代码时，我得到了 ArithmeticException。我找不到在我的代码中可能发生这种情况的地方。

我需要return字符串中的答案，参数可以是一个数组，最多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 的错误或可能的整数数组吗？

Answer 1

ArithmeticException 当您尝试除以零时抛出。您的代码中唯一使用除法的地方是 interleave 函数

Answer 2

Can someone help find either a bug or a possible array of integers that would cause an ArithmeticException?

可能会抛出 ArithmeticException，因为您将数字除以 0。添加堆栈跟踪有助于确定它发生的位置，但您正在 interleave 方法中执行除法。

factorial(a) * factorial(b)是整数乘法。如果结果太大而不适合整数可以具有的最大值，它将溢出。

比如34！ mod 2⁴¹ = 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,3‌0,31,32,33,34,35};

会扔。

Java - 数字数组的可能排列，这将导致相同的二叉搜索树

Java - possible permutations of an array of numbers which would result in an identical binary search tree

arrays

permutation

binary-search-tree