# 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 &#x20;

**限制：**

1 <= n < 2^31

注意：本题与主站 233 题相同：https://leetcode-cn.com/problems/number-of-digit-one/

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 二、 分析

#### 2.1 暴力

当然遍历全部数字，进行累加理论上是可行的。但是如果真写出这样的代码就别想通过面试了🤷‍♂️。

#### 2.2 按位分析

我们需要知道一个前提，1出现的次数和就是1在每一位上出现的次数的和。那么我们如何计算出每一位上出现1的次数呢？

下面我们以`310562`为例进行一下分析。

**百位**

我们想知道在这位出现1的次数，我们定义当前位的数字为 `num = 5` ， 其左边的所有数字为 `pre = 310` ， 右边的数字为 `aft = 62` ，当前位为 `base = 100` 。

* 左组合数量：
  * 0 ～ 310
  * pre + 1
* 右组合数量：
  * 0 ～ 99
  * base
    * 因为 1 < 5 ，百位为1时位数足够，可以取到 99
    * 其实就等于当前的`位`，即100

次数 = (pre + 1) \* base

![1](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-4fd2066230c54e83a147fe9d3edeb59bf4ae6dd9%2F43-01.png?alt=media)

**千位**

pre = 31, num = 0, base = 1000, aft = 562

![1](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-3de35cd3508f6418f594851c089fb92539549a7c%2F43-02.png?alt=media)

* 当前位为0，当为1时必须需要前面退位，如上图变化
  * 前范围变为 0 ～ 30
* 左组合数量
  * 0 ～ 30
  * pre
* 右组合数量：
  * 0 ～ 999
  * base

次数 = (pre \* base)

**万位**

pre = 3, num = 1, base = 10000, aft = 0562

![3](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-5f9ad3b0dd6f93449f1a9bc1fec21669926907f4%2F43-03.png?alt=media)

* 当 pre 取 0 ～ 2 时：
  * 左组合数量
    * 0 ～ 2
    * pre
  * 右组合数量：
    * 0 ～ 999
    * base
* 当 pre 取 3 时：
  * 左组合数量
    * 3
    * 1
  * 右组合数量：
    * 0 ～ 562
    * (aft + 1)

次数 = (pre \* base) \* (aft + 1)

**左数 & 右数**

上面将所有三种特殊情况的次数计算方式都推导出来了。剩下推出 pre aft num 的公式即可。

* 根据规律推导出：
  * pre = n / base / 10
  * aft = n % base
  * num = n / base % 10

下面我们就可以根据上面的公式完成遍历的逻辑了。

### 三、 编码

```
func countDigitOne(_ n: Int) -> Int {
    var base = 1
    var sum = 0

    while base <= n {
        let pre = n / base / 10
        let aft = n % base
        let num = n / base % 10
                
        if num == 1 {
            sum += ((pre * base) + (aft + 1))
        }
        else if num == 0 {
            sum += (pre * base)
        }
        else {
            sum += ((pre + 1) * base)
        }
                
        base *= 10
    }
    
    return sum
}
```

![4](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-bdb6c90d6ec439d489102aa01c49f92d93383567%2F43-04.png?alt=media)
