java - 重数计算的最佳有效解决方案？

Question

我需要找出两个整数之间重整数的个数 A和 B , 其中A <= B在任何时候。

An integer is considered heavy whenever the average of it's digit is larger than 7.

For example: 9878 is considered heavy, because (9 + 8 + 7 + 8)/4 = 8, while 1111 is not, since (1 + 1 + 1 + 1)/4 = 1.

我有下面的解决方案，但它绝对糟糕，并且在运行大量输入时会超时。我可以做些什么来提高效率？

int countHeavy(int A, int B) {
    int countHeavy = 0;

    while(A <= B){
        if(averageOfDigits(A) > 7){
            countHeavy++;
        }
        A++;
    }

    return countHeavy;
}
 
float averageOfDigits(int a) {
    float result = 0;
    int count = 0;

    while (a > 0) {
        result += (a % 10);
        count++;
        a = a / 10;
    }

    return result / count;
}

Answer 1

用查找表计算数字

您可以生成一个表，该表存储有多少个具有 d 位的整数，其数字之和大于数字 x。然后，您可以快速查找在 10、100、1000 ... 整数的任意范围内有多少重数。这些表只包含 9×d 个值，因此它们占用的空间很小并且可以快速生成。

然后，要检查范围 A-B，其中 B 有 d 个数字，您构建 1 到 d-1 个数字的表，然后将范围 A-B 分成10、100、1000 ... 的 block 并在表中查找值，例如对于范围 A = 782，B = 4321:

   RANGE      DIGITS  TARGET     LOOKUP      VALUE

 782 -  789     78x    > 6    table[1][ 6]     3    <- incomplete range: 2-9
 790 -  799     79x    > 5    table[1][ 5]     4
 800 -  899     8xx    >13    table[2][13]    15
 900 -  999     9xx    >12    table[2][12]    21
1000 - 1999    1xxx    >27    table[3][27]     0
2000 - 2999    2xxx    >26    table[3][26]     1
3000 - 3999    3xxx    >25    table[3][25]     4
4000 - 4099    40xx    >24    impossible       0
4100 - 4199    41xx    >23    impossible       0
4200 - 4299    42xx    >22    impossible       0
4300 - 4309    430x    >21    impossible       0
4310 - 4319    431x    >20    impossible       0
4320 - 4321    432x    >19    impossible       0    <- incomplete range: 0-1
                                              --
                                              48

如果第一个和最后一个范围不完整(不是 *0 - *9)，请根据目标检查起始值或结束值。 (在示例中，2 不大于 6，因此所有 3 个重数都包含在范围内。)

生成查找表

对于一位十进制整数，大于值x的整数n的个数是:

x:  0  1  2  3  4  5  6  7  8  9
n:  9  8  7  6  5  4  3  2  1  0

如您所见，这很容易通过取 n = 9-x 来计算。

对于2位十进制整数，其位数之和大于值x的整数n的个数是:

x:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18
n:  99 97 94 90 85 79 72 64 55 45 36 28 21 15 10  6  3  1  0

对于三位十进制整数，其位数之和大于值x的整数n的个数是:

x:   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27
n: 999 996 990 980 965 944 916 880 835 780 717 648 575 500 425 352 283 220 165 120  84  56  35  20  10   4   1   0

这些序列中的每一个都可以从前一个序列生成:从值 10^d 开始，然后从该值中减去前一个序列(跳过第一个零)。例如。要从 2 位数字的序列生成 3 位数字的序列，从 10³ = 1000 开始，然后:

 0. 1000 -   1      = 999
 1.  999 -   3      = 996
 2.  996 -   6      = 990
 3.  990 -  10      = 980
 4.  980 -  15      = 965
 5.  965 -  21      = 944
 6.  944 -  28      = 916
 7.  916 -  36      = 880
 8.  880 -  45      = 835
 9.  835 -  55      = 780
10.  780 -  64 +  1 = 717  <- after 10 steps, start adding the previous sequence again
11.  717 -  72 +  3 = 648
12.  648 -  79 +  6 = 575
13.  575 -  85 + 10 = 500
14.  500 -  90 + 15 = 425
15.  425 -  94 + 21 = 352
16.  352 -  97 + 28 = 283
17.  283 -  99 + 36 = 220
18.  220 - 100 + 45 = 165  <- at the end of the sequence, keep subtracting 10^(d-1)
19.  165 - 100 + 55 = 120
20.  120 - 100 + 64 =  84
21.   84 - 100 + 72 =  56
22.   56 - 100 + 79 =  35
23.   35 - 100 + 85 =  20
24.   20 - 100 + 90 =  10
25.   10 - 100 + 94 =   4
26.    4 - 100 + 97 =   1
27.    1 - 100 + 99 =   0

顺便说一句，如果“重”数定义为 7 以外的值，您可以使用相同的表。

---

代码示例

下面是演示该方法的 Javascript 代码片段(我不会说 Java)。它非常未经优化，但它在不到 0.07 毫秒的时间内完成了 0→100,000,000 示例。它也适用于 7 以外的权重。转换为 Java，它应该很容易击败任何实际运行数字并检查其权重的算法。

function countHeavy(A, B, weight) {
    var a = decimalDigits(A), b = decimalDigits(B);        // create arrays
    while (a.length < b.length) a.push(0);                 // add leading zeros
    var digits = b.length, table = weightTable();          // create table
    var count = 0, diff = B - A + 1, d = 0;                // calculate range
    for (var i = digits - 1; i >= 0; i--) if (a[i]) d = i; // lowest non-0 digit
    while (diff) {                                         // increment a until a=b
        while (a[d] == 10) {                               // move to higher digit
            a[d++] = 0;
            ++a[d];                                        // carry 1
        }
        var step = Math.pow(10, d);                        // value of digit d
        if (step <= diff) {
            diff -= step;
            count += increment(d);                         // increment digit d
        }
        else --d;                                          // move to lower digit
    }
    return count;

    function weightTable() {                               // see above for details
        var t = [[],[9,8,7,6,5,4,3,2,1,0]];
        for (var i = 2; i < digits; i++) {
            var total = Math.pow(10, i), final = total / 10;
            t[i] = [];
            for (var j = 9 * i; total > 0; --j) {
                if (j > 9) total -= t[i - 1][j - 10]; else total -= final;
                if (j < 9 * (i - 1)) total += t[i - 1][j];
                t[i].push(total);
            }
        }
        return t;
    }
    function increment(d) {
        var sum = 0, size = digits;
        for (var i = digits - 1; i >= d; i--) {
            if (a[i] == 0 && i == size - 1) size = i;      // count used digits
            sum += a[i];                                   // sum of digits
        }
        ++a[d];
        var target = weight * size - sum;
        if (d == 0) return (target < 0) ? 1 : 0;           // if d is lowest digit
        if (target < 0) return table[d][0] + 1;            // whole range is heavy
        return (target > 9 * d) ? 0 : table[d][target];    // use look-up table
    }
    function decimalDigits(n) {
        var array = [];
        do {array.push(n % 10);
            n = Math.floor(n / 10);
        } while (n);
        return array;
    }
}
document.write("0 &rarr; 100,000,000 = " + countHeavy(0, 100000000, 7) + "<br>");
document.write("782 &rarr; 4321 = " + countHeavy(782, 4321, 7) + "<br>");
document.write("782 &rarr; 4321 = " + countHeavy(782, 4321, 5) + " (weight: 5)");