Сложность: medium
Мы строим таблицу из 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
👨💻 Алгоритм:
1⃣Создайте метод depthFirstSearch, который принимает n количество строк в текущем дереве, k позицию целевого узла в последней строке и rootVal значение корня текущего дерева в качестве параметров. Если n равно 1, то в нашем дереве будет единственный узел, и этот узел является целевым узлом. Поэтому возвращаем его значение rootVal.
2⃣Найдите количество узлов в последней строке текущего дерева, totalNodes, которое равно 2^(n-1). Если текущий целевой узел k находится в левой половине последней строки текущего поддерева (то есть k <= totalNodes / 2), переходим в левое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 0, иначе следующее значение узла будет 1. Возвращаем вызов depthFirstSearch(n - 1, k, nextRootVal).
3⃣В противном случае, если текущий целевой узел k находится в правой половине последней строки текущего поддерева (то есть k > totalNodes / 2), переходим в правое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 1, иначе следующее значение узла будет 0. Кроме того, позиция целевого узла изменится на (k - (totalNodes / 2)). Возвращаем вызов depthFirstSearch(n - 1, newPosition, nextRootVal).
😎 Решение:
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)
Ставь 👍 и забирай 📚 Базу знаний