问题描述:一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排,每个页码都不含多余的前导数字0。例如,第6页用数字6表示,而不是06或006等。数字计数问题要求对给定书的总页码n,计算出书的全部页码中分别用到多少次数字0,1, 2,…,9。

思路:

最暴力的思想,总页码为n时候,其0-9数字出现的次数是总页码为n-1时候的数字出现次数加上n中0-9数字出现的次数。可以从n=1开始迭代,到题目要求的最大值。算法的复杂度为o(n)

代码如下:

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int main(){
  const int MAXN=1000;
  int page_num[MAXN+5][10];
  memset(page_num,0,sizeof(page_num));
  page_num[1][1]=1;
  for(int i=2;i<=MAXN;i++){
    int page_now=i;
    while(page_now!=0){
      page_num[i][page_now%10]+=1;
      page_now/=10;
    }
    for(int j=0;j<10;j++){
      page_num[i][j]+=page_num[i-1][j];
    }
  }

  for(int i=0;i<10;i++){
    cout<<page_num[100][i]<<" ";
  }
  cout<<endl;
  return 0;
}

这种方法简单易懂,编程实现也很方便,只有一个缺点:速度太慢。他的复杂度是o(n)级别的,题目要求n的最大值为10 ^ 9,所以当输入为n=10 ^ 9时,会超时,也会溢出。因此,这里需要使用一些更加快速的方法。

思路V2.0

通过分析,我们可以发现,所有数字的次数是个位,十位,百位…的各个数字个数相加的结果。因此,我们可以直接根据数字n来计算最终的数字的个数。比如个位中,数字出现的个数就是由n/10n%10所决定的,比方说n=123,那么他个位上数字出现的次数就是[12,12,12,..,12,]+[0,1,1,1,0,0,..,0];十位上出现的数字的次数跟个位出现的次数计算一样,即根据n/100以及十位上的值计算,这个数字要乘以10因为是在十位,此外,还要考虑个位对十位的作用。还是举例n=123,十位上数字出现的次数为10*[1,1,1,..,1]+10*[0,1,0,0,..,0]+[0,0,4,0,..,0] (左式中的1是因为n/100=1,中间是因为十位是2,右边是因为个位还加了4个2)。所以,对于一个n的某一个位而言,该位数字的个数是由比这位高的数字,该位的数字,以及该位低的位决定的。实际编程的时候,还要考虑各种边界条件带来的影响。最终函数表示如下:

int r[10];
void count_number(int n){
  const int MAXN=9;
  int tag=1;
  for(int i=0;i<10;i++){
    r[i]=0;
  }
  for(int i=0;i<MAXN;i++){
    int gt=n/(tag*10);
    int eq=(n%(tag*10))/tag;
    int lt=n%tag;
    for(int j=0;j<10;j++){
      r[j]+=gt*tag;
    }
    if(gt!=0) r[0]-=tag;
    for(int j=0;j<eq;j++){
      r[j]+=tag;
    }
    if(gt==0 && eq!=0) r[0]-=tag;
    if (!(gt==0 && eq==0))r[eq]+=(lt+1);
    tag*=10;
  }
}

可以看到,该方法的复杂度是log10(n),速度比第一种方法快了不少,不过第一种方法可以拿来验证第二种方法的正确与否。缺点就是有各种边界条件。因此,编程时候脑子一定要清楚。