[233][困难] 数字1的个数

解题思路

233. 数字 1 的个数 剑指 Offer 43. 1～n整数中1出现的次数

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：

输入：n = 12
输出：5

示例 2：

输入：n = 13
输出：6

限制：

• $1 \le n \lt 2^{31}$

解题思路

Leetcode官方题解: 数字 1 的个数

首先统一符号用法, 使用$i$表示位置, 个位时$i=1$, 十位时$i=10$, 依次类推.

以个位切入, 对于一个数字, 个位上的1, 每隔10个数就会出现一次; 十位上的1, 每隔100个数就会出现一次. 因此对于数字$n$, 位数$i$上的1出现的次数为$n // (i * 10)$, 当这个$i$位置上出现1时, 对应的就有$i$的数字在$i$位置上1, 因此这部分$i$出现的总数量为$(n // (i * 10)) * i$次.

例如对于数字315的十位数, $(355 // (10 * 10)) * 10 = 30$, 代表的就是10, 11, ..., 110, 111, ..., 210, 211, ...这些数字. 我们只看十位上1的数量, 因为个位数的1数量已经在上一步计算过了, 百位数的1还要等到下一次循环计算.

但同时也可以看到, $355 // (10 * 10)$的整除结果为3, 对应上面的30个数字, 这些数字需要考虑百位为0的情况, 3这个结果, 对应的分别是百位为0, 1, 2的结果, 是不包含百位为3的结果的.

百位为3的结果是我们计算十位时另外要考虑的一部分. 百位为3可以看做剩余的一部分, 之前的0, 1, 2分别覆盖了0~99, 100~199, 200~299的数字, 使用上面的公式就能计算得出, 但对于百位为3的情况, 很可能做不到覆盖300~399, 这部分需要单独考虑.

此时我们还是在考虑十位数, 且十位数为1有多少数字. 对于百位为3, 十位为1的情况, 如果$n \lt 310$, 百位为3这部分就没有贡献; 如果$310 \le n \lt 319$, 这部分的贡献就是$n \ \text{mod} \ (i * 10) - i + 1$, 其中的$+1$考虑的是310的情况; 如果$n \ge 320$, 对应的数量就是10, 即$i$.

因此, 根据上面三种情况, 这部分十位数为1对应的数字数量为$\min(\max(n \ \text{mod} \ (i * 10) - i + 1,\ 0),\ i)$.

因此我们从个位1, 向上循环, 十位百位千位等等, 因此考虑每个位置上为1的情况, 然后只记录此种情况下, 对应的这个位置上1的数量, 这样可以做到对1的统计相互不冲突. 对于11这个数字, 个位数上的1在对个位数计算时被统计, 十位上的1在十位计算时被统计, 一个数字不同位置的1在循环到对应的不同位数时被分别统计.

而每个位数对应的1的数量为:

$(n // (i * 10)) * i + \min(\max(n \ \text{mod} \ (i * 10) - i + 1,\ 0),\ i)$

class Solution:
    def countDigitOne(self, n: int) -> int:
        if n <= 0:
            return 0

        i, res = 1, 0
        while 1:
            res += min(i, max(n % (i * 10) - i + 1, 0))
            res += n // (i * 10) * i
            if n // (i * 10) == 0:
                break
            i *= 10

        return res