我为Codility的一堂课写了一个程序。它被称为计数div。
例如。我给出了数字6,11和2.有3个数字从6到11我们可以除以2，它的6,8,10这样的方法应该返回3。
起初我只使用int进行递归程序，但是我得到了错误，所以我将它改为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;
}
有什么我可以做的，或者我的解决方案想法只是为了这个目的不好？我知道他们是其他解决方案，但我首先想出了这个，我想知道我是否可以修复它。
对于这个问题，递归不是一个很好的选择，因为当你浏览数字时，你真的没有很多状态存储。每次将范围增加1时，将深度增加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();
但是，您也可以在没有任何循环或流的情况下解决此问
编辑1：错误的解决方案，虽然似乎是正确和优雅的。检查以下@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;
}
您的解决方案超出了初始要求
复杂：
预期的最坏情况时间复杂度为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);
}
}
B值越大，BigIntegers将存储在您的机器内存中。这就是为什么它适用于小值，并且不适用于大值。因此，递归是解决此类问题的一种不好的解决方案，因为您试图在内存中存储太多值。
这是Java中的（100/100）解决方案。
class Solution {
public int solution(int A, int B, int K) {
int result;
int toAdd = 0;
int lowerBound = 0;
int upperBound = 0;
if (A % K == 0) {
lowerBound = A;
toAdd = 1;
} else {
lowerBound = A - A % K + K;
if ((lowerBound - A % K) >= 0 ) {
toAdd = 1;
}
}
if (B % K == 0) {
upperBound = B;
} else {
upperBound = B - B % K;
}
result = (upperBound - lowerBound) / K + toAdd;
return result;
}
}
我能够使用算术级数（https://en.wikipedia.org/wiki/Arithmetic_progression）解决问题。我不得不为0添加一个特殊情况，我无法解释但它是基于测试结果：
if (K > B)
return A == 0 ? 1 : 0;
int min = A >= K ? A + A % K : K;
int max = B - (B % K);
// an = a1 + (n − 1) * ⋅r
return (max - min + K) / K + (A == 0 ? 1 : 0);
这是我的:)
public int solution(int A, int B, int K) {
int numEl = 0;
int first = A;
while(numEl == 0 && first <= B) {
if(first%K == 0) {
numEl += 1;
} else
first += 1;
}
numEl += (B - first)/K;
return numEl;
}
按照代码注释来获得清晰的图片
public int solution(int A, int B, int K) {
int start = 0;
int end = 0;
int count = 0;
start = (A % K == 0)? A : ((A / K)* K ) + K; //minimum divisible by K in the range
end = (B % K == 0)? B : B - (B % K); // maximum divisible by K in the range
count = ((end - start) / K) + 1; //no of divisibles by K inside the range start & end
return count;
}
这是我的解决方案。想法是我正在寻找可以在K上划分的第一个数字，其中范围内的可分数是((B - first) / K) + 1。我们需要知道最大限制（这是B）和第一个可分割之间的区别，并计算它们之间可以适合多少K，因为不包括第一个数字我们需要添加一个以获得正确的结果。
class Solution {
public int solution(int A, int B, int K) {
if (A == B) {
if (A % K == 0) return 1;
else return 0;
}
int first = (A % K == 0) ? A : A + (K - (A % K));
if (A != 0 && (first > B || first == 0)) return 0;
return ((B - first) / K) + 1;
}
}
简洁是红宝石。这也得到100％
def solution(a, b, k)
(b / k - (a - 1) / k).ceil
end