1到n中含1的数字的个数
题目如图所示
很容易想到的就是简单的暴力
#include <stdio.h>
int main()
{
int i, n, m, num = 0;
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
m = i;
while (m)
{
if (m % 10 == 1)
{
num++;
m = 0;
}
m /= 10;
}
}
printf("%d\n", num);
return 0;
} 但要优化，似乎很难 不过，我想出了一种时间复杂度很低的算法
先用刚刚的代码运行一下，比如我们要算的n为5637：
优化方法如下：
首先，我们把1-5637分为：
（1）1-4999
（2）5000-5599
（3）5600-5629
（4）5630-5637
然后分别求出里面的不含1的个数，最后用5637-该个数即可
求出不含1的个数会比求出含1的个数简单，方法如下：
1-4999是个4位数，第1位数的取值为0-4，第2位数取值为0-9，第3位数取值为0-9，第4位数取值也为0-9，而且不能同时为0
那么第1位数能取的数为0,2,3,4共4位数；第2、3、4位数能取的分别为0,2-9的9位数
则不含1的有4*9*9*9=2916，但不能同时为0，所以为2915个
同理5000-5599有1*5*9*9=405个，5600-5629有1*1*2*9=18个，5630-5637有1*1*1*7=7个
一共有2915+405+18+7=3345个
那么含1的就有5637-3345=2292个
不难发现计算方法为：
5637-（4*9^3+5*9^2+2*9^1+6*9^0）=2292
但事实上，没那么容易，考虑2009，
计算方法为（过程较为简单，故省略）：
2009-（1*9^3+8*9^0）=1272
是0的位置应该忽略
而且，出现1时，要处理一下，比如1111，
计算方法为（分段后，后面的段的前面部分只要含了1，自然就不用计算了）：
1111-（9^3-1）=292
遇到1的时候特殊处理一下即可
代码如下：
#include <stdio.h>
long long a[100];
long long b[100];//b[i]为9的i次方
int main()
{
long long i, p, n, m, num = 0;
scanf("%lld", &n);
p = n;
for (i = 0; p; i++)
{
a[i] = p % 10;
p /= 10;
}
m = i;
b[0] = 1;
for (i = 1; i < m; i++)
{
b[i] = b[i - 1] * 9;
}
for (i = m - 1; i >= 0; i--)
{
if (a[i] > 1)
{
num += (a[i] - 1) * b[i];
}
if (a[i] == 1)
{
num += b[i];
num--;
break;
}
}
printf("%lld\n", n - num);
return 0;
} 
小天才公司福利 1326人发布
查看3道真题和解析
