数字统计

题意

统计闭区间 $[L,R]$ 中的所有整数里，数字 2 出现的总次数。

思路

遍历 range(left, right + 1)，端点 right + 1 保证右端点被包含。每个数转为字符串后，count("2") 统计本数贡献，最后累加。

代码

Python代码

python

1
2
3left, right = map(int, input().split())
answer = sum(str(number).count("2") for number in range(left, right + 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,l,r;
    int cnt=0;
    scanf("%d%d",&l,&r);
    for (i=l;i<=r;i++){
        int t= i;
        while( t != 0){
            int a = t % 10;
            if( a == 2){
                cnt++;
            }
            t /= 10;
        }
    }
    printf("%d\n",cnt);
    return 0;
}

复杂度

设区间长度为 $s$ 、其中数的位数最多为 $d$ ，时间复杂度为 $O(sd)$ ，额外空间复杂度为 $O(d)$ 。

总结

计数区间题先确认是闭区间，再把右端点加一传给 Python 的 range。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结