剑指Offer30 Count One

求出1_{13的整数中1出现的次数,并算出100}1300的整数中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;
    }
}