En este post te voy a explicar como resolví el problema: LeetCode: Range Sum Query 2D de la plataforma LeetCode.
Primeros pasos.
El problema Range Sum Query 2D te pide calcular la suma de una zona determinada de una matriz. Para esto te dan los valores de la esquina superior izquierda y de la esquina inferior derecha de un cuadrilátero. Debes usar todos los elementos que se encuentren en el área para calcular la suma.
Este ejercicio se puede solucionar por fuerza bruta por un doble for. El proposito del ejercicio es que encuentres una forma óptima para resolverlo.
¿Cómo soluciono el ejercicio?.
En mi caso, decidí emplear un enfoque de preprocesamiento lineal. En la siguiente matriz.
- [1, 2, 3, 4 ]
- [0, 1, 10, 1]
- [1,19, 8, 1 ]
- [1, 4, 5, 9 ]
Supón que te recibes col1=1, row1:=1, col2=2 row2=3. El valor cuadrilátero a calcular es:
- [_, _, _, _]
- [_, 1, 10, _]
- [_,19, 8, _]
- [_, 4, 5, _ ]
Los valores son estáticos, las posiciones de los números no van a cambiar. Puedes hacer un pre procesado de las sumas.
- [1, 3, 6, 10]
- [0, 1, 11, 12] → 11 – 0 = 11. Lo mismo que: 10 + 1
- [1,20, 28, 29] → 28 – 1 = 27. Lo mismo que: 19 + 8;
- [1, 5, 10, 19]. → 10 – 1 = 9. Lo mismo que: 5 + 4.
Si, en este ejemplo la ganancia de rendimiento es poca. La complejidad en tiempo se vera reducida a medida que aumenta el tamaño de la matriz. El número de iteraciones necesarias siempre va a ser igual al largo del cuadrilátero. En cambio, en un enfoque de fuerza bruta el tiempo va a ser cuadrático.
Solución.
- NVL in SQL Server - 2023-11-01
- ¿Que es Cake Build? - 2023-02-22
- #How to fix error: MSB4019: The imported project «Microsoft.Data.Tools.Schema.SqlTasks.targets» was not found - 2023-02-20
