统计数字问题

1001-高同学

发表文章数:265

首页 » LeetCode » 正文

在王晓东编著的《算法设计与实验题解》中看到的这个问题,问题描述如下:
一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排,每个页码都不含多余的前导数字0。例如第6页用6表示而不是06或006。数字统计问题要求对给定书的总页码,计算出书的全部页码中分别用到多少次数字0,1,2,3,…..9。

刚开始写的时候直接用暴力解法,算法时间复杂度是O(N^2),在处理数字稍微大一点就很吃力,然后看了看配套的习题解答,数学上说的很经典。

给定一个n位数,比如说5位数,那么从00000(5个零)到99999(5个9),由于每一位上的0~9这10个数字出现的频率是相同的,所以这10个数字出现的次数也相同,书中给出的推到公式是:n*(10^(n-1))。

我看了些博客,以及加上自己在回宿舍的路上想的一些方法,其实有点麻烦的是最高位的算法啦。

给一个数字y,如果它是n位数,那么它的n-1位一定满足上述的推导公式。假设这个数y的最高位上的数是x,那么前n-1位中的0~9这10个数字出现的次数就是上述推导公式*x。不难理解的是:从0到x-1的数字,出现的次数为10^(n-1)。最高位出现的次数就是:y%10^(m-1)+1

这样的话代码实现如下:

#include <bits/stdc++.h>

using namespace std;

long long  num[10] = {0};
int NumLen (int n)
{
    if(n ==0)    //!!!注意这里 当page为10或100或...时,如果不加这个会出错
        return 1;
    int cnt = 0;
    while(n!=0)
    {
        cnt++;
        n = n/10;
    }
    return cnt;
}
int FirstNum(int len,int n)
{
    if(len == 1)
        return n;
    return n/pow(10,len-1);
}
int f(int n)
{
    return n*pow(10,n-1);
}
void countN(int n)
{
    int m,fir,i;
    m = NumLen(n);
    fir = FirstNum(m,n);
    if(m == 1)
        num[fir]++;
    else
    {
        for(i=0; i<10; i++)
        {
            num[i]+=fir*f(m-1);
        }
        for(i=1; i<fir; i++)
        {
            num[i]+=(int)pow(10,m-1);
        }
        num[fir] += 1+n%(int)pow(10,m-1);
    }
}
int main()
{
    long long  page;
    int len,i;
    cin>>page;
    len = NumLen(page);
    for(i=0; i<len; i++)
    {
        countN(page);
        page = page%(int)pow(10,NumLen(page)-1);
    }
    for(i=0; i<10; i++)
        cout<<num[i]<<" ";
    return 0;
}

 

 

拜师教育学员文章:作者:1001-高同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《统计数字问题》 发布于2018-09-10

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录