统计数字问题

问题描述：

给出n,遍历1~n,统计每个数字的出现次数，没有前导0(1 <= n <= 1e9)。

引子

这是一道很老的题目,OJ没有收录。
暴力代码必定超时，但可以用来测试。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int c[10] = {0}, n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int tmp = i; tmp; tmp /= 10)
            c[tmp % 10]++;
    for (int i = 0; i < 10; i++)
        cout << c[i] << endl;
    return 0;
}//暴力枚举 检查代码

观察00-99的表

#include <bits/stdc++.h>
using namespace std;
int main(){
    for (int i = 0; i < 100; i++){
        if(i<10) printf("0%d ",i);
        else printf("%d ",i);
        if(i%10==9)cout<<endl;
        }
    return 0;
}

推导

有前导0的情况比没有前导0的情况更规律。
所以采用类似几何中“补形”的做法，先计算有前导0的情况，之后再减去。
从0-9，每个数都使用了1次。
从00-99，每个数都使用了20次。
从000-999，每个数都使用了300次。
设使用次数为f(n)
n=1时
f(1)=10
n>1时
f(n)=10f(n-1)+10^(n-1)
这个其实是一个递归的理解，000-999中有十次遍历00-99，三位数自带个位和百位，从000-999一共有1000个数，有1000个百位没有计算进去，那么就要再加上1000/10=100.
所以f(n)=n*10^n-1
(本来这里是公式的，但牛客网的这个公式插入死活显示不出来，我以后可能就不在牛客写博客了，我也已经申请到了博客园的权限)

思路

把工作拆解成以下几个部分：
以2345为例

1.先计算个十百位（非最高位）直接满足公式的数 [0000-0999] [1000,1999]
0-9 :300 + 300

2.计算最高位，1000次0：[0000-0999]；1000次1：[1000,1999]；346次2：[2000,2345]
0:+1000
1:+1000
2:+346

3.到现在，还剩下345没有计算。也就是说，我们剩下的工作就是计算345的统计数字问题。
显然可以递归解决

4.删除0。
删除前导0类似前面

还有一点补0的小细节，在注释里写了。

代码

#include<bits/stdc++.h>
using namespace std;
int cnt[10],n;
void solve(int n) {
    int len = log10(n);
    int p = n / ((int)pow(10.0, len));//最高位
    for(int i = 0; i <= 9; i++) //第一步
        cnt[i] += p * len * (int)pow(10.0, (len-1));
    for(int i=0; i<p; i++) //第二步 
        cnt[i]+=(int)pow(10.0, len);
    cnt[p]+=1+n%((int)pow(10.0, len));
    int t=n%((int)pow(10.0,len));//判断是否要递归 t为去掉最高位后的数 
    if(!t) {
        if(len) cnt[0]+=len;//eg.2000 0再加3  
        return;
    } else if(len-log10(t)> 1)//eg.2020 0再加1 
        cnt[0]+=(len-log10(t)-1) * t;
    solve(t);
}
int main() {
    while(cin >> n) {
        memset(cnt,0,sizeof(cnt));
        solve(n);int len = log10(n) + 1;
        for(int i = 1; i <= len; i++)//从低位往高位减 i=1的时候刚好减掉了个位的0 
            cnt[0] -= (int)pow(10.0, (i - 1));//减去前导0
        for(int i = 0; i < 10; i++) 
            cout << cnt[i]<< ' ' ;
        cout << endl;
    }
    return 0;
}