磁带均衡训练
我前几天接到了一份关于工作的痘痘测试，因此我一直在练习使用他们的培训页面中的一些问题Link
不幸的是，我只能在Tape-Equilibrium问题上得到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/
任何帮助将不胜感激，我想确保我没有犯任何基本错误。
您的解决方案已经是O（N）。 你需要从sumleft和sumright中删除abs。
if (Math.abs( sumleft - sumright ) < ans) { ans = Math.abs( sumleft - sumright ); }
在第二个for循环之前，
ans =Math.abs( sumleft - sumright );
它应该工作。
100％ ，在Javascript中
var i, ll = A.length, tot = 0, upto = 0, min = Number.MAX_INT; for (i=0; i
考虑Ruby中的这个100/100解决方案：
# Algorithm: # # * Compute the sum of all elements. # * Iterate over elements, maintain left and right weights appropriately. # * Maintain a minimum of `(left - right).abs`. def solution(ar) sum = ar.inject(:+) left = ar[0] right = sum - left min_diff = (right - left).abs 1.upto(ar.size - 2) do |i| left += ar[i] right -= ar[i] diff = (right - left).abs min_diff = [min_diff, diff].min end # Result. min_diff end #--------------------------------------- Tests def test sets = [] sets << ["1", 1, [1]] sets << ["31", 2, [3, 1]] sets << ["312", 0, [3, 1, 2]] sets << ["[1]*4", 0, [1]*4] sets << ["[1]*5", 1, [1]*5] sets << ["sample", 1, [3, 1, 2, 4, 3]] sets.each do |name, expected, ar| out = solution(ar) raise "FAILURE at test #{name.inspect}: #{out.inspect} != #{expected.inspect}" if out != expected end puts "SUCCESS: All tests passed" end
一些C＃为你。
using System; // you can also use other imports, for example: // using System.Collections.Generic; class Solution { public int solution(int[] A) { // write your code in C# with .NET 2.0 int sumRight = 0; for(int i=0; i
我也遇到了像CTB一样有83％的问题，但对于我的C ++解决方案。
对于我的代码，我的磁带总和是在更新权利和leftsum之后进行评估，但其中存在问题。 在这种情况下，第二个循环应该进行评估，直到P = A.size（） – 1。 否则，您将最终评估一个磁带对，其中所有内容都添加到leftsum，并且没有任何内容添加到rightsum（根据问题描述不允许）。
关于我的解决方案的一个可能很好的方面（现在固定为100％）是，与上面的几个解决方案相比，它对总和的评估少了一次。
#include int solution(vector &A) { int sumright = 0; int sumleft; int result; for (int i=1; i
这是我刚刚为它编写的解决方案（Java），非常简单易懂，是O（n）并且在编码方面100％得分：
public int solution(int[] A) { if (A.length == 2) return Math.abs(A[0]-A[1]); int [] s1 = new int[A.length-1]; s1[0] = A[0]; for (int i=1;i=0;i--) { s2[i] = s2[i+1] + A[i+1]; } int finalSum = Integer.MAX_VALUE; for (int j=0;j
上面发布的类似CTB算法：该代码在JAVA中获得100％的分数;
class Solution { public int solution(int[] A) { int [] diff; int sum1; int sum2=0; int ans, localMin; diff = new int[A.length-1]; //AT P=1 sum1=A[0] sum1=A[0]; for (int i =1;i
}
这是我在Python中的100分代码可能对你有所帮助。 如果你有N = 2 A = [ – 1,1]，当你得到总和时你应该看看它是否会阻止“双重误差”你得到0但它应该返回| -1-1 | = | -2 | = 2
def solution(A): a=A tablica=[] tablica1=[] suma=0 if len(a) == 2: return abs(a[0]-a[1]) for x in a: suma = suma + x tablica.append(suma) for i in range(len(tablica)-1): wynik=(suma-2*tablica[i]) tablica1.append(abs(wynik)) tablica1.sort() return tablica1[0]
我的C＃代码100/100：
using System; class Solution { public int solution (int[] A) { int min = int.MaxValue; int sumLeft = 0; int sumRight = ArraySum (A); for (int i = 1; i < A.Length; i++) { int val = A[i - 1]; sumLeft += val; sumRight -= val; int diff = Math.Abs (sumLeft - sumRight); if (min > diff) { min = diff; } } return min; } private int ArraySum (int[] array) { int sum = 0; for (int i = 0; i < array.Length; i++) { sum += array[i]; } return sum; } }
C课程100％分数：Codility – TapeEquilibrium
int solution(int A[], int N) { int i, leftSum, rightSum, last_minimum, current_min; //initialise variables to store the right and left partition sum //of the divided tape //begin dividing from position 1 (2nd element) in a 0-based array //therefore the left partition sum will start with //just the value of the 1st element leftSum = A[0]; //begin dividing from position 1 (2nd element) in a 0-based array //therefore the right partition initial sum will start with //the sum of all array element excluding the 1st element rightSum = 0; i = 1; while (i < N) { rightSum += A[i]; i++; } //get the initial sum difference between the partitions last_minimum = abs(leftSum - rightSum); if (last_minimum == 0) return last_minimum; //return immediately if 0 diff found //begins shifting the divider starting from position 2 (3rd element) //and evaluate the diff, return immediately if 0 diff found //otherwise shift till the end of array length i = 2; //shift the divider while (i < N){ leftSum += A[i-1]; //increase left sum rightSum -= A[i-1]; //decrease right sum current_min = abs(leftSum - rightSum); //evaluate current diff if (current_min == 0) return current_min; //return immediately if 0 diff if (last_minimum > current_min) last_minimum = current_min; //evaluate //lowest min i++; //shift the divider } return last_minimum; }
我正在做同样的任务，但不能超过50分。 我的算法太慢了。 所以，我搜索了一个提示并找到了解决方案。 我已经使用了只对数组中的元素求和一次并获得100/100的想法。 我的解决方案是使用JavaScript，但它可以很容易地转换为Java。 您可以使用以下链接转到我的解决方案。
http://codility.com/demo/results/demo8CQZY5-RQ2/
请查看我的代码，如果您有任何问题，请告诉我。 我很乐意帮助你。
function solution(A) { // write your code in JavaScript 1.6 var p = 1; var sumPartOne = A[p - 1]; var sumPartTwo = sumUpArray(A.slice(p, A.length)); var diff = Math.abs(sumPartOne - sumPartTwo); for(p; p < A.length - 1; p++) { sumPartOne += A[p]; sumPartTwo -= A[p]; var tempDiff = Math.abs(sumPartOne - sumPartTwo); if(tempDiff < diff) { diff = tempDiff; } } return diff;
}
function sumUpArray(A) { var sum = 0; for(var i = 0; i < A.length; i++) { sum += A[i]; } return sum;
}
这是ruby中的100分
def solution(a) right = 0 left = a[0] ar = Array.new for i in 1...a.count right += a[i] end for i in 1...a.count check = (left - right).abs ar[i-1] = check left += a[i] right -= a[i] end find = ar.min if a.count == 2 find = (a[0]-a[1]).abs end find end
这就是我做的！ //使用.NET 2.0在C＃中编写代码
using System; class Solution { public int solution(int[] A) { int sumRight = 0, sumleft, result; for(int i=1; i
我在Chengays 上找到了完美的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; }
这是一个简单的C ++解决方案（100/100）：
#include #include int solution(vector &A) { int left = 0; int right = 0; int bestDifference = 0; int difference = 0; left = std::accumulate( A.begin(), A.begin() + 1, 0); right = std::accumulate( A.begin() + 1, A.end(), 0); bestDifference = abs(left - right); for( size_t i = 2; i < A.size(); i++ ) { left += A[i - 1]; right -= A[i - 1]; difference = abs(left - right); if( difference < bestDifference ) { bestDifference = difference; } } return bestDifference; }
C课程100％分数：Codility
int solution(int A[], int N) { long p; long index; long leftSum; long rightSum; long totalSum=0; long last_minimum=100000; long current_min; if(N==2) return abs(A[0]-A[1]); if(N==1) return abs(A[0]); for(index=0; index < N; index++) totalSum = totalSum + A[index]; leftSum = 0; rightSum = 0; for (p = 1; p <= N-1; p++) { leftSum += A[p - 1]; rightSum = totalSum - leftSum; current_min = abs((long)(leftSum - rightSum)); last_minimum = current_min < last_minimum ? current_min : last_minimum; if (last_minimum == 0) break; } return last_minimum; } int abs(int n) { return (n >= 0) ? n : (-(n)); }
100％得分：磁带均衡：Codility：JavaScript
function solution(A) { // write your code in JavaScript (ECMA-262, 5th edition) var p=0; var index=0; var leftSum=0; var rightSum=0; var totalSum=0; var N = A.length; var last_minimum=100000; if(A.length == 2) return (Math.abs(A[0]-A[1])); if(A.length == 1) return (Math.abs(A[0])); for(index=0; index < N; index++) totalSum = totalSum + A[index]; for(p=1; p <= N-1; p++){ leftSum += A[p - 1]; rightSum = totalSum - leftSum; current_min = Math.abs(leftSum - rightSum); last_minimum = current_min < last_minimum ? current_min : last_minimum; if (last_minimum === 0) break; } return last_minimum; }
def TapeEquilibrium (A): n = len(A) pos = 0 diff= [0] if len(A) == 2: return abs(a[0]-a[1]) for i in range(1,n-1,1): diff.sort() d = (sum(A[i+1:n-1]) - sum(A[0:i])) diff.append(abs(d) + 1) if abs(d) < diff[1]: pos = i + 1 return pos
public static int solution(int[] A) { int SumLeft=0; int SumRight = 0; int bestValue=0; for (int i = 0; i < A.Length; i++) { SumRight += A[i]; } bestValue=SumRight; for(int i=0;i
索引的起点和终点不正确 – 因此“双打”测试失败，因为此测试仅具有起点和终点。 如果使用的数字集合没有恰好包含对端点的依赖性，则可能会通过其他测试。
设N = A.length求和是右边的总和。 其最大值应排除A [N]，但包括A [0]。 sumleft – 从左边的总和。 其最大值应包括A [0]但不包括A [N]。 因此，在第一个循环中错误地计算了最大求和率。 类似地，在第二循环中，由于排除了A [0]，因此不计算sumleft的最大值。 Nadesri指出了这个问题，但我认为如果我明确指出代码中的错误会有用，因为那是你最初提出的问题。 这是我用c99编写的解决方案。 https://codility.com/demo/results/demoQ5UWYG-5KG/
这是我的100/100 Python解决方案：
def TapeEquilibrium(A): left = A[0] right = sum(A[1::]) diff = abs(left - right) for p in range(1, len(A)): ldiff = abs(left - right) if ldiff < diff: diff = ldiff left += A[p] right -= A[p] return diff