剑指Offer(牛客版)--面试题43: 1~n 整数中 1 出现的次数

题目描述：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。

完整代码：

class Solution {
public:
    
    int NumberOf1Between1AndN_Solution(int n)
    {
         //检查输入的合法性
         if(n <= 0)
             return 0;
        //声明一个变量，用来存放数字
         char array[50];
        //将整数转换成字符串
        sprintf(array,"%d",n);
        //返回 1 的出现正数
        return Numbersof1(array);
    }
private:
    //统计 1 出现的次数
    int Numbersof1(const char* array)
    {
        //检查输入的合法性
        if(!array || *array < '0'|| *array > '9'|| *array == '\0' )
            return 0;
        //计算开头的第一个数字
        int first = *array - '0';
        //计算 array 的长度 
        unsigned int length = static_cast<unsigned int> (strlen(array));
        //计算单个数字0的情况
        if(length == 1 && first == 0)
            return 0;
        //计算单个数字非 0 的情况
        if(length == 1 && first > 0)
            return 1;
        //假设数字为21345，将数字分成 1~1345 和 1346~21345
        /******计算1346~ 21345中，最高位 1 出现的次数********/
        //统计 1 出现的次数
        int NumFirstDigits = 0;
        //如果最高位大于 1
        if(first > 1)
            //则 1 出现的次数为 10的(lenght - 1)次方
            NumFirstDigits = Numbersof10(length - 1);
        //如果最高为等于 1
        else if(first == 1)
            //则 1 的出现次数为 除 1 以外的后面数字 + 1
            NumFirstDigits = atoi(array + 1) + 1;
        /*******计算出最高位之外 1 出现的次数********/
        //声明一个变量，统计此种情况下 1 出现的次数
        int NumOtherDigits = first * (length - 1) * Numbersof10(length - 2);
        //递归计算 1~1345 中 1 出现的次数
        //声明一个变量，计算此种情况下的 1 的个数
        int NumRecursive = Numbersof1(array + 1);
        //返回最终 1 出现的次数
        return NumFirstDigits + NumOtherDigits + NumRecursive;
    }
    
    //计算 10 的 n 次方
    int Numbersof10(unsigned int n)
    {
        int result = 1;
        for(unsigned int i = 0; i < n; ++i)
            result *= 10;
        //返回结果
        return result;
    }
};

           

相关知识点：

1、sprintf()函数；

https://blog.csdn.net/bat67/article/details/52063813

2、atoi()函数；

https://blog.csdn.net/weibo1230123/article/details/80091106