描述

输入一个整数 n ，求 1～n 这 n 个整数的十进制表示中 1 出现的次数
例如， 1~13 中包含 1 的数字有 1 、 10 、 11 、 12 、 13 因此共出现 6 次

注意：11 这种情况算两次

数据范围： 1≤n≤30000

进阶：空间复杂度 O(1) ，时间复杂度 O(lognn)

示例

// 输入：
13
// 返回值：
6

// 输入：
0
// 返回值：
0

解题思路

最简单的方法是依次遍历，判断每个数中存在的 1 的数量相加，但是复杂度较大

仔细观察本题，可以发现其实是一道数学找规律的题目

首先，如果我们修改下题目，如果要找出 1 到 n 中百位数上 1 出现的次数？那么，则可以推导：

// 假设：n = 12013
12013            12113            12213            12313
------            ------            ------            ------
100 ~ 199        100 ~ 199        100 ~ 199        100 ~ 199
1100 ~ 1199        1100 ~ 1199        1100 ~ 1199        1100 ~ 1199
2100 ~ 2199        2100 ~ 2199        2100 ~ 2199        2100 ~ 2199
...                ...                ...                ...
9100 ~ 9199        9100 ~ 9199        9100 ~ 9199        9100 ~ 9199
10100 ~ 10199    10100 ~ 10199    10100 ~ 10199    10100 ~ 10199
11100 ~ 11199    11100 ~ 11199    11100 ~ 11199    11100 ~ 11199
                12100 ~ 12113    12100 ~ 12199    12100 ~ 12199
+                +                +                +
------            ------            ------            ------
12*100            12*100+13+1        (12+1)*100        (12+1)*100

// 从上推到可以发现：百位上 1 出现的次数受百位前的高位 12 个低位 13 的影响，规律如下：
假设：高位=high 当前百位=cur 低位=low
- 当 cur == 0 时：count = high * 100
- 当 cur == 1 时：count = high * 100 + low + 1
- 当 cur > 1 时：count = (high + 1) * 100

已知百位上 1 出现的次数，则可以将百位位数左右移动，也可以知道各位、十位中 1 出现的次数，将以上的 100 改为 i*10（1、10、100、...）

则有：

- 当 cur == 0 时：count = high * i * 10
- 当 cur == 1 时：count = high * i * 10 + low + 1
- 当 cur > 1 时：count = (high + 1) * i *10)

代码实现

/**
 * [JZ43-中等] 从 1 到 n 整数中 1 出现的次数
 *
 * @param n int整型
 * @return int整型
 */
func numOfOneFromInt(n int) int {
    i, count, high, cur, low := 1, 0, 0, 0, 0
    for i <= n {
        // 取高位
        high = n / (i * 10)
        // 取当前位
        cur = (n / i) % 10
        // 取低位
        low = n - n/i*i
        if cur == 0 {
            count += high * i
        } else if cur == 1 {
            count += high*i + low + 1
        } else {
            count += (high + 1) * i
        }
        i *= 10
    }
    return count
}