求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
我的解法：
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
if(n<=0) return 0;
return NumberOf1Between1AndN_Solution(n-1) + f(n);
}
public int f(int n){
int sum = 0;
while(n>0){
if(n%10 == 1) sum ++;
n = n/10;
}
return sum;
}
}
写下这几行代码，我就知道肯定有更好的解法。类似于配列组合，确定其中一位，来推断其规律。想了想，好像确定的这位数为0,1还是大于1都会影响。放弃了，看了答案，看来自己的方向没有错，只是没想明白。
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
// 12$22
// 只考虑百分位$
// 定义12 为before
// 定义22 为after
// 如果$是0，12022
// before = 12 时候，121 > 120 舍去
// 总数 = （11+1）x(99+1) = 1200
// 如果$是1,12122
// before = 12 时候，after有 22+1 个选择
// before < 12 时候，（11+1）x(99+1)
// 总共 = 1223
// 如果$ > 1,比如12722
// before = 12 时候，after有 0~99 一共一百个选择
// 总共 = 13x100 = 1300种
int sum = 0;
int before;
int after;
int current;
// 从个位开始计算
for (int i = 1; i <= n; i *= 10) {
before = n / (i * 10); // 当最高位的时候，before为0
after = n % i; // 当个位的时候after为空，即为0,
current = (n / i) % 10;
if (current == 0) {
sum += before * i;
} else if (current == 1) {
sum += before * i + after + 1;
} else {
sum += (before + 1) * i;
}
}
return sum;
}
}
