更新的答案
我最初的答案很容易理解，但编码起来很棘手。这是更容易编码的东西。这是一个直接的非递归解决方案，它通过计算每个位置出现零的方式的数量来工作。
例如：
x <= 1234. 以下形式的数有多少？
x = ??0?
“数百个或更多”（1,2，...，12）有 12 种可能性。那么必须有一个零。那么最后一位数字有 10 种可能性。这给出12 * 10 = 120了在第三位包含 0 的数字。
因此，范围（1 到 1234）的解是：
但一个例外是如果n包含一个零数字。考虑以下情况：
x <= 12034. 以下形式的数有多少？
x = ??0??
我们有 12 种方法来挑选“数千个或更多”。对于 1, 2, ... 11，我们可以选择任意最后两位数字（给出 11 * 100 种可能性）。但是如果我们从 12 开始，我们只能在最后两位数字之间选择一个数字00。34所以我们得到11 * 100 + 35了完全的可能性。
这是这个算法的一个实现（用 Python 编写，但应该很容易移植到 C 中）：
def countZeros(n):
result = 0
i = 1
while True:
b, c = divmod(n, i)
a, b = divmod(b, 10)
if a == 0:
return result
if b == 0:
result += (a - 1) * i + c + 1
else:
result += a * i
i *= 10
我建议将此算法从以 2 为基数调整为以 10 为基数：
结果算法为 O(log N)。
方法是编写一个简单的递归函数count(n)，从 1 到 计数零n。
关键的观察是，如果 N 以 9 结尾，例如：
123456789
您可以将 0 到 N 的数字分成 10 个大小相等的组。第 0 组是以 0 结尾的数字。第 1 组是以 1 结尾的数字。第 2 组是以 2 结尾的数字。依此类推，一直到第 9 组，即所有以 9 结尾的数字。
除了第 0 组之外，每个组都count(N/10)对总数贡献了零位，因为它们都没有以零结尾。第 0 组贡献count(N/10)（计算除最后一位以外的所有数字）加上N/10（从最后一位数中计算零）。
由于我们是从 1 到 N，而不是从 0 到 N，这个逻辑对于个位数的 N 是不成立的，所以我们只是将其作为一种特殊情况来处理。
[更新]
到底是什么，让我们概括并定义数字在从 1 到count(n, d)的数字中出现的次数。dn
/* Count how many d's occur in a single n */
unsigned
popcount(unsigned n, unsigned d) {
int result = 0;
while (n != 0) {
result += ((n%10) == d);
n /= 10;
}
return result;
}
/* Compute how many d's occur all numbers from 1 to n */
unsigned
count(unsigned n, unsigned d) {
/* Special case single-digit n */
if (n < 10) return (d > 0 && n >= d);
/* If n does not end in 9, recurse until it does */
if ((n % 10) != 9) return popcount(n, d) + count(n-1, d);
return 10*count(n/10, d) + (n/10) + (d > 0);
}
该案例的丑陋n < 10再次来自范围是 1 到n而不是 0 到... 对于任何大于或等于 的n单个数字，计数为 1，除非为 0。ndd
将此解决方案转换为非递归循环是 (a) 微不足道的，(b) 不必要的，并且 (c) 留给读者作为练习。
[更新 2]
最后(d > 0)一项也来自 1 到n而不是 0 到的范围n。当n以 9 结尾时，从 1 到n包含 1 的数字有多少个有尾数d？好吧，当d为零时，答案是n/10；当d非零时，它比那多一，因为它包括值d本身。
例如，如果n是 19 并且d是 0，则只有一个较小的数字以 0 结尾（即 10）。但如果n是 19 和d2，则有两个以 2 结尾的较小数字（即 2 和 12）。
感谢@Chan 在评论中指出这个错误；我已经在代码中修复了它。
让Z(n) = #zero digits in numbers 0 <= k < n. 显然，Z(0) = 0。
如果n = 10*k + r, 0 <= r <= 9，所有10*k数字10*j + s, 0 <= j < k, 0 <= s <= 9都在范围内，每个倒数第十个数字都是 0，所以是k零，并且每个前缀j（除了最后一个数字）出现十次，但我们不能数 0，所以前缀中的零个数是10*(Z(k)-1)。
数字中零的r个数10*k, ..., 10*k + (r-1)是r*number of zeros in k + (r > 0 ? 1 : 0)。
所以我们有一个O(log n)计算算法Z(n)
unsigned long long Z(unsigned long long n)
{
if (n == 0) {
return 0;
}
if (n <= 10) {
return 1;
}
unsigned long long k = n/10, r = n%10;
unsigned long long zeros = k + 10*(Z(k)-1);
if (r > 0) {
zeros += r*zeroCount(k) + 1;
}
return zeros;
}
unsigned zeroCount(unsigned long long k)
{
unsigned zeros = 0;
while(k) {
zeros += (k % 10) == 0;
k /= 10;
}
return zeros;
}
要计算任意范围的数字，
unsigned long long zeros_in_range(unsigned long long low, unsigned long long high)
{
return Z(high+1) - Z(low); // beware of overflow if high is ULLONG_MAX
}
我有一个非常简单的方法来计算 1 到 n 之间的 0。我希望这能解决您的问题并消除复杂性
function countZero(n) {
var count = 0;
while (n > 0) {
count += Math.floor(n / 10);
n = n / 10;
}
console.log(count);
}
countZero(99);
class FindZero{
public int findZero(int lastNumber){
int count=1,k;
if(lastNumber<10)
return 0;
else if(lastNumber==10)
return 1;
else{
for(int i=11;i<=lastNumber;i++){
k=i;
while(k>0){
if(k%10==0)
count++;
k=k/10;
}
}
return count;
}
}
public static void main(String args[]){
FindZero obj = new FindZero();
System.out.println(obj.findZero(1234));
}
}
我处理这个问题的方式：
数字可以在 1 到 N 的范围内：
所以，我把它分解成这样的范围：
Rangle : #Digits : #Zeros
1 - 9 : 1 : 0
10 - 99 : 2 : 9 (number of all the possible digits when zero is at units place=> _0 ie, 1,2,3,4,5,6,7,8,9
100 - 199 : 3 : 20 => 10 (#digits when zero is at units place) + 10 (#digits when zero is at tens place)
200 - 276 : 3 : 18 => 8 (#digits when zero is at units place) + 10 (#digits when zero is at tens place)
300 - 308 : 3 : 10 => 1 (#digits when zero is at units place) + 9 (#digits when zero is at tens place)
1000- 1008: 4 : 19 => 1 + 9 + 9
现在对于任何给定的范围 1 - N，我希望能够将数字分解为这些范围并使用上述逻辑来计算零的数量。
测试运行：
对于给定的数字 N：
- compute number of digits: len
- if len = 1 : d1: return 0
- len = 2: d2_temp: count # of digits that can possibly occur when 0 is at unit's place
: for e.g. 76: so numbers can be between 10 - 76: (7 - 1) + 1 = 7
: d2: sum(d2_temp, d1)
- len = 3: return d3 : sum(d3_temp, d2)
: compute d3_temp:
: for e.g. n = 308 : get digit at 10^(len-1) : loopMax 3
: d3_temp1: count number of zeros for this loop: 1 * 100 to (loopMax -1) * 100 : (loopMax-1) * 20
: d3_temp2: for n count (#digits when zero is at units place) + (#digits when zero is at tens place)
: d3_temp = d3_temp1 + d3_temp2
让我们尝试概括：
99 : sum( , )
: d3_temp:
: loopMax: n = 99 : n/(10^1) : 9
: d3_temp1: 8 : (9-1) * (10*(len-1)) : (loopMax - 1) * 10 * (len-1)
: d3_temp2: 1 : for len, count #0s in range (loopMax * 10 * (len-1)) to n : count(90, 99)
: d3_temp = 8 + 1
: sum(9, 0)
: 9
从这里开始我遇到了一些麻烦，但这会起作用。