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

解题思路：

我们看到题目要求 “输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数”。其实就是求从1-n这n个数中，每一个数的计数位上出现的1的个数的总和。

所以我们只需要知道在某个计数位上面1出现次数的计算方法即可求解这道题目，下面我们分为几种情况讨论：

1、当前位上的值等于0

我们可以看到当前位为百位，即base = 100；当前位上的数为cur = 0，此时为什么需要借位呢？

因为当cur为0的时候，后面的b即使取0-36的任何一个数，cur都不可能出现1，永远都是0。

所以需要向前借位，借位后cur才能有为1的情况，当cur借到位的时候，将cur变为1，此时我们就可以去计算1出现的个数了。

此时a的取值范围为 0-513，然后b的范围为0-99。0-513这个好理解，因为被cur借去了一位，但是b不是刚开始只能取0-36吗？为什么就能够变成0-99呢？我们看到，当cur向前借位的时候，cur是可以取0-9任意一个数的，因为我们就是想让cur为1，所以cur这一位完全可以提供给后面的借位，所以b的取值可以为 0-99。

好了，上面说了那么多，此时这种情况下，1出现的次数怎么算呢？

我们可以转化为这么想，当cur为1的时候，最多能够生成多少个cur为1的数呢？不就是cur前面能变换的个数乘上后面能变换的个数吗？

所以n = 514036的时候，cur为1出现的次数 res = a * base。

2、当前位上的值等于1时

我们可以从上图很清楚的看到，此时cur=1，并且当a为514的时候，b只能取0-36，此时 res1 = 1 * (b+1)

当a取值 0-519 的时候，b就能够取 0-99 。此时 res2 = a * base

所以总的就为 res = res1 + res2

3、当前位上的值大于1时

我们可以得到a和b的取值范围，至于b为什么又是0-99而不是0-36，解释跟上面一样。

所以 res = (a+1) * base（tips : 0-514 为 a+1 个数）

因此，我们可以按照上面的思路书写代码啦~

代码
Java版

public int NumberOf1Between1AndN_Solution(int n) {
        // 从个位数开始
        int base = 1;
        // 总的出现1的次数现在为 0
        int res = 0;
        // 不能超过n
        while(base <= n){
            // 求出当前位 ，高位，低位
            int cur = n/base%10;
            int a = n/base/10;
            int b = n%base;

            // 分三类情况讨论，对应上面解释的三种情况
            if(cur > 1)
                res += (a+1)*base;
            else if(cur == 0)
                res += a*base;
            else res += a*base+b+1;
            base *= 10; // 位数向前移一位
        }
        return res; // 最后得到全部出现1的次数，返回
    }

golang版

func NumberOf1Between1AndN_Solution( n int ) int {
    // write code here
    // 从个位数开始
    base,res := 1,0
    for base <= n {
        // 当前位
        cur := n/base%10
        // 高位
        a := n/base/10
        // 低位
        b := n%base

        // 对应三种情况
        if cur > 1 {
           res += (a+1)*base
        }else if cur == 0 {
           res = res + a*base
        }else{ res = res + a*base+b+1}
        base *= 10
    }
    return res
}

复杂度分析：
时间复杂度 ： 循环次数为数字n的位数，所以为 ，即时间复杂度为 。
空间复杂度 ： 常量的空间。