# 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 <= n < 2^31
注意：本题与主站 233 题相同：
来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
### 二、 分析
#### 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
**千位**
pre = 31, num = 0, base = 1000, aft = 562
* 当前位为0，当为1时必须需要前面退位，如上图变化
* 前范围变为 0 ～ 30
* 左组合数量
* 0 ～ 30
* pre
* 右组合数量：
* 0 ～ 999
* base
次数 = (pre \* base)
**万位**
pre = 3, num = 1, base = 10000, aft = 0562
* 当 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
}
```
