Тренировка ленточной равновесии

Я получил тест на кодовость на днях для работы, поэтому я практиковал использование некоторых проблем со своей обучающей страницы Ссылка

К сожалению, мне удалось получить 83/100 на вопрос "Равноправие на ленте":

Дается непустой нуль-индексированный массив A, состоящий из N целых чисел. Массив 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]) | Другими словами, это абсолютная разница между суммой первой части и суммой второй части.

Напишите функцию, которая при задании непустого нулевого индекса A из N целых чисел возвращает минимальную разницу, которая может быть достигнута.

Пример: 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.00.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 и "small". http://codility.com/demo/results/demo9DAQ4T-2HS/

Любая помощь будет оценена, я хочу убедиться, что я не делаю никаких основных ошибок.

Ответы

Ответ 1

Ваше решение уже O (N). Вам нужно удалить абс из sumleft и sumright.

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

Также перед вторым циклом,

ans =Math.abs( sumleft - sumright );

Он должен работать.

Ответ 2

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;

Ответ 3

Рассмотрим это решение 100/100 в 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

Ответ 4

Некоторые С# для ya.

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

Ответ 5

Я также сталкивался с проблемами, получающими 83%, как CTB, но для моего решения на С++.

Для моего кода моя ленточная сумма оценивала ПОСЛЕ обновления прав и левого пространства, но в этом и заключается проблема. В этом случае второй цикл должен оцениваться до 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;
}

Ответ 6

Аналогичный алгоритм CTB, опубликованный выше: Этот код получает 100% баллов в 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; 
}

}

Ответ 7

Мой код С# 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;
    }
}

Ответ 8

Вот мое решение (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;
}

Ответ 9

Я выполнял ту же задачу, но не смог получить более 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;

}

Ответ 10

это мой 100 баллов в Python, возможно, поможет вам. Вы должны взглянуть на то, если statment предотвратит "двойную ошибку", если у вас есть 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]

Ответ 11

Это 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

Ответ 12

вот что я сделал!!! // пишем ваш код в С# с .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;
   }
  }

Ответ 13

Я нашел идеальное решение для TapeEquilibrium от Cheng on Codesays. Я перевел его на Java для всех, кому это интересно. Решение Cheng выбрало 100% на 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;
}

Ответ 14

Вот простое решение в С++ (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;
}

Ответ 15

100% Оценка в программе C: 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));
}

Ответ 16

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

Ответ 17

100% Оценка в программе 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; 
}

Ответ 18

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

Ответ 19

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;

    }

Ответ 20

Начальная и конечная точки индексов неверны - следовательно, тест "удваивает" терпит неудачу, так как этот тест имеет только начальную и конечную точку. Другие тесты могут проходить, если набор используемых номеров не содержит зависимости от конечных точек.

Пусть N = A. длина Справедливость - суммы справа. Максимальное значение этого параметра должно исключать A [N], но включать A [0]. sumleft - суммы слева. Максимальное значение этого параметра должно включать A [0], но исключить A [N]. Таким образом, max sumright неправильно вычисляется в первом цикле. Аналогично во втором цикле максимальное значение sumleft не вычисляется, поскольку A [0] исключается. Надесри указывает на эту проблему, но я подумал, что было бы полезно, если бы я прямо указал на ошибки в вашем коде, поскольку это было то, что вы изначально задали. Вот мое решение, написанное на c99. https://codility.com/demo/results/demoQ5UWYG-5KG/

Ответ 21

Вот мое решение 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