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

Question

我为 Codility 的一个课程编写了程序。它被称为计数 div。

例如。我给出数字 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：错误的解决方案，虽然似乎是正确和优雅的。min = 16, max =342, div = 17下面@Bopsi提到的检查：

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;
}

Answer 2

您的解决方案不符合初始要求

复杂：

预期最坏情况时间复杂度为 O(1)；
预计最坏情况的空间复杂度为 O(1)。

一条线解决方案

public class CountDiv {
    public int solution(int a, int b, int k) {
        return b / k - a / k + (a % k == 0 ? 1 : 0);
    }
}

检测结果