Сложность: 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 {
private function depthFirstSearch(int $n, int $k, int $rootVal): int {
if ($n === 1) return $rootVal;
$totalNodes = 1 << ($n - 1);
if ($k > $totalNodes / 2) {
$nextRootVal = $rootVal === 0 ? 1 : 0;
return $this->depthFirstSearch($n - 1, $k - $totalNodes / 2, $nextRootVal);
} else {
$nextRootVal = $rootVal === 0 ? 0 : 1;
return $this->depthFirstSearch($n - 1, $k, $nextRootVal);
}
}
public function kthGrammar(int $n, int $k): int {
return $this->depthFirstSearch($n, $k, 0);
}
}Ставь 👍 и забирай 📚 Базу знаний