剑指offer编程题—整数中1出现的次数

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

解题思路
思路1：
直接暴力循环，时间复杂度位O(nlogn)
思路2
主要是寻找数学规律，时间复杂度为O(logn)，详情参考网友链接。
参考连接：整数中1出现的次数(从1到n整数中1出现的次数)

代码实现：

#include<iostream>
#include<cmath>
using namespace std;

//题解1：暴力循环
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int count=0;
        int temp;
        for(int i=1;i<=n;++i){
            temp=i;
            while(temp){
                if(temp%10==1) ++count;
                temp/=10;
            }
        }
        return count;
    }
};

/*题解2：找规律：
1.如果第i位（自右向左，i从第1位开始标号）上的数字是0，则第i位可能出现1的次数由更高位决定，
  出现1的次数=更高位数*当前位数的权重（10^(i-1));
2.如果第i位上的数字是1，则第i位出现1的次数不仅受更高位影响，还受低位影响，
  出现1的次数=更高位数*当前位数的权重（10^(i-1))+1+低位数
3.如果第i位上数字大于1，则第i位出现1的次数由更高位决定，
  出现1的次数=（更高位数+1）*当前位数的权重（10^(i-1))
*/
class Solution1 {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int r = 0;
        for(long long i = 1; i <= n; i *= 10){
            //如果第i位上数字大于1，表达式( n / i + 8)实现了向更高位进1， ( n / i + 8)/ 10实现了（更高位+1）的操作
            //如果第i位上数字小于等于1，表达式( n / i + 8) / 10求得的就是更高位的数字。
            //表达式(n / i % 10 == 1) 用于判断第i位上是否为1
            //表达式(n / i % 10 == 1) * (n % i + 1)实现了（低位数+1）
            r += ( n / i + 8) / 10 * i + (n / i % 10 == 1) * (n % i + 1);
        }
        return r;
    }
};

int main(int argc,char **argv)
{
    int n=113;
    int res;
    Solution sol;
    res=sol.NumberOf1Between1AndN_Solution(n);
    cout<<res<<endl;

    Solution1 sol1;
    res=sol1.NumberOf1Between1AndN_Solution(n);
    cout<<res<<endl;
    return 0;
}