java - 提高 codility 的代码性能

Question

今天我听说了一个名为 codility 的网站，用户可以在其中进行各种编程测试以检查其代码的性能。

当我开始时，他们向我展示了这个样本测试，

Task description A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y. The small frog always jumps a fixed distance, D. Count the minimal number of jumps that the small frog must perform to reach its target.

Write a function: class Solution { public int solution(int X, int Y, int D); } that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y.

For example, given:
X = 10
Y = 85
D = 30 the function should return 3, because the frog will be positioned as follows:

after the first jump, at position 10 + 30 = 40

after the second jump, at position 10 + 30 + 30 = 70

after the third jump, at position 10 + 30 + 30 + 30 = 100

Assume that: X, Y and D are integers within the range

[1..1,000,000,000]; X ≤ Y. Complexity: expected worst-case time

complexity is O(1); expected worst-case space complexity is O(1).

这个问题非常简单，我花了大约 2 分钟的时间来编写解决方案，如下所示，

class Solution {
    public int solution(int X, int Y, int D) {

        int p = 0;
        while (X < Y){
            p++;
            X = X + D;
        }
    return p;
    }
}

但是，测试结果显示我的代码的性能只有20%，我的得分只有55%，

这是结果的链接，https://codility.com/demo/results/demo66WP2H-K25/

那是非常简单的代码，我只用了一个 while 循环，它怎么可能变得更快？

Answer 1

基础数学:

X + nD >= Y
nD >= Y - X
n >= (Y - X) / D

n 的最小值将是 (Y - X) 除以 D 的舍入结果。

这个操作的大O分析:

• 复杂度:O(1)。这是一个区别，一个 split 和一个综合
• 最坏情况下的空间复杂度为 O(1):您最多可以再添加 3 个变量:
  • Y - X 的差异，让我们将其分配给 Z。
  • Z 除以 D，我们将其分配给 E。
  • 将 E 向上舍入，让我们将其分配给 R(来自结果)。