java - 给定一批 0-9 的整数，在我用完某个整数之前我能写的最后一个数字是多少？

Question

正如标题所说，给定一堆整数 0-9，在我用完某个整数之前我可以写的最后一个数字是多少？

因此，如果我有一个存货，比如从 0 到 9 的每个数字都有 10 个，那么在我用完某个数字之前我可以写的最后一个数字是多少。例如，对于 2 的股票，我可以写数字 1 ... 10:

1 2 3 4 5 6 7 8 9 10

此时我的库存为 0，我不能写 11。另请注意，如果给我的库存为 3，我仍然只能写数字 1 ... 10，因为 11 会花费我 2 个，这将使我的库存为 -1。

到目前为止我得到了什么:

public class Numbers {

public static int numbers(int stock) {
    int[] t = new int[10];
    for (int k = 1; ; k++) {

        int x = k;
        while (x > 0) {

            if (t[x % 10] == stock) return k-1;
            t[x % 10]++;
            x /= 10;

        }

    }
}

public static void main(String[] args) {
    System.out.println(numbers(4));

}

}

有了这个，我可以获得相当大库存的正确答案。库存大小为 10^6 时，代码在约 2 秒内完成，而库存为 10^7 的数字则需要整整 27 秒。这还不够好，因为我正在寻找一种可以处理高达 10^16 库存大小的解决方案，所以我可能需要一个 O(log(n)) 解决方案。

这是一个像作业一样的家庭作业，所以我没有在这个泡菜上挣扎了很长一段时间才来到这里。我没有通过谷歌搜索得出任何类似的结果，而且 wolfram alpha 无法识别这给出的任何类型的模式。

到目前为止我得出的结论是，那些总是会先用完。我没有证据，但确实如此。

任何人都可以提出任何建议吗？非常感谢。

---

编辑:

感谢 btilly 的指点(请参阅他的帖子和下面的评论。也标记为解决方案)，我想出了并实现了一种查找数字 1...n 成本的有效方法。我将在今天晚些时候实现二进制搜索以查找您可以用给定股票写入的最后一个数字后进一步详细说明。

---

编辑 2:解决方案

我完全忘记了这篇文章，所以我很抱歉没有在我的解决方案中编辑。不过，我不会复制实际的实现。

我用于查找数字成本的代码执行以下操作:

首先，让我们选择一个数字，例如9999. 现在我们将每个十位数字的成本相加得到成本，如下所示:

9 9 9 9
^ ^ ^ ^
^ ^ ^ roof(9999 / 10^1) * 10^0 = 1000
^ ^ roof(9999 / 10^2) * 10^1 = 1000
^ roof(9999 / 10^3) * 10^2 = 1000
roof(9999 / 10^4) * 10^3 = 1000

因此 9999 的成本是 4000。

256 也一样:

2 5 6
^ ^ ^
^ ^ roof(256 / 10^1) * 10^0 = 26
^ roof(256 / 10^2) * 10^1 = 30
roof(256 / 10^3) * 10^2 = 100

因此 256 的成本是 156。

实现这个想法将使程序只能处理没有数字 1 或 0 的数字，这就是为什么需要进一步的逻辑。让我们调用上面解释的方法 C(n, d)，其中 n 是我们要处理的数字获取成本，d 是 n 的第 d 位我们目前正在与之合作。我们还定义一个方法D(n, d)，它将返回 n d 个数字em>。然后我们将应用以下逻辑:

sum = C(n, d)

if D(n, d) is 1:
    for each k < d, k >= 0 :
        sum -= ( 9 - D(n, k) ) * 10^(k-1);

else if D(n, d) is 0:
    sum -= 10^(d-1)

有了这个，程序将有效地计算出一个数字的正确成本。在此之后，我们只需应用二进制搜索来查找具有正确成本的数字。

Answer 1

第 1 步。编写一个高效的函数来计算需要使用多少库存来写入所有数字，直到 N。 (提示:使用公式计算用于写出最后一位数字的所有内容，然后使用递归计算用于其他数字的所有内容。)

第 2 步。进行二进制搜索以找到您可以用库存量写的最后一个数字。