java - test - codility exercises

Entrenamiento de Codility Equilibrium Codility

Question

Recibí una prueba de codilidad el otro día para un trabajo, como tal, he estado practicando usando algunos de los problemas de su página de capacitación Link

Desafortunadamente, solo he podido obtener 83/100 en la pregunta de Tape-Equilibrium:

Se proporciona una matriz A no indexada a cero no A que consta de N enteros. La matriz A representa números en una cinta.
Cualquier número entero P, tal que 0 <P <N, divide esta cinta en dos partes no vacías: A [0], A [1],…, A [P - 1] y A [P], A [P + 1],…, A [N - 1].
La diferencia entre las dos partes es el valor de: | (A [0] + A [1] +… + A [P - 1]) - (A [P] + A [P + 1] +… + A [ N - 1]) |
En otras palabras, es la diferencia absoluta entre la suma de la primera parte y la suma de la segunda parte.

Escriba una función que, dada una matriz A no indexada a cero no vacía de N enteros, devuelva la diferencia mínima que se puede lograr.

Ejemplo: A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3
Podemos dividir esta cinta en cuatro lugares:
P = 1 , diferencia = | 3 - 10 | = 7
P = 2 , diferencia = | 4 - 9 | = 5
P = 3 , diferencia = | 6 - 7 | = 1
P = 4 , diferencia = | 10 - 3 | = 7
En este caso devolvería 1 ya que es la diferencia más pequeña.

N es un int, rango [2..100,000]; cada elemento de A es un int, rango [−1,000..1,000]. Tiene que ser O (n) la complejidad del tiempo,

Mi código es el siguiente:

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

Me enojé un poco con Math.abs. Las dos áreas de prueba en las que falla son "dobles" (que creo que son dos valores, -1000 y 1000, y "pequeñas". http://codility.com/demo/results/demo9DAQ4T-2HS/

Cualquier ayuda sería apreciada, quiero asegurarme de que no estoy cometiendo ningún error básico.

Answer 1

¡¡¡Esto es lo que hice!!! // escribe tu código en C # con .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;
}
}

Answer 2

Algoritmo similar de CTB publicado anteriormente: este código obtiene el 100% en 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;
} 

}

Answer 3

Algunos C # para ti.

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 4

Aquí está mi solución (Java) que acabo de escribir, muy simple de entender y es O (n) y tiene una puntuación del 100% en la codilidad:

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

Answer 5

Aquí está mi solución 100/100 de 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 6

Aquí hay una solución fácil en 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 7

Considera esta solución 100/100 en 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

Answer 8

Encontré la solución perfecta para TapeEquilibrium de Cheng en Codesays . Lo traduje a Java para cualquiera que tenga curiosidad por él. La solución de Cheng alcanzó el 100% en 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;
}

Answer 9

Esta es la puntuación de 100 en rubí.

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 10

Estaba haciendo la misma tarea, pero no pude obtener más de 50 puntos. Mi algoritmo era demasiado lento. Entonces, busqué una pista y encontré tu solución. He usado la idea de sumar los elementos de la matriz solo una vez y obtuve 100/100. Mi solución está en JavaScript, pero se puede transformar fácilmente en Java. Puedes ir a mi solución usando el enlace de abajo.

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

Por favor, eche un vistazo a mi código y hágame saber si tiene alguna pregunta. Me encantaría ayudarte.

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 11

Este es mi código de puntuación de 100 en Python tal vez te ayude. Debes echarle un vistazo a si la leyenda evita que se produzca un "doble error" si tienes N = 2 A = [- 1,1] cuando haces una suma. Obtienes 0 pero debería devolver | -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]

Answer 12

Los puntos de inicio y final de los índices no son correctos, por lo tanto, la prueba de "dobles" falla, ya que esta prueba solo tiene un punto de inicio y final. Pueden pasar otras pruebas si el conjunto de números utilizados no contiene una dependencia de los puntos finales.

Sea N = A.length El derecho de suma es la suma de la derecha. El valor máximo de esto debe excluir A [N] pero incluir A [0]. sumleft - sumas de la izquierda. El valor máximo de esto debe incluir A [0] pero excluir A [N]. Por lo tanto, la suma máxima se calcula incorrectamente en el primer bucle. De forma similar, en el segundo bucle, el valor máximo de sumleft no se calcula, ya que se excluye A [0]. Nadesri señala este problema, pero pensé que sería útil si señalaba explícitamente los errores en su código, ya que eso era lo que originalmente pidió. Aquí está mi solución escrita en c99. https://codility.com/demo/results/demoQ5UWYG-5KG/

Answer 13

Mi código 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 14

Su solución ya es O (N). Es necesario eliminar los abdominales de sumleft y sumright.

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

También antes del segundo bucle,

ans =Math.abs( sumleft - sumright );

Deberia de funcionar.

Answer 15

También estaba teniendo problemas para obtener el 83% como CTB, pero para mi solución C ++.

Para mi código, mi suma de cinta estaba evaluando DESPUÉS de actualizar rightsum y leftsum, pero ahí radica el problema. En este caso, el segundo bucle debe evaluar hasta P = A. tamaño () - 1. De lo contrario, terminará evaluando un par de cintas donde todo se agrega a leftsum, y no se agrega nada a rightsum (que no está permitido de acuerdo con la descripción del problema).

Un aspecto posiblemente bueno de mi solución a continuación (ahora corregido para obtener el 100%) es que hace una evaluación menos de la suma, en comparación con un par de soluciones anteriores.

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

Answer 16

100% en el programa de 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;
}

Answer 17

100% en el programa de 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));
}

Answer 18

100% , en 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 19

Puntuación del 100%: Equilibrio de la cinta: Codilidad: 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;
}

Answer 20

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

Answer 21

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