题目描述：

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

实现如下：

//方法一
//将所有的数遍历一次，对每一个数的每一位再进行是否为1的判断
//时间复杂度为O（n*logn）
class Solution 
{
private:
	int NumberOf1(unsigned int n)
	{
        int number = 0;
        while(n)//对此数字的每一位都进行判断
		{
            if(n % 10 == 1)//模10取余，判断是否为1
                number++;
            n = n / 10;//将最后一位舍弃
        }
        return number;
    }
public:
    int NumberOf1Between1AndN(unsigned int n)
    {
        int number = 0;//计数器
        for(unsigned int i = 1; i <= n; ++i)//循环遍历所有的数
            number += NumberOf1(i);
        return number;
    }
};

//方法二
//时间复杂度为O(logn)
class Solution 
{
private:
	static int PowerBase10(unsigned int num)//计算num与10次方的关系
	{
		int res = 1;
		for (unsigned i = 0; i < num; ++i)		
			res *= 10;
		return res;
	}
	static int NumberOf1(const char* str)
	{
		//防御性动作，判断字符串是否存在、第一个数字是否合法、字符串是否为NULL
		if (!str || *str < '0' || *str > '9' || *str == '\0')
			return 0;
		
		int first = *str - '0';//取数字的最高位，将其转化为int
		unsigned int length = static_cast<unsigned int>(strlen(str));//计算数字的位数，将其转化为unsigned int

		if (length == 1 && first == 0)//如果是一位数且值为0，则直接返回0
			return 0;
		if (length == 1 && first > 0)//如果是一位数且值大于0，则1只出现1次，直接返回1
			return 1;

		int numFirstDigit = 0;
		if (first > 1)//如果第一位数大于1，则计算数字与10的次方关系
			numFirstDigit = PowerBase10(length - 1);
		else if (first == 1)//如果第一位数等于1，则1出现的次数为从最高位为1到最大值的差值再加一
			numFirstDigit = atoi(str + 1) + 1;
		
		int numOtherDigits = first*(length - 1)*PowerBase10(length - 2);//计算次高位开始的数出现1的次数
		int numRecursive = NumberOf1(str + 1);//递归计算从1开始到此数去掉最高位的数出现1的次数

		return numFirstDigit + numOtherDigits + numRecursive;//返回之和
	}
public:
	int NumberOf1Between1AndN_Solution(int n)
	{
		if (n <= 0)//防御性动作
			return 0;
		char str[100];
		sprintf(str, "%d", n);//将数字转化为字符串形式
		return NumberOf1(str);
	}
};