LC 233. 数字 1 的个数

题目描述

这是 LeetCode 上的 233. 数字 1 的个数 ，难度为 困难。

给定一个整数 $n$，计算所有小于等于 $n$ 的非负整数中数字 $1$ 出现的个数。

示例 1：

1
2
3
输入：n = 13

输出：6

示例 2：
1
2
3
输入：n = 0

输出：0

提示：

  • 0 <= n <= $2 * 10^9$

基本分析

这是一道经典的「数位 DP」模板题的简化版，原题在 这里 。

这几天每日一题出得挺好，「序列 DP」、「区间 DP」、「数位 DP」轮着来 🤣

但由于本题只需求 $1$ 出现的次数，而不需要求解 $0$ 到 $9$ 的出现次数，同时意味着不需要考虑统计 $0$ 次数时的前导零边界问题。

因此，也可以不当作数位 DP 题来做，只当作一道计数类模拟题来求解。

计数类模拟

回到本题，我们需要计算 $[1, n]$ 范围内所有数中 $1$ 出现的次数。

我们可以统计 $1$ 在每一位出现的次数，将其累加起来即是答案。

举个 🌰，对于一个长度为 $m$ 的数字 $n$，我们可以计算其在「个位（从右起第 $1$ 位）」、「十位（第 $2$ 位）」、「百位（第 $3$ 位）」和「第 $m$ 位」中 $1$ 出现的次数。

假设有 $n = abcde$，即 $m = 5$，假设我们需要统计第 $3$ 位中 $1$ 出现的次数，即可统计满足 $—1—$ 形式，同时满足 $1 <= —1— <= abcde$ 要求的数有多少个，我们称 $1 <= —1— <= abcde$ 关系为「大小要求」。

我们只需对 $c$ 前后出现的值进行分情况讨论：

  • 当 $c$ 前面的部分 $< ab$，即范围为 $[0, ab)$，此时必然满足「大小要求」，因此后面的部分可以任意取，即范围为 $[0, 99]$。根据「乘法原理」，可得知此时数量为 $ab * 100$；
  • 当 $c$ 前面的部分 $= ab$，这时候「大小关系」主要取决于 $c$：
    • 当 $c = 0$，必然不满足「大小要求」，数量为 $0$；
    • 当 $c = 1$，此时「大小关系」取决于后部分，后面的取值范围为 $[0, de]$，数量为 $1 * (de + 1)$；
    • 当 $c > 1$，必然满足「大小关系」，后面的部分可以任意取，即范围为 $[0, 99]$，数量为 $1 * 100$；
  • 当 $c$ 前面的部分 $> ab$，必然不满足「大小要求」，数量为 $0$。

其他数位的分析同理。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int countDigitOne(int n) {
        String s = String.valueOf(n);
        int m = s.length();
        if (m == 1) return n > 0 ? 1 : 0;
        // 计算第 i 位前缀代表的数值，和后缀代表的数值
        // 例如 abcde 则有 ps[2] = ab; ss[2] = de
        int[] ps = new int[m], ss = new int[m];
        ss[0] = Integer.parseInt(s.substring(1));
        for (int i = 1; i < m - 1; i++) {
            ps[i] = Integer.parseInt(s.substring(0, i));
            ss[i] = Integer.parseInt(s.substring(i + 1));
        }
        ps[m - 1] = Integer.parseInt(s.substring(0, m - 1));
        // 分情况讨论
        int ans = 0;
        for (int i = 0; i < m; i++) {
            // x 为当前位数值，len 为当前位后面长度为多少
            int x = s.charAt(i) - '0', len = m - i - 1;
            int prefix = ps[i], suffix = ss[i];
            int tot = 0;
            tot += prefix * Math.pow(10, len);
            if (x == 0) {
            } else if (x == 1) {
                tot += suffix + 1;
            } else {
                tot += Math.pow(10, len);
            }
            ans += tot;
        }
        return ans;
    }
}

  • 时间复杂度：$O(m)$
  • 空间复杂度：$O(m)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.233 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。