相关疑难解决方法(0)

Imagine you sell those metallic digits used to number houses, locker doors, hotel rooms, etc. You need to find how many of each digit to ship when your customer needs to number doors/houses:

• 1 to 100
• 51 to 300
• 1 to 2,000 with zeros to the left

The obvious solution is to do a loop from the first to the last number, convert the counter to a string with or without zeros to the left, extract each digit and use …

在编程竞赛中,以下模式出现在很多任务中:

给定数字A和B很大(可能是20个十进制数字或更多),确定具有特定属性P的A≤X≤B的整数X

SPOJ有许多这样的任务用于练习.

有趣的属性的例子包括:

• "X的数字总和是60"
• "X仅包含数字4和7"
• "X是回文",这意味着X的十进制表示等于其反向(例如,X = 1234321)

我知道如果我们将f(Y)定义为这样的整数X≤Y,那么我们问题的答案就是f(B) - f(A - 1).减少的问题是如何有效地计算函数f.在某些情况下,我们可以利用某些数学属性来提出公式,但通常属性更复杂,我们在比赛中没有足够的时间.

在很多情况下是否有更通用的方法？它是否也可以用于枚举具有给定属性的数字或计算它们上的一些聚合？

其变体是找到具有给定属性的第k个数,当然可以通过使用二进制搜索和计数函数来求解.

正如标题所说,给定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 ^ …