【刷穿 LeetCode】233. 数字 1 的个数 : 将数位 DP 问题转化为计数类模拟题

题目描述

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

Tag : 「动态规划」、「数位 DP」、「模拟」

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

示例 1：

输入：n = 13
输出：6
复制代码

示例 2：

输入：n = 0
输出：0
复制代码

提示：

• 0 <= n <= 2 * 10^92∗109

基本分析

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

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

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

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

计数类模拟

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

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

举个 🌰，对于一个长度为 mm 的数字 nn，我们可以计算其在「个位（从右起第 11 位）」、「十位（第 22 位）」、「百位（第 33 位）」和「第 mm 位」中 11 出现的次数。

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

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

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

• 当 c = 0c=0，必然不满足「大小要求」，数量为 00；
• 当 c = 1c=1，此时「大小关系」取决于后部分，后面的取值范围为 [0, de][0,de]，数量为 1 * (de + 1)1∗(de+1)；
• 当 c > 1c>1，必然满足「大小关系」，后面的部分可以任意取，即范围为 [0, 99][0,99]，数量为 1 * 1001∗100；

• 当 cc 前面的部分 > ab>ab，必然不满足「大小要求」，数量为 00。

其他数位的分析同理。

代码：

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)
• 空间复杂度：O(m)O(m)

最后

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

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

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

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