1～n 整数中 1 出现的次数

## 1 题目

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

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

**示例 1：**

```txt
输入：n = 12
输出：5
```

**示例 2：**

```txt
输入：n = 13
输出：6
```

**限制：**

* 1 <= n < 2^31

## 2 问题分析

1. **将 $ 1 \sim n$ 的个位**、**十位**、**百位**、...**的 1 出现次数相加**，**即为 1 出现的总次数**。
2. **设数字 $n$ 是个 $x$ 位数**，**记 $n$ 的第 $i$ 位为 $n_i$**，**则可将 $n$ 写为 $n_xn_{x-1} \cdots n_2n_1$**：

1. **称 $n_i$ 为当前位**，**记为 $cur$**。
   2. **将 $n_{i-1}n_{i-2} \cdots n_2n_1$ 称为低位**，**记为 $low$**。
   3. **将 $n_xn_{x-1} \cdots n_{i+2}n_{i+1}$ 称为高位**，**记为 $high$**。
   4. **将 $ 10^i$ 称为位因子**，**记为 $digit$**。
3. 在**计算某位中 1 出现次数时**，**根据当前位 $cur$ 值的不同**，**分为以下三种情况**：

1. **当 $cur = 0$ 时**，**此位 1 的出现次数只由高位 $high$ 决定**，计算公式为：

$$
      high \times digit
      $$
   1. **当 $cur = 1$ 时**，**此位 1 的出现次数由高位 $high$ 和低位 $low$ 决定**，计算公式为：

$$
      high \times digit + low + 1
      $$
   2. **当 $cur = 2, 3, ..., 9$ 时**，**此位 1 的出现次数只由高位 $high$ 决定**，计算公式为：

$$
      (high + 1) \times digit
      $$
4. **变量递推公式为**：

1. **设计按照个位**、**十位**、...**的顺序计算**，则 $high / cur / low / digit$**应初始化为**：
      1. $high = n / 10$。
      2. $cur = n % 10$。
      3. $low = 0$。
      4. $digit = 1$，即**个位**。
   2. 因此，**从个位到最高位的变量递推公式为**：
      1. $low += cur * digit$，即**将 $cur$ 加入 $low$**，**组成下轮 $low$**。
      2. $cur = high \% 10$，即**下轮 $cur$ 是本轮 $high$ 的最低位**。
      3. $high /= 10$，即**将本轮 $high$ 最低位删除**，**得到下轮 $high$**。
      4. c$digit *= 10$，即**位因子每轮 $\times$ 10**。
5. 具体实例如下：

1. 当 $cur = 0$ 时，以 $n = 2304$ 为例，求 $digit = 10$（即十位）的 1 出现次数：

![Picture1.png](/media/202202/2022-02-09_1609210.5370369541150786.png)
   2. 当 $cur = 1$ 时，以 $n = 2314$ 为例，求 $digit = 10$（即十位）的 1 出现次数：

![Picture2.png](/media/202202/2022-02-09_1610230.41455634163523025.png)
   3. 当 $cur = 2, 3, ..., 9$ 时，以 $n = 2324$ 为例，求 $digit = 10$（即十位）的 1 出现次数：

![Picture3.png](/media/202202/2022-02-09_1611220.4709022428185119.png)

## 3 参考代码

```java
/**
 * 剑指 Offer 43. 1～n 整数中 1 出现的次数
 * @param n 整数
 * @return  1～n 整数中 1 出现的次数
 */
public int countDigitOne(int n) {
    int low = 0, high = n / 10, cur = n % 10, digit = 1, res = 0;

while (high != 0 || cur != 0) {
        //  当 high 和 cur 同时为 0 时，说明已经越过最高位，因此跳出
        if (cur == 0) {res += high * digit;}
        else if (cur == 1) {res += high * digit + low + 1;}
        else {res += (high + 1) * digit;}
        //  将 cur 加入 low，组成下轮 low
        low += cur * digit;
        //  下轮 cur 是本轮 high 的最低位
        cur = high % 10;
        //  将本轮 high 最低位删除，得到下轮 high
        high = high / 10;
        //  位因子每轮 x 10
        digit *= 10;
    }

return res;
}
```

## 参考文献

1. [剑指 Offer 43. 1～n 整数中 1 出现的次数](https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof)。
2. [面试题 43. 1～n 整数中 1 出现的次数（清晰图解）](https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2)。