test exercises codility java algorithm puzzle

java - test - codility exercises



Entrenamiento de Codility Equilibrium Codility (21)

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.


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


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

}


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


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


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


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


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


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


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


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;

}


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]


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/


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


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.


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


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


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


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;


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


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


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