磁带均衡训练

Question

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

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

给出了由N个整数组成的非空零索引数组A. 数组A表示磁带上的数字.
任何整数P,使得0 <P <N,将该磁带分成两个非空部分:A [0],A [1],...,A [P-1]和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是一个int,范围[2..100,000]; A的每个元素都是一个int,范围[-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感到有点生气.它失败的两个测试区域是"双"(我认为是两个值,-1000和1000,以及"小" .http://codility.com/demo/results/demo9DAQ4T-2HS/

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

Answer 1

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

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

在第二个for循环之前,

ans =Math.abs( sumleft - sumright );

它应该工作.

Answer 2

100%,在Javascript中

var i, ll = A.length, tot = 0, upto = 0, min = Number.MAX_INT;

for (i=0; i<ll; i++) tot += A[i];

for (i=0; i<ll-1; i++)
{
    upto += A[i];
    var a1 = upto, a2 = tot - a1, dif = Math.abs(a1 - a2);
    if (dif < min)
         min = dif;
}

return min;

Answer 3

我在 Codesays上找到了 Cheng 对 TapeEquilibrium 的完美解决方案。我将它翻译成 Java，供任何对此感到好奇的人使用。Cheng 的解决方案在 Codility 上达到了100%

    public int solution(int[] A) {

    // write your code in Java SE 7
    int N = A.length;

    int sum1 = A[0];
    int sum2 = 0;
    int P = 1;
    for (int i = P; i < N; i++) {
        sum2 += A[i];
    }
    int diff = Math.abs(sum1 - sum2);

    for (; P < N-1; P++) {
        sum1 += A[P];
        sum2 -= A[P];

        int newDiff = Math.abs(sum1 - sum2);
        if (newDiff < diff) {
            diff = newDiff;
        }
    }
    return diff;
}