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

题目描述

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

思路：
针对判定位是0,1，2-9，三种情况讨论。
1.判定位是0：举例12012，百位是0，则当百位是1的时候，百位前的数字范围是0-11，共12种；百位后的数字范围是0-99，共100种。因此百位是0的时候，共12100种。
2.判定位是1：举例12012，十位是1，则当十位是1的时候，十位前的数字范围是0-119，共120种；十位后的数字范围是0-9，共10种。特例，因为十位是1，存在前面是120的时候，后面只能是0-2共三种，因此额外加上3种。共12010+3种
3.判定位是2-9：举例12012.千位是2，则当千位是1的时候，千位前的数字范围0-1，共两种；千位后的数字范围0-999，共1000种。总计2*1000种

总结规律：
公式为x*y+z——x代表当前位之前的数目总计，y代表当前位之后的数目总计，z代表特殊情况数目统计。
判定位0：x=前面数位，y=10^后面的位数，z=0
判定位1：x=前面数位，y=10^后面的位数，z=后面具体数字+1（代表0到在这个数字总计个数）
判定位2-9：x=前面数位+1（包含0到当前数字总计个数），y=10^后面的位数，z=0

公式总结
(a+8)/10m +(a%10 == 1?1:0)(b+1)
a代表当前位之前的数，b代表当前位之后的数
+8之后/10解决了0,1和2-9对于x*y之间的区别

代码：

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