Error de java.lang.OutOfMemoryError: Espacio de la pila de Java insuficiente durante la resolución de la pregunta de LeetCode.
Estaba resolviendo la pregunta de leetcode anterior, aquí está mi solución que funciona perfectamente, excepto para el caso de prueba donde n = 30, k = 434991989
, en el cual muestra el error de memoria Java heap space.
public class kthGrammer{
public static void rowGenerator(int n, int[] row, int num){
if(n == num)
return;
int start = (row.length / 2) - (int)Math.pow(2, num - 1);
int pStart = (row.length / 2) - (int)Math.round(Math.pow(2, num - 3));
while(pStart <= (row.length / 2) + (int)Math.pow(2, num - 3)){
if(row[pStart] == 0){
row[start++] = 0;
row[start++] = 1;
}
else{
row[start++] = 1;
row[start++] = 0;
}
++pStart;
}
rowGenerator(n, row, num + 1);
return;
}
public static int kthGrammar(int n, int k) {
int[] row = new int[(int)Math.pow(2,n - 1)];
row[row.length / 2] = 0;
rowGenerator(n, row, 1);
return row[k - 1];
}
public static void main(String[] args) {
System.out.println("\nRespuesta: " + kthGrammar(30, 434991989));
// System.out.println("\nRespuesta: " + kthGrammar(2, 1));
// System.out.println("\nRespuesta: " + kthGrammar(2, 2));
// System.out.println("\nRespuesta: " + kthGrammar(3, 1));
}
}
davy.ai
Explicación de la Solución
La solución utiliza la recursión para generar la secuencia de caracteres k-ésima. Se define una función
rowGenerator
que recibe como entrada n (número de filas), row (fila actual) y num (número de fila actual). Luego, la función calcula el índice de inicio y el índice de inicio del padre para los elementos de la fila utilizando la fórmulastart = (row.length / 2) - (int)Math.pow(2, num - 1)
ypStart = (row.length / 2) - (int)Math.round(Math.pow(2, num - 3))
. Luego, genera los siguientes elementos de la fila en base a los elementos de la fila anterior utilizando la regla de gramática k-ésima dada y los almacena en el arreglo de filas. Esta función se llama a sí misma de forma recursiva hasta generar n filas.La función
kthGrammar
recibe como entrada n y k, y crea un arreglo de enteros de tamaño 2^n-1 para almacenar la fila k-ésima. Luego llama a la funciónrowGenerator
pasando n, el arreglo de fila creado y 1 como entrada.El programa luego llama a la función
kthGrammar
conn = 30
yk = 434991989
e imprime el resultado.Problema
El problema ocurre para el caso de prueba donde
n = 30
yk = 434991989
ya que el tamaño del arreglo de filas se vuelve muy grande (es decir, 2^29 – 1 = 536870911 elementos). Esto requiere mucha memoria, lo cual resulta en eljava.lang.OutOfMemoryError
en Java.Solución
Una solución para abordar este problema es utilizar un enfoque recursivo para generar solo los elementos de la fila necesarios para el valor de k dado. En lugar de crear y almacenar todas las filas en el arreglo de filas, podemos generar los elementos de fila requeridos calculando de forma recursiva la fila padre para el elemento k-ésimo dado.
Se puede utilizar una estructura de árbol binario para representar los elementos de la fila, siendo la raíz el primer elemento, y los hijos izquierdo y derecho representando los elementos de la siguiente fila. Para un k dado, si el valor del elemento padre es
1
, el valor del elemento k-ésimo es0
, y viceversa.Podemos determinar el elemento padre de k utilizando la fórmula:
padre(k) = (k+1)/2
Luego podemos calcular el valor de k de la siguiente manera:
– Si el valor de padre(k) es
1
, entonces el valor del elemento k-ésimo es0
si k es par, y1
si k es impar.– Si el valor de padre(k) es
0
, entonces el valor del elemento k-ésimo es1
si k es par, y0
si k es impar.Aquí está la solución actualizada:
Conclusión
En conclusión, la solución actualizada utiliza un enfoque recursivo para generar solo los elementos de fila necesarios para el valor de k dado, lo cual resuelve el problema de que el programa se quede sin memoria. Esta solución también tiene una complejidad temporal de O(n), que es mucho mejor que la complejidad temporal de la solución anterior que era de O(2^n).