java - 从1开始，我最多可以使用N次，可以数到多少

Question

我的问题如下:对于数字N，当每个数字可以使用N次时，我需要找出可以计数的最大值。

例如，如果N = 5，则最大值为12，因为此时数字1已被使用5次。

我最初的方法是简单地遍历所有数字，并统计到目前为止每个数字已使用了多少次。当N很大时，这显然是非常低效的，因此我正在寻找有关实现此目标的更智能(更有效)方式的建议。

public class Counter {

    private static Hashtable<Integer, Integer> numbers;

    public static void main(String[] args){
        Counter c = new Counter();
        c.run(9);
    }

    public Counter() {
        numbers = new Hashtable<Integer, Integer>();

        numbers.put(0, 0);
        numbers.put(1, 0);
        numbers.put(2, 0);
        numbers.put(3, 0);
        numbers.put(4, 0);
        numbers.put(5, 0);
        numbers.put(6, 0);
        numbers.put(7, 0);
        numbers.put(8, 0);
        numbers.put(9, 0);

    }

    public static void run(int maxRepeat) {

        int keeper = 0;

        for(int maxFound = 0; maxFound <= maxRepeat; maxFound++) {
            keeper++;
            for (int i = 0; i < Integer.toString(keeper).length(); i++) {
                int a = Integer.toString(keeper).charAt(i);
                 //here update the tally for appropriate digit and check if max repeats is reached
                }
            }

        System.out.println(keeper);
    }
}

Answer 1

对于初学者，不要使用Counter支持Hashtable，而应使用int[]。当您确切知道地图必须包含多少个元素时，尤其是当键是数字时，数组就是完美的选择。

话虽如此，我认为最有效的加速可能来自更好的数学，而不是更好的算法。经过一些试验(或者很明显)，您会注意到1始终是给定次数使用的第一个数字。因此，给定N，如果您可以找到第一个使用1位数N+1的数字，那么您知道答案就是在此之前的数字。这样一来，您就可以解决问题，而不必实际计算那么高。

现在，让我们看看使用多少个1来计数各种数字。在本篇文章中，当我们尝试计算要使用多少个1表示一个数字时，我将使用n来指定一个数字，而大写N指定使用多少个1表示某个数字。

一位数字

以一位数字开头:

1:  1
2:  1
...
9:  1

显然，一个数字最多需要1的个数是... 1.好吧，实际上我们忘记了一个:

0:  0

稍后将很重要。因此，我们应该这样说:计数至一位数字 X所需的1的数量为 X > 0 ? 1 : 0。让我们定义一个数学函数 f(n)，它将表示“计数到 n所需的1的数量”。然后

f(X) = X > 0 ? 1 : 0

两位数字

对于两位数的数字，有两种类型。对于 1X形式的数字，

10: 2
11: 4
12: 5
...
19: 12

您可以这样想:最多 1X要求数字1等于

f(9)(最多9个)加上

1(从10起)加上

X(如果是1X，则从11-包括X > 0的前几位开始)加上

，但要计算X，需要许多1

或者在数学上，

f(1X) = f(9) + 1 + X + f(X)

然后是两位数大于19的数字:

21: 13
31: 14
...
91: 20

用 YX计数到两位数字 Y > 1所需的1的数量为

f(19)(最多19个)加上

f(9) * (Y - 2)(从数字20中的1到包含(Y-1)9的数字-就像Y = 5，我的意思是20-49中的1，来自21、31、41)加上

，但要计算X，需要许多1

或者在数学上，对于 Y > 1，

f(YX) = f(19) + f(9) * (Y - 2) + f(X)
      = f(9) + 1 + 9 + f(9) + f(9) * (Y - 2) + f(X)
      = 10 + f(9) * Y + f(X)

三位数

一旦输入三位数，就可以扩展模式。对于 1YX形式的任何三位数(现在 Y可以是任何数字)，从计数到该数字的总1等于

f(99)(最多99个)加上

1(从100起)加上

10 * Y + X(从101- 1YX的前两位开始)加上

，但要两位数的YX最多需要1个数字

所以

f(1YX) = f(99) + 1 + YX + f(YX)

注意 f(1X)的并行。继续逻辑到更多数字，以1开头的数字的模式为

f(1[m-digits]) = f(10^m - 1) + 1 + [m-digits] + f([m-digits])

其中 [m-digits]表示长度为 m的数字序列。

现在，对于不以1开头的三位数数字 ZYX(即 Z > 1)，要计数到它们的位数为1

