胶带平衡Codility培训[已关闭]

algorithm java puzzle

2022-09-01 15:15:01

前几天，我收到了一份工作的溺爱测试，因此我一直在练习使用他们培训页面Link中的一些问题。

不幸的是，我只在磁带均衡问题上得到了83/100：

给出了一个由 N 个整数组成的非空零索引数组 A。数组 A 表示磁带上的数字。
任何整数 P，使得，将此磁带拆分为两个非空部分：。
两个部分之间的差值是：
换句话说，它是第一部分的总和与第二部分的总和之间的绝对差值。0 < P < NA\[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])|

编写一个函数，给定一个非空的零索引数组 A（N 个整数），返回可以实现的最小差值。

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

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有点生气。它失败的两个测试区域是“双精度”（我认为是两个值，-1000和1000，以及“小”。http://codility.com/demo/results/demo9DAQ4T-2HS/

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

答案 1

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

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

同样在第二个 for 循环之前，

ans =Math.abs( sumleft - sumright );

它应该有效。

答案 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;