Блог

https://leetcode.com/problems/k-th-symbol-in-grammar/

Я решал приведенный выше вопрос с кодом файла, вот мое решение, оно работает отлично, за исключением тестового примера, n = 30, k = 434991989 в котором он показывает java.lang.OutOfMemoryError: пространство кучи Java

 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("nAnswer: "   kthGrammar(30, 434991989));
        // System.out.println("nAnswer: "   kthGrammar(2, 1));
        // System.out.println("nAnswer: "   kthGrammar(2, 2));
        // System.out.println("nAnswer: "   kthGrammar(3, 1));
    }
}
 

Такие ресурсы, как LeetCode, разрабатывают свои вопросы таким образом, что решение редко может быть достигнуто с помощью прямого подхода (из-за ограничений памяти или процессора), поэтому для получения оптимального решения необходимо провести некоторые алгоритмические исследования. В вашем коде вы генерируете весь набор строк, который довольно большой — 30-я строка содержит 2 ^ 30 элементов, 29-я строка содержит 2 ^ 29 элементов и так далее. Более того, если N будет, например, 1000, то вся структура не поместится в память всего компьютерного кластера. Вот почему вы получаете OutOfMemoryError

Я могу просто дать вам подсказку: идея этого алгоритма заключается в том, что каждая строка в два раза больше предыдущей. Таким образом, K-й элемент в R-й строке является «родительским» для 2 элементов в следующей строке (R 1-й), и эти элементы имеют индексы 2K-1 и 2K. Это формирует шаблон, поэтому вы можете выполнять итерации в обратном направлении от N-й строки, каждый раз деля текущее K на 2, пока не дойдете до 1-й строки, и выполняя некоторые проверки.