f(199)(从计数到199)加上

f(99) * (Z - 2)(从200到(Z-1)99中的1表示)加上

，但要计算YX，需要许多1

所以

f(ZYX) = f(199) + f(99) * (Z - 2) + f(YX)
       = f(99) + 1 + 99 + f(99) + f(99) * (Z - 2) + f(YX)
       = 100 + f(99) * Z + f(YX)

现在，不以1开头的数字的模式似乎很清楚:

f(Z[m-digits]) = 10^m + f(10^m - 1) * Z + f([m-digits])

一般情况

我们可以将最后一个结果与以1开头的数字的公式结合起来。您应该能够验证以下公式是否等效于上面给出的所有数字 Z 1-9的适当情况，并且该方法正确无误当 Z == 0时:

f(Z[m-digits]) = f(10^m - 1) * Z + f([m-digits])
                                + (Z > 1) ? 10^m : Z * ([m-digits] + 1)

对于 10^m - 1形式的数字，例如99、999等，您可以直接评估该函数:

f(10^m - 1) = m * 10^(m-1)

因为数字1将在每个 10^(m-1)数字中使用 m次数-例如，当计数到999时，百位使用100 1，十位使用100 1，百位使用100用1代替。所以这变成

f(Z[m-digits]) = Z * m * 10^(m-1) + f([m-digits])
                                  + (Z > 1) ? 10^m : Z * ([m-digits] + 1)

您可以修改确切的表达方式，但无论如何对于这种特定方法，我认为这已经非常接近了。这里具有的递归关系使您可以通过在每一步剥离前导数字来评估 f(n)，即达到 n所需的1的数量。它的时间复杂度是 n的对数。

实作

鉴于上面的最后一个公式，实现此功能非常简单。从技术上讲，您可以在递归中摆脱一个基本情况:空字符串，即 f("")定义为0。但这将为您节省一些调用，以便处理单个数字以及 10^m - 1形式的数字。省略一些参数验证的方法如下:

private static Pattern nines = Pattern.compile("9+");

/** Return 10^m for m=0,1,...,18 */
private long pow10(int m) {
    // implement with either pow(10, m) or a switch statement
}

public long f(String n) {
    int Z = Integer.parseInt(n.substring(0, 1));
    int nlen = n.length();
    if (nlen == 1) {
        return Z > 0 ? 1 : 0;
    }
    if (nines.matcher(n).matches()) {
        return nlen * pow10(nlen - 1);
    }
    String m_digits = n.substring(1);
    int m = nlen - 1;
    return Z * m * pow10(m - 1) + f_impl(m_digits)
        + (Z > 1 ? pow10(m) : Z * (Long.parseLong(m_digits) + 1));
}

倒相

该算法解决了您所提出的问题的反面问题:也就是说，它计算出一个数字被累加到 n的次数，而您想知道在给定数字 n的情况下可以达到的 N(即1)。因此，正如我在开头提到的那样，您正在寻找第一个 n的 f(n+1) > N。

最简单的方法是从 n = 0开始计数，看看何时超过 N。

public long howHigh(long N) {
    long n = 0;
    while (f(n+1) <= N) { n++; }
    return n;
}

但是，这当然不比在数组中累加计数更好(实际上可能更糟)。拥有 f的全部目的是您不必测试每个数字。您可以大幅度地跳起来，直到找到 n这样的 f(n+1) > N，然后使用跳转来缩小搜索范围。我推荐的一种相当简单的方法是 exponential search在结果上设置上限，然后进行二进制搜索以缩小范围:

public long howHigh(long N) {
    long upper = 1;
    while (f(upper + 1) <= N) {
        upper *= 2;
    }
    long lower = upper / 2, mid = -1;
    while (lower < upper) {
        mid = (lower + upper) / 2;
        if (f(mid + 1) > N) {
            upper = mid;
        }
        else {
            lower = mid + 1;
        }
    }
    return lower;
}

由于上面的 f的实现是O(log(n))，指数+二进制搜索也是O(log(n))，因此最终算法应该类似于O(log ^ 2(n))，我认为N和n之间的关系足够线性，因此您也可以将其视为O(log ^ 2(N))。如果您在日志空间中搜索并明智地缓存该函数的计算值，则有可能将其降低到大约O(log(N))。确定上限后，可能会显着提高速度的一个变体会停留在 interpolation search轮中，但是正确编码很棘手。完全优化搜索算法可能是另一个问题。