java - テープ平衡コディリティトレーニング

Question

先日、就職の為にコディリティテストを受けたので、トレーニングページの リンクからいくつかの問題を使って練習してきました。

残念ながら、Tape-Equilibrium の質問では 83/100 しか得られませんでした。

N 個の整数で構成される空でないゼロ インデックスの配列 A が与えられます。配列 A は、テープ上の数字を表します。
のような任意の整数 P は、0 < P < Nこのテープを 2 つの空でない部分に分割しますA\[0], A\[1], …, A\[P − 1] and A\[P], A\[P + 1], …, A\[N − 1]。
2 つの部分の差は次の値です。|(A\[0] + A\[1] + … + A\[P − 1]) − (A\[P] + A\[P + 1] + … + A\[N − 1])|
つまり、最初の部分の合計と 2 番目の部分の合計の絶対差です。

N 個の整数の空でないゼロ インデックスの配列 A が与えられた場合に、達成できる最小の差を返す関数を作成します。

例: A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3
このテープを 4 つの場所に分割できます:
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 に少し腹を立てました。失敗する 2 つのテスト領域は「double」です (これは、-1000 と 1000 の 2 つの値と「small」だと思います 。http://codility.com/demo/results/demo9DAQ4T-2HS/

基本的な間違いを犯していないことを確認したいと思います。

Answer 1

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 2

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

Answer 3

これが私の 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

Answer 4

あなたのためにいくつかの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;
    }
}

Answer 5

I was doing the same task, but couldn't get better than 50 something points. My algorithm was too slow. So, I searched for a hint and found your solution. I've used the idea of summing the elements in the array only once and got 100/100. My solution is in JavaScript, but it can be easily transformed into Java. You can go to my solution by using the link below.

http://codility.com/demo/results/demo8CQZY5-RQ2/

Please take a look at my code and let me know if you have some questions. I'd be very happy to help you.

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;

}

Answer 6

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

Answer 7

上記の 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; 
}    

}

Answer 8

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

Answer 9

インデックスの開始点と終了点が正しくありません。このテストには開始点と終了点しかないため、「doubles」テストは失敗します。使用される数値のセットにエンドポイントへの依存関係が含まれていない場合、他のテストに合格する可能性があります。

N = A.length とします。sumright は右からの合計です。この最大値は、A[N] を除外する必要がありますが、A[0] を含める必要があります。sumleft - 左からの合計。この最大値には A[0] を含め、A[N] を除外する必要があります。そのため、最初のループで max sumright が誤って計算されます。同様に、2 番目のループでは、A[0] が除外されるため、sumleft の最大値は計算されません。Nadesri はこの問題を指摘していますが、コードのエラーを明示的に指摘していただけると助かると思いました。これがc99で書かれた私のソリューションです。 https://codility.com/demo/results/demoQ5UWYG-5KG/

Answer 10

これは 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

Answer 11

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;

    }