题目
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字 有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化, 可以很快的求出任意非负整数区间中1出现的次数。
分析
其实就是找规律，从高位到底为或者从低位到高位，一位一位的计算1出现的个数。
举个例子进行分析551
我们知道1出现的情况是0-9进行了一个循环，例如从1-10，从1累加到10，就又会出现一个1.
因此，首先考虑个位：
很明显，假如是550，各位就一共出现了55次，由各位的高位决定，如果是551，那么是55 + 1，由各位的高位和个他本真决定，如果是552，那么也是55 + 1
再看十位：
我们先分析502，也就是十位是0的情况，出现的次数是 10-19，110-119、210-219、310-319、410-419，总共出现了50次，也就是 百位*10。
我们再分析512，出现的次数是：10-19，110-119、210-219、310-319、410-419、510 - 512，总共50 + 3
也是当十位是1的时候，决定个数的十位的高位和个位。
以后的位数都是以此类推的分析。
代码
public class offer30 {
public static void main(String[] args) {
offer30 offer30 = new offer30();
System.out.println(offer30.NumberOf1Between1AndN_Solution(5));
}
public int NumberOf1Between1AndN_Solution(int n) {
if(n <= 0)
return 0;
// 当前的位数，1、10、100.
int base = 1;
// 记录1的综述
int countOf1 = 0;
// 从个位开始得到每一位的数
while ((n / base) != 0) {
// 当前的位数上的数
int current = (n /base)%10;
// 高位的数
int high = n /(base *10);
// 低位的数
int low = n - (n/base) * base;
// 如果当前位等于0，出现1的次数由高位决定
if (current == 0) {
countOf1 = countOf1 + high * base;
}else{
// 如果当前位>0
if (current == 1) {// 当前位是1,1的个数由高位和低位决定，为high*10 + 低位 + 1
countOf1 += high * base + low +1;
}else{
// 如果当前位>1，1的个数由高位，决定
// 为 (high + 1) *base
countOf1 += base * (high + 1);
}
}
base = base * 10;
}
return countOf1;
}
}
