面试题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作为例子。首先,可以将165536分为两部分,15535 (1)和5536~65536 (2)。我们先来求1出现在万位时的情况,第(1)段显然不可能出现1出现在万位的情况。在第二段范围内,1出现在万位的数字范围为10000~19999.共计<font color="red">10000</font>个(10<sup>3</sup>)。对于1出现在千位到个位的情况,先来看第(2)段,第(2)段有553665536共60000个数字,也可以将他们分成6段:553615535,1553625535,2553635535……。1是可能出现在每一段的个、十、百、千的任何一位的,根据排列组合的原理,每一位为1,其他位可以为0~9任意一个,所以1出现的次数有10101064=<font color="red">24000</font>个。接下来看第(1)段中1出现在千位到个位的情况,很明显,(1)和(2)是互相独立的,所以可以用递归去求解,求解结果为<font color="red">2714</font>。

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

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int NumberOf1(const string str)
{
int length=str.size();
if(length&lt;=0)
return 0;
int first=str[0]-'0';
if(length==1 &amp;&amp; first==0)
return 0;
if(length==1 &amp;&amp; first&gt;0)
return 1;
int numFirstDigit=0;
if(first==1)
{
numFirstDigit=atoi(str.c_str()+1)+1;
}
else if(first&gt;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&lt;=0)
return 0;
char str[11];
sprintf(str,"%d",n);
return NumberOf1(str);
}

以上

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

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

<div>来自为知笔记(Wiz)</div>