零的数量 给定一个整数 n，请统计从 1 开始，到 n 为止的所有整数的十进制表示中，一共出现了多少个 0？ 例如 n=100 时，1到 100 中，只有以下数字出现过 0： 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 所以总计出现 11 次

要统计从1到n所有整数中出现0的次数，我们可以考虑每个数位上0的贡献。对于每一位（个位、十位、百位等），我们只需要判断当前数是否能被10的相应次方整除。因为只有当个位为0或者是个位以上的数乘以10的倍数时，才会出现0。

这里是一个简单的C++函数，用于计算0的数量：

#include <iostream>

int countZeroes(int n) {
    int count = 0;
    while (n != 0) {
        if (n % 10 == 0) {
            count++;
        }
        n /= 10; // Move to the next digit
    }
    return count;
}

int main() {
    int n = 100;
    std::cout << "Number of zeros from 1 to " << n << ": " << countZeroes(n) << std::endl;
    return 0;
}

这个函数`countZeroes`遍历给定整数n的每一位，如果该位是0，则计数器加1。然后，每次迭代后都除以10，直到n变为0。

相关问题

给定一个整数n(10<n<100),求从1到n这n个整数的十进制表示中1出现的次数，用C语言写代码举例

在C语言中，我们可以使用位运算来计算从1到n这n个整数的二进制表示中1的总出现次数。因为每一位的二进制形式中1的数量等于该位的权重（如果该位为1，则贡献1次，0则不计）。当我们将每个整数转换成二进制并按位相加时，实际上就是累计了所有数字中的1的总数。

以下是一个简单的C函数示例，它实现了这个功能：

#include <stdio.h>

int countOnes(int n) {
    int count = 0;
    while (n > 0) {
        // 将n右移一位相当于除以2，并丢弃余数
        // 通过异或操作得到1的位数，因为1 & 1 == 0，1 ^ 1 == 1
        count += n & 1;
        // 右移一位去掉最低位
        n >>= 1;
    }
    return count;
}

int main() {
    int n;
    printf("Enter a number between 10 and 99: ");
    scanf("%d", &n);
    
    if (n >= 10 && n < 100) {
        int result = countOnes(n);
        printf("The number of 1s in the decimal representation from 1 to %d is %d.\n", n, result);
    } else {
        printf("Invalid input! Please enter a number between 10 and 99.\n");
    }

    return 0;
}

在这个例子中，`countOnes()` 函数通过位运算逐个统计1的出现次数，然后在`main()`函数中获取用户输入并验证范围，最后打印结果。

给定两个正整数 n 和 k，求从 1到 n 这 n个正整数的十进制表示中 k 出现的次数。 输入格式 共一行，包含两个整数 n和 k。 输出格式 输出一个整数，表示答案。

算法1

暴力枚举每个数字的每一位，统计k出现的次数，时间复杂度为O(n*log_10(n))。

时间复杂度

参考文献

Python 代码

C++ 代码

算法2

统计k在每个数位上出现的次数，并累加得到最终答案。以k=3为例，假设当前处理的是x，x的第i位为di。有以下三种情况：

- di>k，则di可以取0~9中任意一个数字，共10^(i-1)种情况，其中i表示第i位，10^(i-1)表示该数位前(i-1)位共有10^(i-1)种情况。
- di<k，则第i位只能取0~di-1中的数字，如果i=1，则0不能出现，共di*(10^(i-1))种情况。
- di=k，则第i位只能取0~di-1中的数字，共(dk-1)*(10^(i-1)) + x%(10^(i-1))+1种情况，其中x%(10^(i-1))表示当前数位前(i-1)位的数字共有x%(10^(i-1))+1种情况，因为x前(i-1)位的数字可以取0~(x%(10^(i-1)))。

注意到以上三种情况中第一种情况和第二种情况可以合并成一个公式，故最终的公式为：

ans = ∑i=1 ^ len(n)[(n // (10^i))*10^(i-1)+min(max(n%(10^i)−k+1,0),10^(i−1))−(k==0)*10^(i−1)]
其中，n // (10^i)表示取n的前i位数字，max(n%(10^i)−k+1,0)表示取n的第i位数字时，能取到的范围。注意当k=0时，第二项需要减去10^(i-1)。

时间复杂度

参考文献

Python 代码

C++ 代码

算法3

对于每一位数位上出现k的次数进行统计。根据数位的不同分类具体处理，具体如下：

- 如果k=0，则枚举当前数位，次数为n/10^(i+1)*10^i，表示高位上数位1~n/10^(i+1)共可以变化10^i种，其中i表示数位从右数第x位，不包含本位（假设最低位为第0位）上的前缀0。

Python 代码

C++ 代码

- 如果当前位数字是k，则统计方式分为三种：

- 如果该位数字为0，则次数为前面数位（不包括本身）0~n/10^(i+1)的个数
- 如果该位数字不为0，则次数为前面数位（不包括本身）0~n/10^(i+1)的个数+1
- 如果i=0,即当前位为最低位且为k，则次数为1

Python 代码

C++ 代码

- 如果当前位数字小于k，则次数为前面数位（不包括本身）0~n/10^(i+1)的个数
- 如果当前位数字大于k，则次数为前面数位（不包括本身）0~n/10^(i+1)的个数+1
于是有以下代码

时间复杂度

参考文献

Python 代码

C++ 代码