# 题目链接
# 题目描述
输入一个整数 n ,求1~n这n个整数的十进制表示中1出现的次数。
例如,输入12,1~12这些整数中包含1 的数字有1、10、11和12,1一共出现了5次。
示例 1:
输入:n = 12
输出:5
1
2
2
示例 2:
输入:n = 13
输出:6
1
2
2
# 解题思路
掌握数学规律,把n分成三部分,high,cur,low三个区域。还有一个digit位级。每完成一次。三个区域和位级都发生变化。直到cur走完全过程
func countDigitOne(n int) int {
// 这里 digitNum 为 digit 所在位 对应的可能性
// 其实位为个位 因此 digitNum = 1 1乘以任何数 = 任何数
digitNum, sum := 1, 0
high, cur, low := n/10, n%10, 0
for high != 0 || cur != 0 {
// 固定位 计算数量
if cur < 1 {
sum += high * digitNum
} else if cur == 1 {
sum += high*digitNum + low + 1
} else {
sum += (high + 1) * digitNum
}
// 换下一位 更新高低位 及digit数量级
low = low + cur*digitNum
high, cur = high/10, high%10 //这里 cur 是等于 前一个 high 模10
digitNum = digitNum * 10
}
return sum
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21