> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/shu-xue/233-shu-zi-1-de-ge-shu.md).

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

## 解题思路

[233. 数字 1 的个数](https://leetcode-cn.com/problems/number-of-digit-one/) [剑指 Offer 43. 1～n整数中1出现的次数](https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/)

输入一个整数 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 的个数](https://leetcode-cn.com/problems/number-of-digit-one/solution/shu-zi-1-de-ge-shu-by-leetcode/)

首先统一符号用法, 使用$$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)$$

```python
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
```