21 Pertanyaan: Pelatihan Codility-Equilibrium Tape [ditutup]

pertanyaan dibuat di Wed, Dec 23, 2015 12:00 AM

Saya menerima tes kodilitas pada suatu hari untuk suatu pekerjaan, karena itu saya telah berlatih menggunakan beberapa masalah dari halaman pelatihan mereka Tautan

Sayangnya, saya hanya bisa mendapatkan 83/100 pada pertanyaan Tape-Equilibrium:

  

Array tanpa indeks kosong nol yang terdiri dari N bilangan bulat diberikan. Array A mewakili angka pada kaset.
     Setiap bilangan bulat P, sedemikian sehingga 0 < P < N, bagi rekaman ini menjadi dua bagian yang tidak kosong: A [0], A [1], ..., A [P - 1] dan A [P], A [P + 1], ..., A [N - 1 ].
  Perbedaan antara dua bagian adalah nilai: | (A [0] + A [1] + ... + A [P - 1]) - (A [P] + A [P + 1] + ... + A [N - 1]) |
  Dengan kata lain, itu adalah perbedaan absolut antara jumlah bagian pertama dan jumlah bagian kedua.

     

Tulis fungsi yang, dengan array nol yang diindeks nol-kosong dari integer N, mengembalikan perbedaan minimal yang dapat dicapai.

     

Contoh: A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3
  Kami dapat membagi rekaman ini di empat tempat:
P = 1, perbedaan = | 3 - 10 | = 7
P = 2, perbedaan = | 4 - 9 | = 5
P = 3, perbedaan = | 6 - 7 | = 1
P = 4, perbedaan = | 10 - 3 | = 7
  Dalam hal ini saya akan mengembalikan 1 karena ini adalah perbedaan terkecil.

     

N adalah int, kisaran [2..100.000];   setiap elemen A adalah int, kisaran [−1,000..1,000]. Itu perlu O (n) kompleksitas waktu,

Kode saya adalah sebagai berikut:

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

Saya jadi sedikit marah dengan Math.ab. Dua area pengujian yang gagal adalah "ganda" (yang menurut saya adalah dua nilai, -1000 dan 1000, dan "kecil". http://codility.com/demo/results/demo9DAQ4T-2HS/

Bantuan apa pun akan dihargai, saya ingin memastikan saya tidak membuat kesalahan mendasar.

    
21
  1. Di loop kedua untuk Anda, Anda harus loop sampai A.length-1. Setelah itu akan menjadi 100% karena Anda akan menghindari substraksi yang tidak perlu.
    2015-12-02 15: 28: 51Z
  2. Saya pergi untuk memeriksa tes, dan saya tidak mengerti deskripsi mereka. Terima kasih untuk menyebutkan In other words, it is the absolute difference between the sum of the first part and the sum of the second part., itu membuat saya senang ..
    2016-06-18 08: 40: 29Z
21 Jawaban                              21                         

Solusi Anda sudah O (N). Anda harus menghapus perut dari sumleft dan sumright.

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

Juga sebelum loop kedua,

 
ans =Math.abs( sumleft - sumright );

Seharusnya berhasil.

    
11
2013-10-18 17: 25: 15Z
  1. Bagaimana ini bisa O (N)? Itu berulang melalui array dua kali bukan O (2N)
    2014-09-29 15: 45: 10Z
  2. @ JimCollins Dalam urutan kompleksitas, faktor konstan tidak memiliki arti. O (N) = O (2N).
    2014-09-29 16: 00: 47Z
  3. @ JimCollins: kode tidak mengulang loop array dua kali. Kode berisi dua loop dan masing-masing tidak memiliki loop dalam.
    2015-06-10 06: 41: 15Z
  4. Kondisi di loop kedua harus kurang dari 1. Ini karena jumlah yang benar tidak akan mungkin jika array dipartisi di akhir.
    2016-07-01 21: 19: 35Z
  5. perbedaan akan selalu terus berkurang sampai kami mencapai minimum. Begitu kita mencapai titik ini, itu hanya bisa naik. Jadi bagaimana jika kita putus dari loop pada saat ini? Tidakkah itu menghemat sekitar setengah dari iterasi?
    2018-01-23 11: 14: 58Z

100% , dalam 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;
    
10
2017-10-24 09: 06: 22Z
  1. Ini akan gagal dalam kasus tepi jika perbedaan minimum jika lebih besar dari 9999 :). Saya sarankan menggunakan INFINITY atau (1 << 31) - 1 atau Number.MAX_INT untuk keamanan.
    2015-12-29 15: 28: 01Z
  2. Terima kasih, telah memodifikasinya dengan saran Anda.
    2017-10-24 09: 06: 56Z

