题解 | #整数中1出现的次数（从1到n整数中1出现的次数）#

时间复杂度，或者说是n的位数。理论上应该是最优的时间复杂度了，主要方法就是 dp 递推。

当然也可以用递归实现效率也不会太差，因为没有重复计算子问题。这里使用循环实现的。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        if(n==0)
            return 0;
        // 结果
        int res=0;
        // n 为现在遍历到的位数对应的 10 的指数，从个位开始到最高位 0, 1，2...
        // div 为 10^n，div可由 div*=10递推得到
        int div = 1;
        //  ten1^n 为 < 10^n 中所有 1 的个数，由10^(n-1)
        // 可以两部分
        // 1. 由于10^n位是由10^(n-1)+1 个数得到的，所以新加一位后，从 0~9 有 9 个数，这个部分贡献的 1 的个数为 10*ten1^{n-1}
        // 2. 第n位中会出现一个 1，后跟0~10^{n-1}-1 中所有的数，所以这个n位 1 会出现10^{n-1}次
        // 由此可得 ten^n=0; tenn^n=10*tenn^{n-1}+10^{n-1};
        int tenn=0; 
        // qui 和 mod 用于获得第 n 位的数值，qui 为第n位上的值
        // mod = n % (10*div);
        // qui = mod / div;
        int qui, mod;
        // 整体思路如下
        // 若现在已有 n 位之前所有 1 出现的个数res，则到n位时 1 有3 部分贡献
        // 1. 全 10 次方贡献： 0~qui 中有 qui 个 tenn^{n}，这部分的贡献为 qui*tenn^{n}
        // 2. qui 后接的不足 10^n的值，贡献为 res
        // 3. 第 n 位 1 出现次数
        //     1. 若 qui==0, 不考虑这个贡献
        //     2. 若 qui==1, 则0~n-1位所有值都会贡献一个 1，贡献(input n %div)+1个 1
        //     3. 若 qui>1，则贡献10^n 个 1
        while(n/div){
            mod = n % (10*div);
            qui = mod / div;
            if(qui==1){
                res = tenn+res+(n%div)+1; // 对应 1， 2， 3.2
            }
            else if(qui>0){
                res= qui*tenn+div+res; // 对应 1，2，3.3
            }
            tenn=10*tenn+div;
            div*=10;
        }
        return res;
    }
};