时间戳

首页 > 解决方案 > 使用 Java 编写代码中的 PassingCars 问题

java - 使用 Java 编写代码中的 PassingCars 问题

问题描述

我正在做代码任务。我目前正在通过汽车任务 - https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/；

其中一项性能测试，我得到“错误答案，得到 -1794967296 预期 -1”

（性能测试名称为“large_big_answer 0..01..1，长度 = ~100,000”）

其他测试做得很好

我想知道如何纠正这个错误

这是我的代码

class Solution {
    public int solution(int[] A) {
        int mul = 0;
        int cnt = 0;
        for(int i = 0 ; i<A.length ; i++){
            if(A[i] == 0) mul++;
            else cnt = cnt+mul;
        }
        if(cnt>1000000000) return -1;
        return cnt;
    }
}

标签： javaperformance

解决方案

正如@Nicholas K 所指出的，这个问题确实与溢出有关。

将检查if (cnt > 1_000_000_000)移到 for 循环中。要求是：

如果经过的汽车对数超过 1,000,000,000，则该函数应返回 -1。

因此，一旦对数超过计数，则停止。

所以，

public int solution(int[] A) {
    int mul = 0;
    int cnt = 0;
    for(int i = 0 ; i<A.length ; i++){
        if(A[i] == 0) mul++;
        else cnt = cnt+mul;

        if(cnt>1000000000) return -1;
    }

    return cnt;
}

这是一个显示失败的测试用例：

@Test
public void testHalfEach() {
    final int[] inp = new int[100_000];
    final int exp = -1;
    Arrays.fill(inp, 0, 50_000, 0);
    Arrays.fill(inp, 50_000, 100_000, 1);
    validate(inp, exp);
}

private void validate(int[] inp, int exp)
{
    PassingCars prog = new PassingCars();
    int ans = prog.solution(inp);
    assertEquals(exp, ans);
}

更改检查的位置将允许此测试通过。

推荐阅读