Pertimbangkan solusi 100/100 ini di Ruby:

 
# 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
    
3
2014-01-24 13: 41: 14Z

Beberapa C # untukmu.

 
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;
    }
}
    
3
2014-02-07 20: 21: 46Z
  1. Kondisi di loop kedua harus kurang dari 1. Ini karena jumlah yang benar tidak akan mungkin jika array dipartisi di akhir.
    2016-07-01 21: 20: 18Z

Saya juga mengalami masalah mendapatkan 83% seperti CTB, tetapi untuk solusi C ++ saya.

Untuk kode saya, jumlah rekaman saya sedang mengevaluasi SETELAH memperbarui hak cipta dan leftsum, tetapi di situlah masalahnya. Dalam hal ini, loop kedua harus mengevaluasi hingga P = A.size () - 1. Jika tidak, Anda akan mengevaluasi pasangan tape di mana semuanya ditambahkan ke leftsum, dan tidak ada yang ditambahkan ke rightsum (yang tidak diizinkan sesuai dengan deskripsi masalah).

Salah satu aspek yang mungkin bagus tentang solusi saya di bawah (sekarang ditetapkan untuk mendapatkan 100%) adalah bahwa ia melakukan satu evaluasi jumlah yang kurang, dibandingkan dengan beberapa solusi di atas.

 
#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;
}
    
2
2014-03-03 06: 14: 08Z

Ini adalah solusi saya (Java) yang baru saja saya tulis untuk itu, sangat sederhana untuk dipahami dan O (n) dan melakukan skor 100% pada kodilitas:

 
 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;
}
    
2
2014-09-13 19: 34: 39Z
  1. dapatkah Anda menghubungi saya apa yang salah dengan solusi saya codility.com/demo/results/demo5VVCPJ-BXB
    2015-08-07 17: 09: 17Z

Algoritma serupa dari CTB yang diposting di atas: Kode ini mendapatkan skor 100% di JAVA;

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

}

    
1
2013-12-26 17: 40: 56Z

ini adalah kode skor 100 saya di Python mungkin akan membantu Anda. Anda harus melihat apakah statment mencegahnya dari "kesalahan ganda" jika Anda memiliki N = 2 A = [- 1,1] ketika Anda membuat jumlah. Anda mendapatkan 0 tetapi harus mengembalikan | -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]
1
2014-01-04 01: 58: 28Z

Kode C # 100/100 saya:

 
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;
    }
}
    
1
2014-05-13 21: 21: 49Z

Skor 100% dalam Program C: 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; 
}
    
1
2014-08-08 03: 23: 27Z
  1. Jawaban yang bagus menyertai contoh kode dengan penjelasan untuk pembaca masa depan. Sementara orang yang mengajukan pertanyaan ini dapat memahami jawaban Anda, menjelaskan bagaimana Anda sampai di sana akan membantu orang lain yang tak terhitung jumlahnya.
    2014-08-07 19: 13: 52Z

