首页 > 剑指offer > 剑指offer(10)-整数中1出现的次数
2013
12-19

剑指offer(10)-整数中1出现的次数

题目来自 剑指offer系列 九度 1373:http://ac.jobdu.com/problem.php?pid=1373

题目描述:
亲们!!我们的外国友人YZ这几天总是睡不好,初中奥数里有一个题目一直困扰着他,特此他向JOBDU发来求助信,希望亲们能帮帮他。问题是:求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。 
输入:
输入有多组数据,每组测试数据为一行。每一行有两个整数a,b(0<=a,b<=1,000,000,000)。 

输出:
对应每个测试案例,输出a和b之间1出现的次数。 
样例输入:
0 5
1 13
21 55
31 99
样例输出:
1
6
4
7

 

题目分析:找出1到a所有整数中1出现的次数和1到b所有整数中1出现的次数,然后求其差值即可。此题不可用暴力算法,会超时,最大范围为10亿。那么我们来分析一下,看看能不能有其他的求解办法。

例如1234这个数,1的个数之和为千位上出现的次数+百位上出现的次数+十位上出现的次数+个位上出现的次数,

即1出现的次数689    =    235          +           200              +                130          +         124

又例如1046这个数,1出现的次数362   =    47           +           100              +                 110         +         105

再例如1146这个数,1出现的次数362   =    147         +          147               +                 120         +         115

通过分析可知,在某位上出现1的次数与自身位相关,而且也与之前的位和之后的位相关。

由此可将一个数拆分为   前面部分+中间位+后面部分,或front+mid+back(例如1146在求百位中的1出现次数时,可看成1+1+46来处理)

我们可得如下规律:

当mid > 1时,  1出现的次数为10^(back的位数) * (front+1) ;
当mid == 1时,1出现的次数为10^(back的位数)* front + (back + 1) ;
当mid == 0时,1出现的次数为10^(back的位数) * front ;

代码如下:

#include <stdio.h>

long long fun(long long n)
{
	if(n < 1)
		return 0;
	long long count = 10, num = 0, front, mid, back,m;
	front = n;
	mid = 0;
	back = 0;
	while(front)
	{
		front = n/count;
		m = n%count;
		mid = m/(count/10);
		back = m%(count/10);
		if(mid > 1)
			num = num + (count/10) * (front+1);
		else if(mid == 1)
			num = num + (count/10) * front + (back + 1);
		else 
			num = num + (count/10) * front;	
		count = count * 10;
	}
	return num;
}

int main()
{
	long long n,m;
	while(scanf("%lld %lld",&n,&m)!=-1)
		if(n>m)
			printf("%lld\n",fun(n) - fun(m-1));
		else
			printf("%lld\n",fun(m) - fun(n-1));
	return 0;
}

转自:http://blog.csdn.net/love_cppandc/article/details/8702172


  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }