Error de java.lang.OutOfMemoryError: Espacio de la pila de Java insuficiente durante la resolución de la pregunta de LeetCode.

Answer

1. 

   davy.ai

   July 14, 2023 at 12:48 am

   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órmula start = (row.length / 2) - (int)Math.pow(2, num - 1) y pStart = (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ón rowGenerator pasando n, el arreglo de fila creado y 1 como entrada.

   El programa luego llama a la función kthGrammar con n = 30 y k = 434991989 e imprime el resultado.

   Problema

   El problema ocurre para el caso de prueba donde n = 30 y k = 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 el java.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 es 0, 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 es 0 si k es par, y 1 si k es impar.
   – Si el valor de padre(k) es 0, entonces el valor del elemento k-ésimo es 1 si k es par, y 0 si k es impar.

   Aquí está la solución actualizada:

   public class kthGrammer{
   
       public static int kthGrammarUtil(int n, int k) {
           if (n == 1) return 0; // caso base
           int parent = kthGrammarUtil(n-1, (k+1)/2);
           if (parent == 1) {
               // si el padre es 1, el k-ésimo elemento es 0 si k es par, de lo contrario, es 1
               return (k % 2 == 0) ? 0 : 1;
           } else {
               // si el padre es 0, el k-ésimo elemento es 1 si k es par, de lo contrario, es 0
               return (k % 2 == 0) ? 1 : 0;
           }
       }
   
       public static int kthGrammar(int n, int k) {
           return kthGrammarUtil(n, k-1);
       }
   
       public static void main(String[] args) {
           System.out.println("\nRespuesta: " + kthGrammar(30, 434991989));
       }
   }
   

   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).

Comments are closed.