mat[i]代表 1到（10^i-1）之间1的个数
假如是10806
那么f（10806）=mat[4] * 1+f(806)+807;
f(806)=mat[3] * 8+f[6]+10^2;
最后加的师min（100,806-100+1），第一个同理
就是个递归的过程，
计算最高位的1的个数，
然后加上 最高位*mat[i]的1的个数
然后递归算余数，把最高位消除就行

注意下不要落下数就好了，比如我10000的时候把10000本身落下了（最后项式min中第二项+1的部分，卒）

C++ 代码

class Solution {

typedef long long ll;
ll mat[18];
ll min1(ll a,int b){
    return a>(ll)b?(ll)b:a;
}
ll toten(int n){
    n--;
    ll ret=1;
    while(n--){
        ret*=10;
    }return ret;
}
ll downbit(ll n){
    if(n==0)return 0;
    if(n<=9)return 1;
    ll k=n;
    int bit=1;
    int bitnum=0;
    while(k/10){
        bitnum++;
        k/=10;
        bit*=10;
    }
    ll ret=0;
    //cout<<mat[bitnum]*(int)(n/bit)<<" "<<downbit(n%bit)<<" "<<min1(n-bit+1,bit)<<endl;
    return mat[bitnum]*(int)(n/bit)+downbit(n%bit)+min1(n-bit+1,bit);
}

public:
    int numberOf1Between1AndN_Solution(int n) {
        mat[1]=1;
        for(int i=2;i<=17;i++){
            mat[i]=toten(i)+10*mat[i-1];
        }
        return downbit(n);
    }
};