LeetCode：数字 1 的个数
题目
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例 1：
1 | 输入：n = 13 |
示例 2：
1 | 输入：n = 0 |
提示：
0 <= n <= 2 * 10^9
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-digit-one
思路
规律如图：个位数、十位数、百位数有1，然后……
代码
Go
代码一（执行超时，不可取）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41package main
import (
"fmt"
"math"
)
func countDigitOne(n int) int {
var r int
for i := 0; i <= n; i++ {
// 尾数是1
if t := i % 10; t == 1 {
fmt.Println(i, "--", t)
r += 1
}
// 十位、百位、千位等
f := float64(i)
for {
if f < 10 {
break
}
if f = math.Floor(f / 10); int(f)%10 == 1 {
r += 1
fmt.Println(i, "::", f)
}
}
}
return r
}
func main() {
// fmt.Println(countDigitOne(13)) // 6
// fmt.Println(countDigitOne(20)) // 12
// fmt.Println(countDigitOne(100)) // 21
// fmt.Println(countDigitOne(110)) // 33
fmt.Println(countDigitOne(824883294)) //
}代码二：参考官方讲解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26package main
import (
"fmt"
"math"
)
func countDigitOne(n int) int {
var r int
for i := 1; i <= n; i *= 10 {
d := i * 10
r += (n/d)*i + int(math.Min(math.Max(float64(n%d-i+1), float64(0)), float64(i)))
}
return r
}
func main() {
fmt.Println(countDigitOne(1))
fmt.Println(countDigitOne(11))
fmt.Println(countDigitOne(21))
fmt.Println(countDigitOne(100))
fmt.Println(countDigitOne(824883294))
}这个逻辑有点复杂。参考官网讲解：https://leetcode-cn.com/problems/number-of-digit-one/solution/shu-zi-1-de-ge-shu-by-leetcode/
