计算1到N中各个数字出现的次数 –数位DP

题意：给定一个数n，问从1到n中，0~9这10个数字分别出现了多少次。比如366这个数，3出现了1次，6出现了2次。

题解：《剑指offer》P174；《编程之美》P132 都给出了统计数字1的O(log(n))的解法。把他们进行改进就得到了这个问题的答案。

下面这个代码是我改的剑指offer的，也有类似编程之美的：传送门。

//《剑指offer》P174
#include <bits/stdc++.h>
using namespace std;
int pow1(int n,int len)//注意算的时候不要用math里的pow 会产生误差
{
    int ans=;
    while(len--) ans*=n;
    return ans;
}
int cal(char *c,int i)
{
    int len=strlen(c);
    int f=*c-'',g=*(c+)-'';
    if(len==&&(f<i||i==)) return ;
    if(len==&&f>=i) return ;
    int a1=,a2=,a3=;
    if(i==||f<i) a1=;
    else if(f>i) a1=pow1(,len-);
    else if(f==i) a1=atoi(c+)+;
    a2=f*(len-)*pow1(,len-);
    if(g==&&i==) a2=a2-pow1(,len-)+atoi(c+)+;
    a3=cal(c+,i);
    return a1+a2+a3;
}
int solve(int n,int i)
{
    char c[];
    sprintf(c,"%d",n);
    return cal(c,i);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=;i<;i++)
        printf("%d%c",solve(n,i),i==?'\n':' ');
    }
    return ;
}

官方标程：

#include <bits/stdc++.h>using namespace std;vector<int> solve(int n) {
    vector<int> res(, );
    if(!n) return res;
    if(n %  < ) {
        res = solve(n - );
        while(n) {
            res[n % ]++;
            n /= ;
        }
        return res;
    }
    res = solve(n / );
    for(int i = ; i < ; i++) res[i] = res[i] *  + n /  + (i > );
    return res;
}
int main() {
    int n;
    cin >> n;
    vector<int> ans = solve(n);
    for(int i = ; i < ans.size(); i++) {
        i ==  ? cout << ans[i] : cout << " " << ans[i];
    }
    return ;
}