剑指Offer - 九度1373 - 整数中1出现的次数（从1到n整数中1出现的次数）
2014-02-05 23:03

题意分析：
　　对于给定的整数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)哦。

 1 // 688882    zhuli19901106    1373    Accepted    点击此处查看所有case的执行结果    1020KB    1161B    0MS
 2 // 201402020057
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 long long int sum[11];
 7 
 8 long long int solve(long long int x)
 9 {
10     long long int b10;
11     int idx;
12 
13     if (x == 0) {
14         return 0;
15     } else if (x < 10) {
16         return 1;
17     }
18 
19     b10 = 1;
20     idx = 0;
21     while (b10 * 10 <= x) {
22         b10 *= 10;
23         ++idx;
24     }
25     /*
26     printf("b10 = %lld\n", b10);
27     printf("idx = %d\n", idx);
28     */
29     if (x / b10 > 1) {
30         return (x / b10) * sum[idx] + b10 + solve(x % b10);
31     } else {
32         return sum[idx] + (x % b10 + 1) + solve(x % b10);
33     }
34 }
35 
36 int main()
37 {
38     int i;
39     int x, y;
40     long long int b10;
41 
42     sum[0] = 0;
43     sum[1] = 1;
44     b10 = 1;
45     for (i = 2; i <= 10; ++i) {
46         b10 *= 10;
47         sum[i] = 10 * sum[i - 1] + b10;
48     }
49 
50     /*
51     for (i = 0; i <= 10; ++i) {
52         printf("sum[%d] = %lld\n", i, sum[i]);
53     }
54     */
55 
56     while (scanf("%d%d", &x, &y) == 2) {
57         // the problem should‘ve told me what to do if x > y, it‘s unfair.
58         if (x > y) {
59             i = x;
60             x = y;
61             y = i;
62         }
63 
64         if (x == 0) {
65             printf("%lld\n", solve(y));
66         } else {
67             printf("%lld\n", solve(y) - solve(x - 1));
68         }
69     }
70 
71     return 0;
72 }