剑指offer.30.整数中1出现的次数（从1到n整数中1出现的次数）

刷剑指Offer的时候发现了一个很巧妙的做法
咩咩很多时候喜欢去钻研计算机的算法与数学做法的结合 换句话说 咩咩喜欢直接手算推出公式再丢给电脑去算出结果
真是奇怪的程序员

话不多说，先把题目抛出来：

求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

我第一反应的解法当然是哈哈哈哈把数字变成字符然后暴力遍历（我真的配当程序员吗）

而这位先生的做法是->

public int NumberOf1Between1AndN_Solution(int n) {
    int cnt = 0;
    for (int m = 1; m <= n; m *= 10) {
        int a = n / m, b = n % m;
        cnt += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);
    }
    return cnt;
}

思路是分别计算个位、十位、百位…上出现 1 的个数。
以n=216举例：
首先统计个位数上有多少个1，有1,11,21,31,41,51，…201,211；
一共是22个 // 这里22=(216/10)+1个1；
接着是统计十位数上有多少个1,10-19一共10个，110-119一共10个，210-216一共7个。一共是27个 这里的27个是怎么来的呢 首先我们可以得出每100个数会出现10个类似10-19这样的数，那么显然，之前我们得到了的（216/10）告诉我们一共有21个“10”，也就是有 “（21/10）* 10” 一共20个数，另外7个另外单独考虑。这里我们可以用a=216，a%10+1=7来求出最后7个
注意，这里就会发现，前面我们求个位的22个时，最后剩下的211我们可以给216加8进位去获得，有的同学会问为什么不加9，这里就是保证不出现211+9=220,220%10=0这种干扰判断的情况。
接着是百位，当个位十位处理得当，其实百位没有什么太大的问题了，直接把100-199的100个数算出来即可，也就是a=216/100=2,b=216%100=16
((a + 8) / 10) * m=10/10*100=100
注意这里我们可以发现，如果a+8不到进位条件，换句话说（a+8）/10=0，举个例子，n=164，这里的百位的1应当是65个，则65=b+1=64+1
环环相扣，非常巧妙。