[数据结构与算法]LeetCode 233. Number of Digit One【计数模拟】困难

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，这个截止期限可能是永远。

在这一系列刷题文章中，不仅讲解多种解体思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时还会总结相应的算法模板。为了方便在PC上运行调试、分享代码文件，我还将建立相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目总结、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Example 1:

Input: n = 13
Output: 6

Example 2:

Input: n = 0
Output: 0

Constraints:

• 0 <= n <= 109

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

解法 数位DP简化的计数模拟

这一题其实是简化版，是一道「数位DP」模板题P1980 [NOIP2013 普及组] 计数问题的简化，不过那道NOIP题效率最高的解法也还是计数模拟，见这篇文章。做过那道题后再做这道题，会轻松很多。

回到本题，是时候重温计数原理了：

• 加法原理：简单来说就是分类。做一件事情，完成它有不重不漏的 $n$ 大类解法，第一大类有 $m_1$ 种方法，第二大类有 $m_2$ 种方法，……，第 $n$ 大类有 $m_n$ 种方法，那么完成这件事共有 $m_1+m_2+\dots \dots +m_n$ 种方法。
• 乘法原理：简单来说就是分步。做第一步有 $m_1$ 种不同的方法，做第二步有 $m_2$ 种不同的方法，……，做第 $n$ 步有 $m_n$ 种不同的方法。那么完成这件事共有 $m_1\times m_2\times m_3\times \dots \times m_n$ 种不同的方法。

本题计算 $[1,n]$ 的所有整数中 $1$ 出现的个数，主要运用加法分类原理，即分别计算所有整数中出现在个位、十位、百位……的 $1$ 的个数，然后加总得到结果。现在的问题是，如何统计 $1$ 在第 $i$ 位出现的次数？

假设一个五位的数 $n=abcde$ ，我们需要统计第 $3$ 位中 $1$ 出现的次数，即计算满足 $\_\_1\_\_$ 形式且 $1\le \_\_1\_\_\le abcde$ 的整数有多少个，我们将这一条件简称为「限定」。下面主要对 $c$ 的大小（和 $c$ 前一部分的大小）进行分类讨论：

• 当 $c>1$ 时：
  • $c$ 前一部分 $<ab$ 时，即范围为 $[0,ab)$ ，必然满足「限定」，因此后一部分可以任意取值，范围为 $[0,99]$ 。根据乘法原理，此时第 $3$ 位中 $1$ 出现的次数加上 $ab?100$ ；
  • $c$ 前一部分 $=ab$ 时，由于 $c>1$ ，也必然满足「限定」，因此后一部分可以任意取值，范围为 $[0,99]$ ，此时第 $3$ 位中 $1$ 出现的次数加上 $100$ ；
  • $c$ 前一部分 $>ab$ 时，必然不满足「限定」。
• 当 $c=1$ 时：
  • $c$ 前一部分 $<ab$ 时，即范围为 $[0,ab)$ ，必然满足「限定」，因此后一部分可以任意取值，范围为 $[0,99]$ 。根据乘法原理，此时第 $3$ 位中 $1$ 出现的次数加上 $ab?100$ ；
  • $c$ 前一部分 $=ab$ 时，由于 $c=1$ ，只有后一部分取值在范围 $[0,de]$ 时才满足「限定」，此时第 $3$ 位中 $1$ 出现的次数加上 $de+1$ ；
  • $c$ 前一部分 $>ab$ 时，必然不满足「限定」。
• 当 $c=0$ 时:
  • $c$ 前一部分 $<ab$ 时，即范围为 $[0,ab)$ ，必然满足「限定」，因此后一部分可以任意取值，范围为 $[0,99]$ 。根据乘法原理，此时第 $3$ 位中 $1$ 出现的次数加上 $ab?100$ ；
  • $c$ 前一部分 $=ab$ 时，由于 $c=0$ ，无论后一部分如何取值，都不能满足「限定」；
  • $c$ 前一部分 $>ab$ 时，必然不满足「限定」。

或者主要对 $c$ 前一部分的大小进行分类讨论，简要归纳如下：

• $c$ 前一部分 $<ab$ 时，无论如何都满足「限定」，因此后一部分可以任意取值，此时第 $3$ 位中 $1$ 出现的次数加上 $ab?100$ ；
• $c$ 前一部分 $=ab$ 时，是否满足「限定」取决于 $c$ 的大小：
  • $c>1$ 时，必然满足「限定」，因此后一部分可以任意取值，此时第 $3$ 位中 $1$ 出现的次数加上 $100$ ；
  • $c=1$ 时，只有后一部分取值在范围 $[0,de]$ 时才满足「限定」，此时第 $3$ 位中 $1$ 出现的次数加上 $de+1$ ；
  • $c=0$ 时，无论后一部分如何取值，都不能满足「限定」；
• $c$ 前一部分 $>ab$ 时，必然不满足「限定」。

最后实现的代码如下：

class Solution {
public:
    int countDigitOne(int n) { 
        int ans = 0;
        long long r = 1;
        while (r <= n) { //分别计算个、十、百......千位上1出现的次数,再求和
            int a = n / (r * 10), b = n / r % 10, c = n % r;
            switch (b) {
                case 0: ans += a * r; break;
                case 1: ans += a * r + c + 1; break;
                default: ans += (a + 1) * r; break;
            }
            r *= 10; //不然r可能溢出
        } 
        return ans;
    } 
};

时间复杂度为 $O(\lg n)$ ，空间复杂度为 $O(1)$ 。运行效率如下：

执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户
内存消耗：5.8 MB, 在所有 C++ 提交中击败了73.12% 的用户