软件测试

题目描述

原题链接：洛谷 P2602 [ZJOI2010] 数字计数

输入两个正整数a,b，求在[a,b]中的所有整数中，每个数码(0\~9)各出现了多少次。

输入格式：

输入两个正整数a, b确定区间[a,b](0<a<b<10^13)。

输出格式：

在一行中输出0\~9每个数码在[a,b]区间内共出现多少次，用空格隔开。

输入样例1：

1 20

输出样例1：

2 12 3 2 2 2 2 2 2 2

输入样例2：

101 300

输出样例2：

40 139 140 41 40 40 40 40 40 40

输入样例3：

1 99

输出样例3：

9 20 20 20 20 20 20 20 20 20

实现代码

方法：数位DP。

public class DigitCount {

    private static final int DIGIT_NUM = 10, INIT_SIZE = 20;

    private static void solve(long x, long[] count, long[] ten, long[] dp) {
        int[] num = new int[INIT_SIZE];
        int len = 0;
        while (x > 0) {
            num[++len] = (int) (x % DIGIT_NUM);
            x = x / DIGIT_NUM;
        }
        for (int i = len; i >= 1; i--) {
            for (int j = 0; j <= DIGIT_NUM - 1; j++) {
                count[j] += dp[i - 1] * num[i];
            }
            for (int j = 0; j < num[i]; j++) {
                count[j] += ten[i - 1];
            }
            long num2 = 0;
            for (int j = i - 1; j >= 1; j--) {
                num2 = num2 * DIGIT_NUM + num[j];
            }
            count[num[i]] += num2 + 1;
            count[0] -= ten[i - 1];
        }
    }

    public static long[] digitCount(long a, long b) throws NumberOutOfBoundException, ANoLessThanBException {
        final long lowerBound = 0, upperBound = 10_000_000_000_000L;
        final int initDpSize = 15;
        if (a <= lowerBound || b <= lowerBound || a >= upperBound || b >= upperBound) {
            throw new NumberOutOfBoundException();
        }
        if (a >= b) {
            throw new ANoLessThanBException();
        }
        long[] result = new long[DIGIT_NUM];
        long[] ten = new long[INIT_SIZE];
        long[] dp = new long[INIT_SIZE];
        long[] countA = new long[INIT_SIZE];
        long[] countB = new long[INIT_SIZE];
        ten[0] = 1;
        for (int i = 1; i <= initDpSize; i++) {
            dp[i] = dp[i - 1] * DIGIT_NUM + ten[i - 1];
            ten[i] = DIGIT_NUM * ten[i - 1];
        }
        solve(a - 1, countA, ten, dp);
        solve(b, countB, ten, dp);
        for (int i = 0; i < DIGIT_NUM; i++) {
            result[i] = countB[i] - countA[i];
        }
        return result;
    }

}

设计测试用例

执行测试用例

基于Maven引入JUnit5框架，主要基于org.junit.jupiter.api.Test和org.junit.jupiter.api.Assertions即可完成任务。

基本的测试思路：

• 如果是正常情况：

  Assertions.assertDoesNotThrow(() -> {
      Assertions.assertArrayEquals(expectedArray, DigitCount.digitCount(a, b));
  });

• 如果是异常情况：

  Assertions.assertThrows(XXXException.class, () -> DigitCount.digitCount(a, b));

正常情况可以套在一个确保非异常的Lambda表达式中执行；而异常情况则应该单测，防止一处异常全体异常。

美中不足的点是魔法数的大量引入。

