PAT 解题报告 1049. Counting Ones (30)

1049. Counting Ones 题目描述:

给出一个正整数N (<=230), 求出从1 到 N这些十进制数字钟1′s的个数, 例子见下面的具体描述:

The task is simple: given any positive integer N, you are supposed to count the total number of 1′s in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1′s in 1, 10, 11, and 12.

1049. Counting Ones 算法分析:

这个题目有意思, 考虑递归或者动态规划的思路吧. 假设dp[i]表示从1 到 9…9这么十进制数字中1的个数, 其中9…9是i位数, 即有i个9. 那么我们知道

dp[i+1] = dp[i]            // 1 到 9...9, i位数
        + 1 * 10 ^ (i-1)   // i+1位数, 首位的1出现的次数
        + 9 * dp[i]        // i+1位数, 非首位1出现的次数

然后对于任意一个i位数num, 我们如果知道从1到num的1的个数是cnt[i], 在num前面加上一位H, 当H > 1的时候, 从1到这个i+1位数(H, num)所有数字中的1的个数cnt[i+1]将由三部分组成: (1) H * dp[i], H从0到1,到2, …到H共经历了H个dp[i]; (2) 其中当H总0跳到1的时候, 也需要统计H=1这个1本身, 数量是10 ^ i, (3) 当H就是H > 1的时候,还需要统计低位的num中, 从1到num中1的个数, 也就是cnt[i]. 其他情况H = 1, 0的时候依次类推. 实现的代码可以AC的如下:

#include <iostream>
#include <cstring>
#include <cstdio>

#define REP(i,n) for(int i=0;i<(n);++i)

using namespace std;

int nones[12][2];

int main(void) {
    nones[1][0] = 1;
    int mul = 10;
    for(int i=2; i<=9; ++i) {
        nones[i][0] =   nones[i-1][0]
                        + 1*mul
                        + 9*nones[i-1][0] ;
        mul *= 10;
    }
    int N;
    scanf("%d", &N);
    int cur_counts = 0;
    int k = 0;
    int num = N;
    while(N) {
        k++;
        N /= 10;
    }
    if(1 == k) {
        if(num)
            printf("1\n");
        else
            printf("0\n");
        return 0;
    }

    if(num%10)
        cur_counts = 1;
    else
        cur_counts = 0;
    mul = 1;
    for(int i=2; i<=k; ++i) {
        mul *= 10;
        int hi = (num/mul)%10;
        int low = num % mul;

        if(hi > 1) {
            cur_counts = hi * nones[i-1][0]  
                            + mul 
                            + cur_counts; 
        }
        else if(hi == 1) {
            cur_counts = hi * nones[i-1][0]  
                            + (low+1) 
                            + cur_counts;  
        }
        else {  
            cur_counts = hi * nones[i-1][0]   
                            + 0 
                            + cur_counts; 
        }
    }
    printf("%d\n", cur_counts);
    return 0;
}

1049. Counting Ones 注意点:

递推关系的挖掘稍微有待绕这里, 理清楚正确的关系需要仔细一点. 实现的细节也要稍加注意, 注意一些特殊的case,比如零啊1啊之类的.

Written on January 19, 2014