数1的个数

题意

把 $1$ 到 $n$ 的所有整数写出，统计其中数字 1 总共出现多少次。

思路

数据范围只有 $10000$ ，逐个枚举即可。对每个数转换为字符串，count("1") 给出它内部数字 1 的出现次数，再用生成器表达式求和。

代码

Python代码

python

1
2
3limit = int(input())
answer = sum(str(number).count("1") for number in range(1, limit + 1))
print(answer)

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#include <cstdio>


int main(){
    int i,n;
    int cnt=0;
    scanf("%d",&n);
    for (i=1;i<=n;i++){
        int t= i;
        while( t != 0){
            int a = t % 10;
            if( a == 1){
                cnt++;
            }
            t /= 10;
        }
    }
    printf("%d\n",cnt);
    return 0;
}

复杂度

设 $n$ 的十进制位数为 $d$ ，时间复杂度为 $O(nd)$ ，额外空间复杂度为 $O(d)$ 。

总结

范围较小时，枚举每个数并统计其字符串字符数，是可靠且易读的数位统计方法。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结