题目描述

blablabla

样例

blablabla

算法

如统计数字abcdefg中 数字1
统计每位数字出现的次数 按照下面原则
xxxdyyy
首先是xxx属于 000~abc-1 则 yyy 可以是 000~999 则一共有 abc*1000次
xxx=abc时 分情况讨论 选择其中一种
(1)d<1，此时1在第四位出现的次数为0
(2)d=1，只有 yyy 000~efg
(3)d>1， yyy可取 000~999

时间复杂度

参考文献

代码

    public int count(int x, int a){//统计1~x中 a出现的个数
        int r, l, sum;
        r = 0; l = 0; sum = 0;
        int i, j;
        for(i =x, j=0; i>9; i/=10, j++){//处理边界问题 剩下单个数字是 单独考虑 现在只考虑l-cur-r型的
            int cur = i % 10;//枚举每一位
            l = (i - cur) / 10;//当前位左边
            sum += l * power10(j);//xxx属于 000~abc-1
            if(cur>a)//yyy可取 000~999
                sum += power10(j);
            if(cur==a)//只有 yyy 000~efg
                sum += r + 1;
            r = r + cur * power10(j);//下一位的右边
        }
        if(i>a) sum += power10(j);//r为0时 只需考虑右边就行 
        if(i==a) sum += r + 1;
        return sum;
    }

    public int power10(int x){
        int res = 1;
        for(int i=0; i<x; i++){
            res *= 10;
        }
        return res;
    }

（可以尝试写统计0出现的个数 稍微特殊些）