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