测试代码：

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class DigitCountTest {

    @Test
    public void demoTest() {
        Assertions.assertDoesNotThrow(() -> {
            long[] expectedArray1 = new long[]{2, 12, 3, 2, 2, 2, 2, 2, 2, 2};
            long[] actualArray1 = DigitCount.digitCount(1, 20);
            Assertions.assertArrayEquals(expectedArray1, actualArray1);
            long[] expectedArray2 = new long[]{40, 139, 140, 41, 40, 40, 40, 40, 40, 40};
            long[] actualArray2 = DigitCount.digitCount(101, 300);
            Assertions.assertArrayEquals(expectedArray2, actualArray2);
        });
    }

    @Test
    public void normalTest() {
        Assertions.assertDoesNotThrow(() -> {
            Assertions.assertArrayEquals(new long[]{488895, 600001, 600000, 600000, 600000, 600000, 600000, 600000, 600000, 600000}, DigitCount.digitCount(1, 1000000));
            Assertions.assertArrayEquals(new long[]{488895, 600000, 600000, 600000, 600000, 600000, 600000, 600000, 600000, 600000}, DigitCount.digitCount(2, 1000000));
            Assertions.assertArrayEquals(new long[]{1088888400000L, 1199999400000L, 1199999400000L, 1199999400000L, 1199999400000L, 1199999400000L, 1199999400000L, 1199999400000L, 1199999400000L, 1199999399988L}, DigitCount.digitCount(1000000, 999999999998L));
            Assertions.assertArrayEquals(new long[]{1088888400000L, 1199999400000L, 1199999400000L, 1199999400000L, 1199999400000L, 1199999400000L, 1199999400000L, 1199999400000L, 1199999400000L, 1199999400000L}, DigitCount.digitCount(1000000, 999999999999L));
            Assertions.assertArrayEquals(new long[]{0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, DigitCount.digitCount(1, 2));
            Assertions.assertArrayEquals(new long[]{1088888888889L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1199999999988L}, DigitCount.digitCount(1, 999999999998L));
            Assertions.assertArrayEquals(new long[]{1088888888889L, 1199999999999L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1199999999988L}, DigitCount.digitCount(2, 999999999998L));
            Assertions.assertArrayEquals(new long[]{1088888888889L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L}, DigitCount.digitCount(1, 999999999999L));
            Assertions.assertArrayEquals(new long[]{1088888888889L, 1199999999999L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L, 1200000000000L}, DigitCount.digitCount(2, 999999999999L));
            Assertions.assertArrayEquals(new long[]{0, 0, 0, 0, 0, 0, 0, 0, 1, 23}, DigitCount.digitCount(999999999998L, 999999999999L));
        });
    }

    @Test
    public void aNoLessThanBTest() {
        Assertions.assertThrows(ANoLessThanBException.class, () -> DigitCount.digitCount(1000000, 1000000));
        Assertions.assertThrows(ANoLessThanBException.class, () -> DigitCount.digitCount(999999999998L, 1000000));
        Assertions.assertThrows(ANoLessThanBException.class, () -> DigitCount.digitCount(1, 1));
        Assertions.assertThrows(ANoLessThanBException.class, () -> DigitCount.digitCount(999999999998L, 2));
    }

    @Test
    public void AOrBOutOfBoundTest() {
        Assertions.assertThrows(NumberOutOfBoundException.class, () -> DigitCount.digitCount(0, 1));
        Assertions.assertThrows(NumberOutOfBoundException.class, () -> DigitCount.digitCount(0, 2));
        Assertions.assertThrows(NumberOutOfBoundException.class, () -> DigitCount.digitCount(0, 1000000));
        Assertions.assertThrows(NumberOutOfBoundException.class, () -> DigitCount.digitCount(0, 999999999998L));
        Assertions.assertThrows(NumberOutOfBoundException.class, () -> DigitCount.digitCount(0, 999999999999L));
        Assertions.assertThrows(NumberOutOfBoundException.class, () -> DigitCount.digitCount(0, 10000000000000L));
        Assertions.assertThrows(NumberOutOfBoundException.class, () -> DigitCount.digitCount(1, 10000000000000L));
        Assertions.assertThrows(NumberOutOfBoundException.class, () -> DigitCount.digitCount(2, 10000000000000L));
        Assertions.assertThrows(NumberOutOfBoundException.class, () -> DigitCount.digitCount(1000000, 10000000000000L));
        Assertions.assertThrows(NumberOutOfBoundException.class, () -> DigitCount.digitCount(999999999998L, 10000000000000L));
        Assertions.assertThrows(NumberOutOfBoundException.class, () -> DigitCount.digitCount(999999999999L, 10000000000000L));
    }

}