找规律

题目链接-来源：力扣（LeetCode）

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：

输入：n = 12
输出：5

思路：

将数字转换为字符串暴力计数会超出时间限制，所以只能期待通过数学规律计算出某个数字包含的 ‘1’ 的个数。
计数 ‘1’ 的难点，或者说计数任何一个数码的难点在于，数码在不同数字范围内出现的「密度」不同，例如，对于11 ~ 19，每个数字都至少出现一个 ‘1’ ，而21 ~ 29，则只出现了1次1，使得我们很难按序去计数。
我们换个角度思考，如果数字大小已经确定了，我们是否可以确定地，统计其每一个十进制位的 ‘1’ 的个数，然后累加呢？答案是肯定的。
例如，我们考察十位，任取一个数，XX3Y，那么这个数字个位出现 ‘1’ 的数字，从 0010 ~ XX19，主要取决于 XX 的大小。而最终有多少次，还取决于这位数字本身和Y的大小，由于是 ‘3’ ，我们知道肯定会经过 ‘1’，所以需要多计数一次。
最终，我们可以确定如下规则，记高位为 high，当前位为 cur，低位为low，当 cur 为 ‘0’ 时，我们要回退到 “high - 1” + “1” + “9…9”的情况，此时 cur 位共出现 high * digit (digit 为cur 位对应的进制数，即低位从0 ~ 99…9 共计digit种情况，而高位从 0 ~ high - 1 共计 high 种情况)；当 cur 为 ‘1’，相比于 ‘0’ 的情况，’1’ 在每个low出现时都会被多统计一次，因此要加上从 0 ~ low 共计 low + 1 个数字；而当 cur 为 ‘2’~’9’时，不会引入额外的’1’，因此最终 ‘1’ 的个数就是 (high + 1) * dight。
对每一位，我们都进行类似的统计，最后累加的结果就是所需要的 ‘1’ 的个数。
时间复杂度：O(logn)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int countDigitOne(int n) {
        int count = 0, high = n / 10, cur = n % 10, low = 0, digit = 1;
        while (low < n) {
            if (cur == 0) {
                count += high * digit;
            } else if (cur == 1) {
                count += high * digit + low + 1;
            } else {
                count += (high + 1) * digit;
            }
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return count;
    }
}