题目描述

blablabla

样例

blablabla

算法1

强调分类讨论：

比如说我要找[1,abcdefg]中的数中1出现的个数
就得先求1在每一个位置上出现的次数

比如我要找第4位上出现的1的数有几个
就是要找满足 1 <= xxx1yyy <= abcdefg

condition
1. xxx∈[000,abc-1] , yyy∈[000,999] , ans += abc*1000 //如果前三位没填满，则后三位就可以随便填
2. abc x :
2.1 d < x: 0
2.2 d = x: yyy∈[000,efg] ans += efg+1
2.3 d > x: yyy∈[000,999] ans += 1000

注意特判 x = 0. 不能有前导0. x 不能在第一位 xxx∈[001,abc-1]

Java 代码

import java.util.*;
import java.io.*;

public class Main{

    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter write = new PrintWriter(System.out);
    public static void main(String[] args) throws IOException{
        String[] s;
        while(true){
            s = read.readLine().split("\\s+");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            if(a == 0 && b == 0 ) break;
            if(a > b){
                int temp = a;
                a = b;
                b = temp;
            }
            for(int i = 0; i <= 9; i++){
                int res = count(b, i) - count(a-1, i);
                write.print(res + " ");
            }
            write.println();
        }
        write.flush();
        write.close();
        read.close();
    }

    public static int count(int n, int x){
        if(n == 0) return 0;
        int res = 0;

        // 保存每个位数的值 从前n位到前1位
        List<Integer> nums = new ArrayList<>();
        while(n != 0){
            nums.add(n%10);
            n = n/10;
        }

        //特判 x = 0最高位不能为0
        int bit = x == 0 ? 1:0;
        n = nums.size();
        for(int i = n-1-bit; i>=0;i--){
            // condition 1
            if(i < n-1){
                res += get(nums, n-1, i+1)*Math.pow(10,i);
                //特判 x = 0
                if(x == 0){
                    res -= Math.pow(10,i);
                }
            }
            // condition 2
            if(nums.get(i) == x){
                res += get(nums, i-1, 0)+1;
            }else if(nums.get(i) > x){
                res += Math.pow(10,i);
            }
        }
        return res;
    }
     //求前l到r位组成的数字
    public static int get(List<Integer> nums, int l, int r){
        int res = 0;
        for(int i = l; i >= r;i--){
            res = res*10+nums.get(i);
        }
        return res;
    }

}