描述：

N为大于1的整数。从1到N，求出数字1出现的个数。比如 N=13 时，包含1的数有1、10、11、12、13，则1出现的个数为6。

这道题目是剑指offer上的一道题的变种。其实我个人认为这种类似于脑筋急转弯的题目除了能够考量一个人的智商或积累之外，在平时工作中意义不大。不过既然面试可能会问到，我们还是来分析一下这道题目。

暴力解法

暴力解法思路很简单，对每一个数，判断其包含多少个1。唯一要注意的一点是，根据 N 可能的上限，要选择合适的数据类型，否则可能会溢出。

   public static void main(String[] args) {
        long n = 13;
        int cnt = 0;

        for (int i = 1; i <= n; i++) {
            cnt += count(i);
        }

        System.out.println(cnt);
    }

    static int count(long number) {
        int cnt = 0;
        while (number > 0) {
            cnt += number % 10 == 1 ? 1 : 0;
            number /= 10;
        }
        return cnt;
    }

对于暴力解法，时间复杂度为nlogn，其实我个人觉得也没啥问题。不过还是有很多人提出了更多更好的方法。

基于数字找规律

这种方法我个人认为还是比较友善的，理解和编程实现都比较简单，按每一位来考虑：

1. 此位大于1，这一位上1的个数有 ([n / 10 ^ (b + 1) ] + 1) * 10^b
2. 此位等于0，为 ([n / 10^(b+1) ] ) * 10^b
3. 此位等于1，在0的基础上加上n mod 10^b + 1

举个例子，我们来分析 N=30143 的情况：

1. 由于3>1,则个位上出现1的次数为(3014+1)*1
2. 由于4>1,则十位上出现1的次数为(301+1)*10
3. 由于1=1，则百位上出现1次数为30*100+(43+1)
4. 由于千位为0，则千位上出现1次数为3*1000

仔细观察，不难明白其中的道理。以百位为例：100到199共有100个1，而除以100以后位30，所以共有30个100到199，这就构成了300 * 100。最后，当对于千位和万位为0的情况，还有100到143这44个数，所以总共为30100 + 43 + 1。同样，不难理解，对于十位，有10到19共10个1，共有301个百位以上不为0的情况，最后加上百位以上都是0的情况，则为 （301+1） 10。

根据上面的总结，不难编程得到结果，这里不再写出详细过程。