# 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
}
```
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/43.1n-zheng-shu-zhong-1-chu-xian-de-ci-shu.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.