java - 从 codility 计算 div。使用递归的程序中的 StackOverflowError

Question

我为 Codility 的其中一课编写了程序。它称为计数分区。

例如。我给出数字 6、11 和 2。从 6 到 11 有 3 个数字可以除以 2，即 6、8、10，所以方法应该返回 3。

起初我只用整数编写了递归程序，但出现错误，所以我将其更改为 BigIntegers，但它根本没有帮助。它适用于小数字，但例如输入:

A = 0, B = 20000, K = 1 它给出错误:

Exception in thread "main" java.lang.StackOverflowError
at java.math.MutableBigInteger.divideKnuth(Unknown Source)
at java.math.MutableBigInteger.divideKnuth(Unknown Source)
at java.math.BigInteger.remainderKnuth(Unknown Source)
at java.math.BigInteger.remainder(Unknown Source)
at java.math.BigInteger.mod(Unknown Source)
at count_div.Solution.bigIntegerSolution(Solution.java:29)
at count_div.Solution.bigIntegerSolution(Solution.java:35)

这是我的代码:

public int solution(int A, int B, int K){

    BigInteger minValue = BigInteger.valueOf(A);
    BigInteger maxValue = BigInteger.valueOf(B);
    BigInteger div = BigInteger.valueOf(K);

    finalCounter = bigIntegerSolution(minValue, maxValue, div).intValue();

    return finalCounter;
}

public BigInteger bigIntegerSolution(BigInteger minValue, BigInteger maxValue, BigInteger div){

    int comparator = minValue.compareTo(maxValue);

    if(comparator <= 0){

        BigInteger modValue = minValue.mod(div);

        if( modValue.compareTo(zero) == 0){
            divCounter = divCounter.add(one);
        }
        minValue = minValue.add(one);
        bigIntegerSolution(minValue, maxValue, div);
    }

    return divCounter;
}

有什么我可以做的，或者我的解决方案想法不适合这个目的吗？我知道它们是其他解决方案，但我首先想到了这个，我想知道我是否可以修复它。

Answer 1

对于这个问题，递归不是一个很好的选择，因为当您在数字中移动时，您实际上没有太多的状态要存储。每次将范围增加一，深度就增加一。因此，您的堆栈溢出错误范围很大。

为此您不需要 BigInteger:导致问题的是堆栈的深度，而不是变量的大小。

这是一个使用递归的解决方案:

int divisorsInRange(int min, int max, int div) {
    if (min > max)
        return 0;
    else
        return (min % div == 0 ? 1 : 0) + divisorsInRange(min + 1, max, div);
}

非递归解决方案确实更简单、更高效。例如，使用 Java 8 流:

return IntStream.range(min, max).filter(n -> n % div == 0).count();

然而，您也可以在没有任何循环或流的情况下解决这个问题。

EDIT1:错误的解决方案，但似乎是正确且优雅的。检查下面@Bopsi 提到的 min = 16, max =342, div = 17:

int countDivisors(int min, int max, int div) {
    int count = (max - min) / div;
    if (min % div == 0 || max % div == 0)
        count++;
    return count;
}

EDIT2:正确的解决方案:

int solution(int A, int B, int K) {
    const int firstDividableInRange = A % K == 0 ? A : A + (K - A % K);
    const int lastDividableInRange = B - B % K;
    const int result = (lastDividableInRange - firstDividableInRange) / K + 1;

return result;
}