Сложность: 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 {
public:
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);
}
}
int kthGrammar(int n, int k) {
return depthFirstSearch(n, k, 0);
}
};Ставь 👍 и забирай 📚 Базу знаний