分析

338. 计数问题

C++ 代码

class Solution {
public:
    int get_num(int l,int r,int num[])
    {
        int res=0;
        for(int i=l;i>=r;i--) res=10*res+num[i];
        return res;
    }
    int pow(int n)
    {
        int res=1;
        while(n--) res*=10;
        return res;
    }
    int work(int n,int x)
    {
        int res=0,len=0,num[10];
        if(n==0) return 0;
        while(n)
        {
            num[++len]=n%10;
            n/=10;
        }
        for(int i=len;i>=1;i--)
        {
            if(i<len) 
                if(x) res+=get_num(len,i+1,num)*pow(i-1); //1不在首位，前i位没有填满

            //前i位已经填满
            if(num[i]<x) res+=0;
            else if(num[i]==x) res+=(get_num(i-1,1,num)+1);
            else res+=pow(i-1);
        }
        return res;
    }
    int numberOf1Between1AndN_Solution(int n) {
        return work(n,1);
    }
};