P4353 数1的个数（【基础】）

解题思路

要把 $1$ 到 $n$ 每个数里"数字 1"出现的次数都数出来。怎么数一个数里有几个 1？用两个操作：

• t % 10 取出 $t$ 的个位，看看是不是 1；
• t / 10 把 $t$ 的个位去掉，剩下前面的数。

把这两个操作放在一个 while 循环里，循环到 $t$ 变成 0 为止，就能把 $t$ 的每一位都检查一遍。外层再用一个 for 循环从 1 走到 $n$，每数到一个 1 就把计数器 cnt 加 1。

拿样例 $n=12$ 来说，数到 $11$ 时：个位是 1 数一次，去掉个位还剩 1，再数一次，所以 11 贡献了 2 个 1；$10$ 贡献 1 个，$1$ 贡献 1 个，$12$ 个位是 2 没有 1。一共 $1+1+2+1=5$ 个，和样例一致。

边界情况：数字 1 本身贡献 1 个；数字 111 里有三个 1，贡献 3 个。$n$ 最大 10000，每个数最多拆 5 位，循环次数很少，不会超时。

参考代码

// 统计从1到n所有整数里数字1出现的次数
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        int t = i;
        while (t) {          // 把t的每一位拆出来检查
            if (t % 10 == 1) cnt++;   // 个位是1
            t /= 10;                  // 去掉个位
        }
    }
    cout << cnt << endl;
    return 0;
}

复杂度分析

$n$ 最大 10000，每个数最多拆 5 位，总共大约 5 万次检查，所以时间复杂度是 $O(n \times 位数)$。只用了几个整数变量，没有用数组，额外空间复杂度是 $O(1)$。