剑指offer-整数中1出现的次数

本文为剑指 offer 系列第三篇。
核心能力是基于数学知识来找数字存在的规律。
这个问题给我的重要启示是将问题普遍化与自动化，是我们作为一个计算机行业从业者应该要做的事，也是让我们所有人受益无穷的事。

题目描述

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

解题思路

思路1:

将1-n的每个数通过取余数来计算每一位是否为1，然后找个计数器来进行统计

思路2:

通过分析每个位置上1出现的规律来进行规律性的查找。下面以数字32456然后计算百位上1的个数来进行演示。

1. 首先将原来的数据分为2部分，a= 32456/100 = 324, b=32456%100 = 56.
2. 这里百位上为4，所以他有完整的33个100位1，也就是(a/10+1)个100，推广一下，我们发现其实任何大于等于2的数字都会有这个规律。
3. 如果这里百位上为0.即32056，则它有完整的32个100，也就是（a/10)个100。
4. 如果这里百位上位1，即32156，则他有完整的32个100，同时会有32100-32156中57个百位上的1.也就是(a/10)个100，然后加上(b+1)个1.
   其他位可以同理得到计算结果。从而问题得到了解决。

解题代码

思路1代码

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        // 方法1: 暴力求解。计算每一个数中每一位是不是1进行求和。
        int res = 0;
        for(int i = 1;  i <= n; i++){
           int temp = i;
            while(temp){
                if(temp%10 == 1){
                    res++;
                }
                temp = temp/10;
            }
        }
        return res;
    }
};

时间复杂度为O(nlgn),空间复杂度为O(1);

思路2代码

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int res = 0;
        for(long i = 1; i<= n; i*=10){
            int a = n/i, b = n%i;
            if(a%10 == 0){
                res += (a/10)*i;
            }else if( a%10 == 1){
                res += (a/10)*i + (b+1);
            }else{
                res += (a/10+1)*i;
            }
        }
        return res;
    }
};

时间复杂度为O(lgn),空间复杂度为O(1);
以上，本题结束！