Saya melakukan tugas yang sama, tetapi tidak bisa mendapatkan lebih dari 50 poin. Algoritma saya terlalu lambat. Jadi, saya mencari petunjuk dan menemukan solusi Anda. Saya telah menggunakan ide untuk menjumlahkan elemen-elemen dalam array hanya sekali dan mendapat 100/100. Solusi saya adalah dalam JavaScript, tetapi dapat dengan mudah diubah menjadi Java. Anda dapat pergi ke solusi saya dengan menggunakan tautan di bawah ini.

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

Silakan lihat kode saya dan beri tahu saya jika Anda memiliki beberapa pertanyaan. Saya akan dengan senang hati membantu Anda.

 
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;

}

    
0
2013-10-29 19: 56: 48Z

Ini 100 skor dalam ruby ​​

 
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
    
0
2014-01-25 07: 17: 42Z
  1. ar.sort akan menghasilkan waktu O (N * log (N)), bukan?
    2014-01-24 13: 45: 39Z
  2. Anda benar, saya melewatkannya, ar.min menyelesaikan masalah, terima kasih
    2014-01-25 07: 16: 44Z

ini yang saya lakukan !!! //tulis kode Anda dalam C # dengan .NET 2.0

 
   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;
   }
  }
    
0
2014-04-14 04: 10: 16Z

Saya menemukan solusi sempurna untuk TapeEquilibrium oleh Cheng on Codesays . Saya menerjemahkannya ke Jawa untuk siapa saja yang ingin tahu tentang itu. Solusi Cheng mengenai 100% pada Codility

 
    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;
}
    
0
2014-06-03 23: 54: 28Z

Ini adalah solusi mudah di 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;
}
    
0
2014-06-06 12: 42: 59Z

Skor 100% dalam Program C: Kodilitas

 
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));
}
    
0
2014-07-26 03: 30: 09Z
  1. 2014-07-26 04: 19: 03Z

Skor 100%: Equilibrium Tape: 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;
}
    
0
2014-07-26 04: 13: 32Z
  1. 2014-07-26 04: 14: 00Z
 
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
    
0
2014-09-10 06: 50: 04Z
 
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;

    }
    
0
2014-09-27 22: 33: 41Z
  1. gandakan dua elemen 0,064 s SALAH JAWABAN mendapatkan 0 tes 2000 simple_positive diharapkan sederhana dengan angka positif, panjang = 5 0,064 s OK simple_negative tes sederhana dengan angka negatif, panjang = 5 0,064 s SALAH JAWABAN mendapat -27 yang diharapkan 3 small_random acak kecil, panjang = 100 0,072 s
    2014-12-05 18: 45: 43Z
  2. Saya pikir maksud Anda panjang dan bukan Panjang
    2017-07-20 21: 38: 25Z

Titik awal dan akhir indeks tidak benar - maka tes 'ganda' gagal, karena tes ini hanya memiliki titik awal dan titik akhir. Tes lain dapat lulus jika set angka yang digunakan tidak mengandung ketergantungan pada titik akhir.

Misalkan N = A.length Sumright adalah jumlah dari kanan. Nilai maksimum ini harus mengecualikan A [N] tetapi termasuk A [0]. sumleft - jumlah dari kiri. Nilai maksimum ini harus mencakup A [0] tetapi tidak termasuk A [N]. Jadi max sumright salah dihitung di loop pertama. Demikian pula pada loop kedua, nilai maks sumleft tidak dihitung karena A [0] dikecualikan. Nadesri menunjukkan masalah ini, tetapi saya pikir akan bermanfaat jika saya secara eksplisit menunjukkan kesalahan dalam kode Anda, karena itulah yang awalnya Anda tanyakan. Inilah solusi saya yang ditulis dalam c99. https://codility.com/demo/results/demoQ5UWYG-5KG/

    
0
2014-10-31 11: 56: 26Z

Ini adalah solusi Python 100/100 saya:

 
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
    
0
2014-11-08 22: 55: 02Z
sumber ditempatkan sini