剑指Offer - 九度1373 - 整数中1出现的次数（从1到n整数中1出现的次数）
2014-02-05 23:03
- 题目描述：
-
亲们！！我们的外国友人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
题意分析：
对于给定的整数a和b，求出从a到b所有整数中，数字‘1’出现的次数。
这题显然不会让我们逐个统计每个数字中‘1’出现的次数，太慢了。
可以按照位数从低往高进行递推：
1. 定义所有n位数中(也包括1位、2位、...、n-1位)‘1’总共出现了f[n]次。
2. f[0] = 0
3. f[n+1]=10*f[n]+10^n。多出来的10^n表示最高位为‘1’的10^n个数。
有了这个f[n]后，可以以log10(n)的复杂度递归求出从1~n中‘1’出现的次数。然后对a、b求解后求出差即可。要注意，a和b指不定谁大，必要的时候交换一下。
时间复杂度O(log10(a) + log10(b))。空间复杂度O(log10(max(a,b)))，虽然接近常数，但也不能写成O(1)哦。
// 688882 zhuli19901106 1373 Accepted 点击此处查看所有case的执行结果 1020KB 1161B 0MS
//
#include <cstdio>
using namespace std; long long int sum[]; long long int solve(long long int x)
{
long long int b10;
int idx; if (x == ) {
return ;
} else if (x < ) {
return ;
} b10 = ;
idx = ;
while (b10 * <= x) {
b10 *= ;
++idx;
}
/*
printf("b10 = %lld\n", b10);
printf("idx = %d\n", idx);
*/
if (x / b10 > ) {
return (x / b10) * sum[idx] + b10 + solve(x % b10);
} else {
return sum[idx] + (x % b10 + ) + solve(x % b10);
}
} int main()
{
int i;
int x, y;
long long int b10; sum[] = ;
sum[] = ;
b10 = ;
for (i = ; i <= ; ++i) {
b10 *= ;
sum[i] = * sum[i - ] + b10;
} /*
for (i = 0; i <= 10; ++i) {
printf("sum[%d] = %lld\n", i, sum[i]);
}
*/ while (scanf("%d%d", &x, &y) == ) {
// the problem should've told me what to do if x > y, it's unfair.
if (x > y) {
i = x;
x = y;
y = i;
} if (x == ) {
printf("%lld\n", solve(y));
} else {
printf("%lld\n", solve(y) - solve(x - ));
}
} return ;
}