一尘不染

磁带均衡的Codility培训

algorithm

前几天,我接受了一项职业能力测试,因此我一直在练习使用他们培训页面上的一些问题 链接

不幸的是,我在磁带均衡问题上只能得到83/100:

给出了一个由N个整数组成的非空零索引数组A。数组A代表磁带上的数字。
任何整数P,例如0 < P < N,将磁带分割成两个非空部分:A\[0], A\[1], …, A\[P − 1] and A\[P], A\[P + 1], …, A\[N − 1]
这两个部分之间的 是以下值:|(A\[0] + A\[1] + … + A\[P − 1]) − (A\[P] + A\[P + 1] + … + A\[N − 1])| 换句话说,它是第一部分之和与第二部分之和之间的 绝对 差。

编写一个函数,该函数在给定N个整数的非空零索引数组A的情况下,返回可以实现的最小差异。

示例:A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3
我们可以将此磁带分成四个位置:
P = 1,差= | 3 − 10 | = 7
P = 2,差异= | 4 − 9 | = 5
P = 3,差= | 6 − 7 | = 1
P = 4,差= | 10 − 3 | = 7
在这种情况下,我将返回1,因为它是最小的差异。

N是一个整数,范围[2..100,000];A的每个元素都是一个整数,范围为[−1,000..1,000]。时间复杂度为O(n),

我的代码如下:

import java.math.*;
class Solution {
public int solution(int[] A) {

    long sumright = 0;
    long sumleft = 0;
    long ans;

    for (int i =1;i<A.length;i++)
        sumright += A[i];

    sumleft = A[0];
    ans =Math.abs(Math.abs(sumright)+Math.abs(sumleft));

    for (int P=1; P<A.length; P++)
    {
        if (Math.abs(Math.abs(sumleft) - Math.abs(sumright))<ans)
            ans = Math.abs(Math.abs(sumleft) - Math.abs(sumright));
        sumleft += A[P];
        sumright -=A[P];
    }
    return (int) ans;  
}

我对Math.abs有点生气。它失败的两个测试区域是“ double”(我认为是两个值,-1000和1000,以及“ small”。http://codility.com/demo/results/demo9DAQ4T-2HS/

任何帮助将不胜感激,我想确保我没有犯任何基本错误。


阅读 303

收藏
2020-07-28

共1个答案

一尘不染

您的解决方案已经是O(N)。您需要从sumleft和sumright中删除abs。

if (Math.abs( sumleft - sumright ) < ans)
{
  ans = Math.abs( sumleft - sumright );
}

同样在第二个for循环之前

ans =Math.abs( sumleft - sumright );

它应该工作。

2020-07-28