题解 | #整数中1出现的次数

设当前数为abcde...（n位）。由于a是否为1限制了1的出现次数，因此分为最高位与后面的数字两个子问题，可以递归处理。

1. a=1，则a处的1贡献了bcde...+1次（a0000...也算一次）。
2. a>1，则最高位为1时可贡献1000...次。

计算完最高位贡献的1后，递归计算去除最高位后的数字贡献的1即可。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        if (n <= 0) return 0;
        if (n < 10) return 1;
        int high = n, m = 1;
        while (high >= 10) {
            high /= 10;
            m *= 10;
        }
        int last = n - high * m, cnt = high > 1? m: last + 1;
        return cnt + high * NumberOf1Between1AndN_Solution(m - 1) + NumberOf1Between1AndN_Solution(last);
    }
};