java – 从1开始可以算多远,当我可以使用任何数字时最多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);
    }
}

对于初学者而言,不是使用Hashtable支持你的Counter,而是使用int [].当您确切地知道地图必须具有多少元素时,尤其是当键是数字时,数组是完美的.

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

现在,让我们来看看有多少1用于计算各种数字.在这篇文章中,我将使用n来指定一个数字,当我们试图计算出有多少1用于计算数字时,而大写字母N表示用多少1来计算某个数字.

一位数字

从一位数字开头：

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

显然,计算一位数字所需的1的数量是…… 1.嗯,实际上我们忘记了一个：

0:  0

这在以后会很重要.所以我们应该这样说：计数到一位数X所需的1的数量是X> 1. 0？ 1：0.让我们定义一个数学函数f(n),它代表“计数到n所需的1的数量”.然后

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

两位数字

对于两位数字,有两种类型.对于1X形式的数字,

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

您可以这样想：计数高达1X需要等于1的1

> f(9)(从最多计数到9)加上
> 1(从10)加
> X(从11-1X的前几位,如果X> 0)加上
>然而,需要很多1来计算X

或者数学上,

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

然后有两位数字高于19：

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

计数为两位数YX所需的1的数量,其中Y> 1是

> f(19)(从数到19)加上
> f(9)*(Y – 2)(从数字20到(Y-1)9的1中包含 – 如果Y = 5,我的意思是20-49中的1,来自21,31,41 )加
>然而,需要很多1来计算X

或者在数学上,对于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的第一个数字开始)加上
>然而,需要多个1来计算两位数的YX

所以

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,计算它们所需的1的数量是

> f(199)(从数到199)加上
> f(99)*(Z – 2)(从200-(Z-1)99中的1开始)加上
>然而,需要很多1来计算YX

所以

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将在每个m个数字中使用10 ^(m-1)次 – 例如,当计数到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′).所以,正如我在开始时提到的那样,你正在寻找f(n 1)>的第一个n. 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的一轮中,但是编码正确是很棘手的.尽管如此,完全优化搜索算法可能是另一个问题.