Repitiendo la pregunta aquí, debido al espacio limitado para explicar la pregunta.
Dada una matriz de números y una constante k, minimice el tamaño de la matriz con las siguientes reglas para eliminar elementos.
Se pueden eliminar exactamente tres elementos de una vez.
- ¿Qué preguntas le hicieron en la entrevista de programación para Google, Amazon, Facebook o Microsoft?
- ¿Cuál es el algoritmo más eficiente y fácil (en términos de implementación) para la coincidencia de patrones en una cadena?
- ¿Cómo abordaría este problema de visualización de 7 segmentos en la ronda A de la prueba Google APAC 2015?
- ¿Cuál según usted debería ser una buena manera de contratar programadores?
- Dada una matriz indexada a cero 'A' = {1, 2, 3, ..., n} de 'n' enteros, ¿cómo podemos reorganizar los números en ella de modo que para dos números cualquiera a [i] y a [ j] (i <j), su promedio no se encuentra entre i y j?
Los tres elementos eliminados deben estar adyacentes en la matriz, es decir, arr [i], arr [i + 1], arr [i + 2]. Y el segundo elemento debe ser k mayor que el primero y el tercer elemento debe ser k mayor que el segundo, es decir, arr [i + 1] – arr [i] = k y arr [i + 2] -arr [i + 1] = k.
Mi solución:
———————————
1. Detecte un caso en el que tengamos un conflicto de qué lado fusionar, por ejemplo:
(2 3 4 5 6), puede fusionar 2 3 4, de modo que solo quede 5 6 al final O
Combina 4 5 6, de modo que solo quede 2 3 al final.
Entonces este es un caso de conflicto. Y para todos los casos de conflicto hacemos lo siguiente.
Sea X la pieza central del subconjunto de 5 que forma parte del conflicto, por lo que 4 en el ejemplo anterior:
si A [x] = A [x + 3], fusionar en el lado derecho, por ejemplo:
si tenemos una matriz original como (2 3 4 5 6 4), entonces combinar 4 5 6 primero dará un mejor resultado y luego combinar 2 3 4, ya que una vez que se elimina 4 5 6, la matriz se convierte en 2 3 4, que puede ser completamente eliminado
si A [x] = A [x-3], fusionar en el lado izquierdo. La misma lógica que la anterior, justo a la izquierda.
y si A [X] = A [X + 3] = A [x-3], podemos combinar y eliminar en cualquier lado.
——————————————-
En general, todos están resolviendo esto usando DP, ¿realmente necesitamos DP aquí? ¿Mi enfoque fallará en cualquier caso?
Esta pregunta es de CodeJam, enlace a continuación.
Panel de control – Prueba APAC de ronda B – Google Code Jam