779. K-th Symbol in Grammar

leetcode medium

#csharp#leetcode#medium#search#string#tree

Task

Мы строим таблицу из n строк (индексация начинается с 1). Начинаем с написания 0 в первой строке. Теперь в каждой следующей строке мы смотрим на предыдущую строку и заменяем каждое появление 0 на 01, и каждое появление 1 на 10.

Например, для n = 3, первая строка будет 0, вторая строка будет 01, и третья строка будет 0110.

Даны два целых числа n и k, вернуть k-й (индексация начинается с 1) символ в n-й строке таблицы из n строк.

Пример:

Input: n = 1, k = 1

Output: 0

Explanation: row 1: 0

C# solution

matched/original

public class Solution {
    private int DepthFirstSearch(int n, int k, int rootVal) {
        if (n == 1) return rootVal;
        int totalNodes = 1 << (n - 1);
        if (k > totalNodes / 2) {
            int nextRootVal = rootVal == 0 ? 1 : 0;
            return DepthFirstSearch(n - 1, k - totalNodes / 2, nextRootVal);
        } else {
            int nextRootVal = rootVal == 0 ? 0 : 1;
            return DepthFirstSearch(n - 1, k, nextRootVal);
        }
    }
    public int KthGrammar(int n, int k) {
        return DepthFirstSearch(n, k, 0);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private int DepthFirstSearch(int n, int k, int rootVal) {
        if (n == 1) return rootVal;
        int totalNodes = 1 << (n - 1);
        if (k > totalNodes / 2) {
            int nextRootVal = rootVal == 0 ? 1 : 0;
            return DepthFirstSearch(n - 1, k - totalNodes / 2, nextRootVal);
        } else {
            int nextRootVal = rootVal == 0 ? 0 : 1;
            return DepthFirstSearch(n - 1, k, nextRootVal);
        }
    }
    public int KthGrammar(int n, int k) {
        return DepthFirstSearch(n, k, 0);
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    private int DepthFirstSearch(int n, int k, int rootVal) {
        if (n == 1) return rootVal;
        int totalNodes = 1 << (n - 1);
        if (k > totalNodes / 2) {
            int nextRootVal = rootVal == 0 ? 1 : 0;
            return DepthFirstSearch(n - 1, k - totalNodes / 2, nextRootVal);
        } else {
            int nextRootVal = rootVal == 0 ? 0 : 1;
            return DepthFirstSearch(n - 1, k, nextRootVal);
        }
    }
    public int KthGrammar(int n, int k) {
        return DepthFirstSearch(n, k, 0);
    }
}

JavaScript solution

matched/original

class Solution {
    depthFirstSearch(n, k, rootVal) {
        if (n === 1) return rootVal;
        const totalNodes = 1 << (n - 1);
        if (k > totalNodes / 2) {
            const nextRootVal = rootVal === 0 ? 1 : 0;
            return this.depthFirstSearch(n - 1, k - totalNodes / 2, nextRootVal);
        } else {
            const nextRootVal = rootVal === 0 ? 0 : 1;
            return this.depthFirstSearch(n - 1, k, nextRootVal);
        }
    }

    kthGrammar(n, k) {
        return this.depthFirstSearch(n, k, 0);
    }
}

Python solution

matched/original

class Solution:
    def depthFirstSearch(self, n: int, k: int, rootVal: int) -> int:
        if n == 1:
            return rootVal
        totalNodes = 2 ** (n - 1)
        if k > totalNodes / 2:
            nextRootVal = 1 if rootVal == 0 else 0
            return self.depthFirstSearch(n - 1, k - (totalNodes / 2), nextRootVal)
        else:
            nextRootVal = 0 if rootVal == 0 else 1
            return self.depthFirstSearch(n - 1, k, nextRootVal)

    def kthGrammar(self, n: int, k: int) -> int:
        return self.depthFirstSearch(n, k, 0)

Go solution

matched/original

package main

type Solution struct{}

func (s Solution) depthFirstSearch(n, k, rootVal int) int {
    if n == 1 {
        return rootVal
    }
    totalNodes := 1 << (n - 1)
    if k > totalNodes/2 {
        nextRootVal := 1
        if rootVal == 1 {
            nextRootVal = 0
        }
        return s.depthFirstSearch(n-1, k-totalNodes/2, nextRootVal)
    } else {
        nextRootVal := 0
        if rootVal == 1 {
            nextRootVal = 1
        }
        return s.depthFirstSearch(n-1, k, nextRootVal)
    }
}

func (s Solution) kthGrammar(n, k int) int {
    return s.depthFirstSearch(n, k, 0)
}

Explanation

Algorithm

Создайте метод depthFirstSearch, который принимает n количество строк в текущем дереве, k позицию целевого узла в последней строке и rootVal значение корня текущего дерева в качестве параметров. Если n равно 1, то в нашем дереве будет единственный узел, и этот узел является целевым узлом. Поэтому возвращаем его значение rootVal.

Найдите количество узлов в последней строке текущего дерева, totalNodes, которое равно 2^(n-1). Если текущий целевой узел k находится в левой половине последней строки текущего поддерева (то есть k <= totalNodes / 2), переходим в левое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 0, иначе следующее значение узла будет 1. Возвращаем вызов depthFirstSearch(n - 1, k, nextRootVal).

В противном случае, если текущий целевой узел k находится в правой половине последней строки текущего поддерева (то есть k > totalNodes / 2), переходим в правое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 1, иначе следующее значение узла будет 0. Кроме того, позиция целевого узла изменится на (k - (totalNodes / 2)). Возвращаем вызов depthFirstSearch(n - 1, newPosition, nextRootVal).

😎