前几天,我接受了一项职业能力测试,因此我一直在练习使用他们培训页面上的一些问题 链接
不幸的是,我在磁带均衡问题上只能得到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),
给出了一个由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])| 换句话说,它是第一部分之和与第二部分之和之间的 绝对 差。
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,因为它是最小的差异。
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有点生气。它失败的两个测试区域是“ double”(我认为是两个值,-1000和1000,以及“ small”。http://codility.com/demo/results/demo9DAQ4T-2HS/
任何帮助将不胜感激,我想确保我没有犯任何基本错误。
您的解决方案已经是O(N)。您需要从sumleft和sumright中删除abs。
if (Math.abs( sumleft - sumright ) < ans) { ans = Math.abs( sumleft - sumright ); }
同样在第二个for循环之前
ans =Math.abs( sumleft - sumright );
它应该工作。