面试题32：从1到n整数中1出现的次数

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

分析

最简单也最容易想到的就是从1到n进行遍历，每到一个数字，就逐个取出它十进制中的每一位数，并判断是否为1。当然，这肯定不是最好的方案。代码从略。

上述代码还有一个缺陷就是没有考虑溢出问题。整型最大只能表示2147483647，要是n大于这个值呢？所以这是一个隐形的大数问题。

解决大数问题的常用方法是用字符串来模拟数字。由于最大的数字有n位，我们可以用一个长度为n+1的char数组来保存n。

而在具体计算时，我使用65536作为例子。首先，可以将1~65536分为两部分，1~5535 (1)和5536~65536 (2)。我们先来求1出现在万位时的情况，第(1)段显然不可能出现1出现在万位的情况。在第二段范围内，1出现在万位的数字范围为10000~19999.共计10000个(10³)。对于1出现在千位到个位的情况，先来看第(2)段，第(2)段有5536~65536共60000个数字，也可以将他们分成6段：5536~15535,15536~25535,25536~35535……。1是可能出现在每一段的个、十、百、千的任何一位的，根据排列组合的原理，每一位为1，其他位可以为0~9任意一个，所以1出现的次数有10101064=24000个。接下来看第(1)段中1出现在千位到个位的情况，很明显，(1)和(2)是互相独立的，所以可以用递归去求解，求解结果为2714。

综上，1~65536中1出现的次数共有10000+24000+2714=36714次。

代码如下：

int NumberOf1(const string str)
{
    int length=str.size();
    if(length<=0)
        return 0;
    int first=str[0]-'0';
    if(length==1 &amp;&amp; first==0)
        return 0;
    if(length==1 &amp;&amp; first>0)
        return 1;
    int numFirstDigit=0;
    if(first==1)
    {
        numFirstDigit=atoi(str.c_str()+1)+1;
    }
    else if(first>1)
    {
        numFirstDigit=pow(10,length-1);
    }
    int numOtherDigit=first*(length-1)*pow(10,length-2);
    int numRecursive=NumberOf1(str.c_str()+1);
    return numFirstDigit+numOtherDigit+numRecursive;
}

int NumberOf1Between1AndN(unsigned int n)
{
    if(n<=0)
        return 0;
    char str[11];
    sprintf(str,"%d",n);
    return NumberOf1(str);
}

以上

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往