AcWing. 338计数问题

给定两个整数 a 和 b，求 a 和 b 之间的所有数字中 0∼9 的出现次数。

例如，a=1024，b=1032，则 a 和 b 之间共有 9 个数如下：

1024 1025 1026 1027 1028 1029 1030 1031 1032

其中 0 出现 10 次，1 出现 10 次，2 出现 7 次，3 出现 3 次等等…

样例

输入样例

1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0

输出样例

1 2 1 1 1 1 1 1 1 1
85 185 185 185 190 96 96 96 95 93
40 40 40 93 136 82 40 40 40 40
115 666 215 215 214 205 205 154 105 106
16 113 19 20 114 20 20 19 19 16
107 105 100 101 101 197 200 200 200 200
413 1133 503 503 503 502 502 417 402 412
196 512 186 104 87 93 97 97 142 196
398 1375 398 398 405 499 499 495 488 471
294 1256 296 296 296 296 287 286 286 247

思路理解

核心算法是comp(int number, int x)函数，它的作用是计算出1~number中x的出现次数。

为了便于理解，会举一些栗子。

举例：number=4572, x=5

从两个角度考虑这个问题，①x分情况，0和非0，因为0不能有前导0；②x放的位置

1. x分情况讨论

如果我想计算出把x放在number的十位的位置，第一步计算出它左边的数，得45,计算出它右边的数，得2，考虑
左边可以随便填的数为0~44，这个时候右边0~9都可以填，接下来就是左边填45和number一样，这个时候就要分情况讨论，如果说x大于7，那就填不下去了，如果x恰好是7，那么个位还可以填0~2，如果x小于7，那么个位可填0~9。如果说x是0的情况，那么它的左边就不能是0，即1~44，其他没有变化。

1. 讨论x放的位置

第1点讨论的是x的一般位置，接下来讨论放在最高位，这个时候它的左边是0，右边是572，如果还是套用上面的方法，会计算 -1 * 572，为了避免这种情况，如果x是0，应该只计算572这三个位置，其他和第1点一样；如果x放在最低位，左边照样计算，右边也是一样的。

java代码实现

import java.util.Scanner;

public class Main {

    // number的位数, number>0
    private static int length(int number) {
        int len = 0;
        while (number != 0) {
            len++;
            number /= 10;
        }
        return len;
    }

    // pow >= 0
    private static int pow10(int pow) {
        int ans = 1;
        while (pow != 0) {
            ans *= 10;
            pow--;
        }
        return ans;
    }

    // 1 ~ number中x的出现次数
    private static int comp(int number, int x) {
        int start = length(number);
        if (x == 0) start--;
        int total = 0;
        for (int i = start; i > 0; i--) {
            int left = number / pow10(i);
            int right = number % pow10(i - 1);
            int n = number / pow10(i - 1) % 10;
            if (left > 0)
                total += left * pow10(i - 1);
            if (x == 0) // 不能有前导0
                total -= pow10(i - 1);
            if (x < n)
                total += pow10(i - 1);
            else if (x == n)
                total += right + 1;
        }
        return total;
    }

    // 计算start~end这些数中0~9出现的次数
    private static void count(int start, int end) {
        if (end < start) {
            int tmp = start;
            start = end;
            end = tmp;
        }
        for (int i = 0; i < 10; i++) {
            System.out.print(comp(end, i) - comp(start - 1, i) + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int left = scanner.nextInt();
            int right = scanner.nextInt();
            if (left == 0 && right == 0) break;
            count(left, right);
        }
        scanner.close();
    }

}