如何修复青蛙跳跃作业中浮点数到整数的舍入不正确

Question

为什么我的解决方案的性能测试失败：

class Solution {
    public int solution(int X, int Y, int D) {
        return (int) Math.ceil((Y-X)/(float)D);
    }
}

如何改进？

测试：

public class SolutionTest {
    private Solution solution;
    @Test
    public void defaultTest(){
        assertEquals(3, solution.solution(10,85,30));
    }
    @Test
    public void many_jump1Test(){
        assertEquals(499999998, solution.solution(-499999996,500000000,2));
    }
    @Before
    public void init(){
        solution = new Solution();
    }
}

Answer 1

我认为您的解决方案遇到了舍入误差，因为float缺乏精度。您的测试结果指出：

对于输入(3、999111321、7(，解决方案返回了错误的答案(142730192预期的142730189(。

给定该输入，让我们看一下如果我们使用 float 以及如果我们使用 double (X - Y) / D的结果：

float f = (999111321 - 3) / 7.0f;  // 1.42730192E8
double d = (999111321 - 3) / 7.0;  // 1.427301882857143E8
                                              ^^

请注意小数点前最后两位数字的舍入误差。为了避免这种情况并获得正确的答案，您只需将D转换为解决方案中的double而不是float。

Answer 2

整数运算要快得多，可以使用整数除法：

(Y - X + D - 1) / D

通常/ D会给出下限值。为了获得 ceil 值，D - 1 .

这样可以节省：

• double分部
• 采取Math.ceil()
• 转换为int