java - 磁带平衡顺应性训练

Question

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

不幸的是，我在磁带平衡问题上只能得到 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 的每个元素都是一个 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/

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

score 15 · Accepted Answer

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

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

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

ans =Math.abs( sumleft - sumright );

它应该工作。

score 13 · Accepted Answer

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;

score 7 · Accepted Answer

我在 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;
}

score 4 · Accepted Answer

这是我的 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

score 4 · Accepted Answer

考虑一下 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

score 3 · Accepted Answer

一些 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<A.Length; i++)
        {
            sumRight += A[i];
        }

        int sumLeft = 0;
        int min = int.MaxValue;
        for(int P=1; P<A.Length; P++)
        {
            int currentP = A[P-1];
            sumLeft += currentP;
            sumRight -= currentP;

            int diff = Math.Abs(sumLeft - sumRight);
            if(diff < min)
            {
                min = diff;
            }
        }
        return min;
    }
}

score 3 · Accepted Answer

这是我刚刚为它编写的解决方案（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<A.length-1;i++) {
        s1[i] = s1[i-1] + A[i];
    }

    int [] s2 = new int[A.length-1];
    s2[A.length-2] = A[A.length-1];
    for (int i=A.length-3;i>=0;i--) {
        s2[i] = s2[i+1] + A[i+1];
    }

    int finalSum = Integer.MAX_VALUE;
    for (int j=0;j<s1.length;j++) {
        int sum = Math.abs(s1[j]-s2[j]);
        if (sum < finalSum)
            finalSum = sum;
    }
    return finalSum;
}

score 2 · Accepted Answer

我的 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;
    }
}

score 2 · Accepted Answer

我也遇到了像 CTB 一样获得 83% 的问题，但对于我的 C++ 解决方案。

对于我的代码，我的磁带总和是在更新 rightsum 和 leftsum 之后评估的，但问题就在这里。在这种情况下，第二个循环应该计算直到 P=A.size()-1。否则，您最终将评估一个磁带对，其中所有内容都添加到leftsum，并且没有任何内容添加到rightsum（根据问题描述，这是不允许的）。

关于我的解决方案（现在固定为 100%）的一个可能好的方面是，与上面的几个解决方案相比，它对总和的评估少了一次。

#include <stdlib.h>

int solution(vector<int> &A) {
    int sumright = 0;
    int sumleft;
    int result;

for (int i=1; i<A.size(); i++) {
    sumright += A[i];
}
sumleft = A[0];

result = abs(sumleft-sumright);
for (int i=1; i<A.size()-1; i++) {
    sumleft  += A[i];
    sumright -= A[i];
    if (abs(sumleft-sumright)<result) {
        result = abs(sumleft-sumright);
    }
}

return result;
}

score 2 · Accepted Answer

100% 分数：磁带平衡：可编码性：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;
}

score 2 · Accepted Answer

我正在做同样的任务，但不能超过 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;

}

score 1 · Accepted Answer

这是我在 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]

score 1 · Accepted Answer

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; 
}

score 1 · Accepted Answer

上面发布的 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<A.length;i++){
        sum2 += A[i];
    }

    ans = Math.abs(sum1- sum2);

    for (int p= 1;p<A.length;p++){
        localMin= Math.abs(sum1- sum2);

        if( localMin < ans ){
           ans = localMin;
        }
        //advance the sum1, sum2
        sum1+= A[p];
        sum2-= A[p];
        diff[p-1]=localMin;
    }
    return (getMinVal(diff));    
}  

public int getMinVal(int[] arr){ 
    int minValue = arr[0]; 
    for(int i=1;i<arr.length;i++){
        if(arr[i] < minValue){ 
            minValue = arr[i]; 
        } 
    } 
    return minValue; 
}

}

score 0 · Accepted Answer

Here is an easy solution in C++ (100/100):

#include <numeric>
#include <stdlib.h>

int solution(vector<int> &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;
}

score 0 · Accepted Answer

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

score 0 · Accepted Answer

这就是我所做的！！！// 使用 .NET 2.0 用 C# 编写代码

   using System;

   class Solution
 {
  public int solution(int[] A)

 {      

 int sumRight = 0, sumleft, result;

    for(int i=1; i<A.Length; i++)
    {
        sumRight += A[i];
    }

    int sumLeft = A[0];
    int min = int.MaxValue;
    for(int P=1; P<A.Length; P++)
    {
        int currentP = A[P-1];
        sumLeft += currentP;
        sumRight -= currentP;

        int diff = Math.Abs(sumLeft - sumRight);
        if(diff < min)
        {
            min = diff;
        }
    }
    return min;
   }
  }

score 0 · Accepted Answer

索引的起点和终点不正确 - 因此“双打”测试失败，因为该测试只有起点和终点。如果使用的一组数字恰好不包含对端点的依赖关系，则其他测试可能会通过。

设 N = A.length sumright 是右边的总和。其最大值应不包括 A[N]，但应包括 A[0]。sumleft - 从左边求和。它的最大值应包括 A[0] 但不包括 A[N]。因此，在第一个循环中错误地计算了最大 sumright。类似地，在第二个循环中，不计算 sumleft 的最大值，因为 A[0] 被排除在外。Nadesri 指出了这个问题，但我认为如果我明确指出您的代码中的错误会很有用，因为那是您最初要求的。这是我用 c99 编写的解决方案。 https://codility.com/demo/results/demoQ5UWYG-5KG/

score 0 · Accepted Answer

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));
}

score 0 · Accepted Answer

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<A.Length;i++)
        {
            SumLeft += A[i];
            SumRight-=A[i];
            if (Math.Abs(SumLeft - SumRight) < bestValue)
            {
                bestValue = Math.Abs(SumLeft - SumRight);
            }

        }
        return bestValue;

    }

score 0 · Accepted Answer

这是红宝石的 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

java - 磁带平衡顺应性训练

21 回答 21

Related

Reference