LeetCode[23] Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all
non-negative integers less than or equal to n.

For example: Given n = 13, Return 6, because digit 1 occurred in the
following numbers: 1, 10, 11, 12, 13.

递归

复杂度
O(N), ? O(1)

思路
每次将一个数拆分成两部分考虑，并考虑当前最高是不是1.
比如115，将数拆分成，15和0-100，这两部分分别计算。
如果最高位是1的数，那么一定会包括 100-115这16个数，除了那两部分之外。
每次抹去高位，观察重复情况。

代码

public int countDigitOne(int n) {
    if(n < 10) {
        return n > 0 ? 1 : 0;
    }
    // count代表位数，num代表最高的值
    int level = 10, num = 0;
    int count = 0;
    // integer overflow;
    while(n / level >= 10) {
        level *= 10;
    }
    num = n / level;
    //
    if(num == 1) {
        count += (n - level + 1) + countDigitOne(level - 1);
    }
    else if(num > 1) {
        count += num * countDigitOne(level - 1) + level;
    }
    // 除了高位的剩余部分；
    count += countDigitOne(n - level * num);
    return count;
    //return level;
}