(Связанные списки и деревья)
Очень важно познакомиться с различными структурами данных и с тем, как их правильно применять. В этой статье представлены наиболее часто задаваемые вопросы на собеседовании и популярные проблемы с массивами, двумерными массивами, очередями, стеками, деревьями двоичного поиска, графами и т.д. знание Javascript. Примеры этих проблем я получил в учебных пособиях по Python, но я хотел решить их с помощью JavaScript, потому что JS является одним из самых популярных языков программирования и необходим любому веб-разработчику.
Ссылки на другие задачи: Часть I, Часть II
# 9 N-й элемент связанного списка
Учитывая связанный список и положительное число n, напишите функцию, которая возвращает значение в n-м узле от конца связанного списка.
Например, если ввод находится под списком и n = 1, то вывод - «E»; n = 4, выход «B»; n = 7, вывод равен нулю.
Примеры:
Input : Linked list: 1->2->3->4->5->6->7, n = 3 Output : 5 Input : Linked list: 11->23->35->41->5->656->17->0, n = 8 Output : 11
Как мы видим на визуализации связанного списка выше, узел со значением «A» указывает на узел со значением «B» и так далее. Последний узел со значением «E» в этом связанном списке указывает на нуль. Чтобы получить ссылку на этот список, мы можем присвоить переменную с именем «head» первому элементу в связанном списке. Каждый элемент или каждый узел в этом связанном списке является объектом, и класс может выглядеть следующим образом:
class Node {
constructor(value) {
this.value = value;
this.child;
}
};
class LinkedList {
constructor(){
this.head;
}
};
Вот эта проблема, давайте инициализируем две переменные, левый указатель и правый указатель, указывающие на первый узел. Затем переместите правый указатель к правому узлу n раз. После этого переместите оба указателя вправо один за другим, пока правый указатель не укажет на нуль. Когда правый указатель будет указывать на нуль, левый указатель будет указывать на узел, который мы ищем. Если n больше, чем длина связанного списка, тогда мы должны вернуть null.
Решение:
function nthFromLast(head, n) {
let left = head,
right = head;
for (let i = 0; i < n; i++) {
if (!right) return null;
right = right.child;
}
while (right) {
right = right.child;
left = left.child;
}
return left;
}
# 10 Это двоичное дерево поиска?
Учитывая двоичное дерево, определите, является ли оно допустимым двоичным деревом поиска (BST).
Примеры:
Input :
5 = root
/ \
2 7
/\ /\
0 3 8 10
Output : true
Input :
5 = root
/ \
2 7
/\ /\
0 3 4 10
Output : false
(4 in the right subtree is less than 5 in the root)
Дерево - это абстрактная модель иерархической структуры, состоящая из узлов с родительско-дочерними отношениями.
Узел в двоичном дереве имеет не более двух дочерних элементов: один левый и один правый. Это определение позволяет нам писать более эффективные алгоритмы для вставки, поиска и удаления узлов в / из дерева. Двоичные деревья широко используются в информатике.
Двоичное дерево поиска - это двоичное дерево, но оно позволяет хранить только узлы с меньшими значениями в левой части и узлы с большими значениями в правой части.
class Node {
constructor(value){
this.value = value;
this.left;
this.right;
}
};
class BinarySearchTree{
constructor(){
this.root;
}
};
Простое решение для каждого узла: проверить, меньше ли его левый узел, чем узел, а правый узел больше, чем узел, но как мы можем увидеть во втором примере, это не сработает. Нам нужно создать две новые переменные, которые будут отслеживать текущее наибольшее и текущее наименьшее значение для текущего узла, который мы проверяем. Мы начинаем с корня, и наши переменные будут upperLimit = null, lowerLimit = null, но когда мы спустимся, например, к правой стороне узла, мы узнаем, что это значение, новый верхний предел, должно быть как минимум больше или равно значению корня, новый нижний предел. И когда мы переходим к левому узлу, мы знаем, что это значение должно быть между нижним и верхним пределом, чтобы быть двоичным деревом поиска. После того, как мы проверим эти условия, мы должны рекурсивно проверить, являются ли левое поддерево и правое поддерево двоичным деревом поиска с новыми ограничениями, которые мы собираемся дать им. Если они есть, верните true из нашей функции.
Решение:
function isBST(node, upperLimit = null, lowerLimit = null) {
if (lowerLimit && node.value < lowerLimit) return false;
if (upperLimit && node.value > upperLimit) return false;
let isLeftBST = true,
isRigthBst = true;
if (node.left) isLeftBST = isBST(node.left, node.value, lowerLimit);
if (isLeftBST && node.right)
isRigthBst = isBST(node.right, upperLimit, node.value);
return isLeftBST && isRigthBst;
}
# 11 Самый низкий общий предок
Для двоичного дерева найдите наименьшего общего предка (LCA) двух заданных значений в дереве. Предположим, что в дереве нет дубликатов.
Пример:
BT:
5 = root
/ \
11 7
/\ /\
0 3 8 10
/ \
1 4
Input : root
n1 = 3
n2 = 4
Output : 11
Input : root
n1 = 11
n2 = 5
Output : 5
Input : root
n1 = 10
n2 = 10
Output : 10
Это очень популярная проблема, и есть много потенциальных решений для нее. Наше решение для собеседования должно быть простым и эффективным. Как мы знаем из предыдущей проблемы, двоичное дерево имеет структуру родитель-потомок с двумя дочерними элементами.
class Node {
constructor(value){
this.value = value;
this.left;
this.right;
}
};
class BinaryTree{
constructor(){
this.root;
}
};
Чтобы решить эту проблему, сначала мы должны найти узлы, которые соответствуют заданным целым числам в дереве, прежде чем найти их наименьшего общего предка. И чтобы найти каждый узел, потребуется O (n) по временной сложности, потому что наше дерево не обязательно отсортировано, а сложность дополнительного пространства или вспомогательного пространства будет O (log n), n - количество узлов в этом дереве.
Мы разделим нашу проблему на две части. Сначала найдите путь между корневым узлом или любым другим узлом, если на то пошло, и целым числом, которое мы ищем. Этот путь будет стеком узлов от узла с заданным значением до корневого узла. Получив эти два пути, мы можем исследовать, какие элементы являются общими для этих двух путей, считая сверху. Последний элемент в общих элементах в этих двух путях будет наименьшим общим предком между заданными целыми числами.
Теперь давайте подумаем, как реализовать путь к нашему узлу. Наша функция примет два аргумента: root и x - один из заданных элементов. Мы пытаемся найти путь к x от корня узла. Мы собираемся сделать это рекурсивно. Базовый случай - когда мы идем к конечному узлу, несуществующему узлу, мы возвращаем undefined. И еще один базовый случай: если корень равен элементу, который мы пытаемся найти, мы возвращаем новый стек с одним значением - массив с текущим узлом. Затем нам нужно спросить, какой путь к левому узлу и к правому узлу, и перейти к поддеревьям. Если x не находится в поддереве, мы ничего не возвращаем. В противном случае, если x в поддереве, добавьте текущий корень к проходу и верните этот путь как новый проход. Если x не в левом поддереве, не в правом поддереве, мы возвращаем undefined.
Используя эту функцию pathToX, мы можем реализовать нашу основную функцию lca, которая принимает три аргумента: корневой узел дерева, которое мы исследуем, и x1, x2 два целых числа, которые мы хотим найти наименьшего общего предка для. Мы собираемся найти путь к x1 и x2 с помощью нашей функции pathToX. Если в этом дереве нет вхождений x1 или x2, мы вернем ноль. После этого мы собираемся найти LCA, инициализируя переменную result. Мы собираемся перебирать наш путь, сохраненный в виде стека, один за другим сверху и назначать текущий равный элемент результату, пока не найдем другой элемент. Последним элементом, присвоенным нашей переменной result, является LCA.
Решение:
function pathToX(root, x) {
if (!root) return;
if (root.value === x) return [root];
let leftPath = pathToX(root.left, x);
if (leftPath) {
leftPath.push(root);
return leftPath;
}
let rightPath = pathToX(root.right, x);
if (rightPath) {
rightPath.push(root);
return rightPath;
}
return;
}
function lca(root, x1, x2) {
pathTo1 = pathToX(root, x1);
pathTo2 = pathToX(root, x2);
if (!pathTo1 || !pathTo2) return null;
let result;
while (pathTo1.length > 0 && pathTo2.length > 0) {
pop1 = pathTo1.pop();
pop2 = pathTo2.pop();
if (pop1 === pop2) result = pop1;
else break;
}
return result;
}
