Удаление элемента из односвязного списка, как и добавление, может происходить в разных позициях: в начале, в середине или в конце списка. Рассмотрим несколько сценариев.
Удаление первого элемента списка
1. Если список пуст, то ничего не делаем.
2. Если список не пуст, сохраняем указатель на первый элемент списка.
3. Обновляем указатель головы списка (
Удаление элемента из середины списка
1. Находим узел, который предшествует удаляемому узлу, проходя по списку, начиная с головы (
2. Изменяем ссылку в предшествующем узле на следующий узел удаляемого узла (то есть пропускаем узел, который хотим удалить).
3. Освобождаем память для удаляемого узла.
Удаление последнего элемента списка
1. Если список пуст, ничего не делаем.
2. Если в списке один элемент (то есть это и есть голова), то просто удаляем этот элемент, присвоив указателю головы
3. Если элементов больше одного, проходим по списку, находя предпоследний элемент.
4. Устанавливаем в поле next предпоследнего элемента значение
Удаление первого элемента списка
1. Если список пуст, то ничего не делаем.
2. Если список не пуст, сохраняем указатель на первый элемент списка.
3. Обновляем указатель головы списка (
head) на следующий элемент, который находится после текущего первого узла.Удаление элемента из середины списка
1. Находим узел, который предшествует удаляемому узлу, проходя по списку, начиная с головы (
head). Это нужно для того, чтобы изменить ссылку на следующий элемент.2. Изменяем ссылку в предшествующем узле на следующий узел удаляемого узла (то есть пропускаем узел, который хотим удалить).
3. Освобождаем память для удаляемого узла.
Удаление последнего элемента списка
1. Если список пуст, ничего не делаем.
2. Если в списке один элемент (то есть это и есть голова), то просто удаляем этот элемент, присвоив указателю головы
null/nil.3. Если элементов больше одного, проходим по списку, находя предпоследний элемент.
4. Устанавливаем в поле next предпоследнего элемента значение
null/nil, таким образом удаляя ссылку на последний элемент.👍3🔥2❤1
Проектирование связанного списка
Привет, друзья. Теперь мы с вами закрепим теорию, которую узучили ранее и реализуем связанный список с нуля.
Сложность: 🟡 Средняя
ℹ️ Описание
Разработайте свою реализацию связанного списка. Вы можете использовать одно- или двусвязный список.
Узел в односвязном списке должен иметь два атрибута: val и next.
val — значение текущего узла
next — указатель/ссылка на следующий узел
Если вы хотите использовать двусвязный список, вам понадобится еще один атрибут prev, чтобы указать на предыдущий узел в связанном списке.
Учтите, что отсчет порядка узлов в связанном списке начинается с нуля.
Реализуйте класс MyLinkedList:
—
—
—
—
—
—
⚠️ Ограничения
— Значения каждого элемента списка находятся в диапазоне от 0 до 1000
— В списке может быть от 0 до 1000 элементов
1️⃣ Пример
✅ Реализация односвязного списка
Сегодня мы рассмотрим реализацию односвязного списка, так как она проще, а уже в следующем посте реализуем двусвязный.
Для начала опишем простой класс MyLinkedList с инициализирующим конструктором и создадим пустые методы-заглушки.
Здесь мы сразу описали тип
Во-первых, в классе мы завели переменную head, которая по умолчанию равна null. Это и есть ссылка на голову списка, то есть на его первый элемент.
Во-вторых, нельзя просто так получить размер связанного списка, так как для подсчета количества нод нужно обойти весь список от его головы до хвоста. Чтобы упростить нам жизнь и дальнейшие вычисления мы завели внутреннюю переменную size в классе, которая инициализируется нулем при создании класса и показывает размер списка. При выполнении операций добавления переменная будет увеличиваться на 1, а при удалении - уменьшаться на 1.
Привет, друзья. Теперь мы с вами закрепим теорию, которую узучили ранее и реализуем связанный список с нуля.
Сложность: 🟡 Средняя
ℹ️ Описание
Разработайте свою реализацию связанного списка. Вы можете использовать одно- или двусвязный список.
Узел в односвязном списке должен иметь два атрибута: val и next.
val — значение текущего узла
next — указатель/ссылка на следующий узел
Если вы хотите использовать двусвязный список, вам понадобится еще один атрибут prev, чтобы указать на предыдущий узел в связанном списке.
Учтите, что отсчет порядка узлов в связанном списке начинается с нуля.
Реализуйте класс MyLinkedList:
—
MyLinkedList() инициализирует объект MyLinkedList.—
int get(int index) метод позволяет получить значение узла в списке по его индексу. Если индекс неверный, метод должен возвращать -1.—
void addAtHead(int val) метод позволяет добавлять узел со значением val в начало списка.—
void addAtTail(int val) метод позволяет добавлять узел со значением val в конец списка.—
void addAtIndex(int index, int val) метод позволяет добавлять узел со значением val на место элемента с индексом index. Если индекс равен длине связанного списка, узел будет добавлен в его конец. Если индекс больше длины списка, то его добавлять не нужно.—
void deleteAtIndex(int index) метод позволяет удалить элемент под индексом index из списка.⚠️ Ограничения
— Значения каждого элемента списка находятся в диапазоне от 0 до 1000
— В списке может быть от 0 до 1000 элементов
1️⃣ Пример
// псевдокод
myLinkedList = MyLinkedList();
myLinkedList.addAtHead(1); // [1]
myLinkedList.addAtTail(3); // [1, 3]
myLinkedList.addAtIndex(1, 2); // [1, 2, 3]
myLinkedList.get(1); // 2
myLinkedList.deleteAtIndex(1); // [1, 3]
myLinkedList.get(1); // 3
✅ Реализация односвязного списка
Сегодня мы рассмотрим реализацию односвязного списка, так как она проще, а уже в следующем посте реализуем двусвязный.
Для начала опишем простой класс MyLinkedList с инициализирующим конструктором и создадим пустые методы-заглушки.
type MyLinkedListNode = {
val: number;
next: MyLinkedListNode | null;
}
export class MyLinkedList {
head: MyLinkedListNode | null;
size: number;
constructor() {
this.head = null;
this.size = 0;
}
get(index: number): number {
return 0
}
addAtIndex(index: number, val: number): void {}
addAtHead(val: number): void {}
addAtTail(val: number): void {}
deleteAtIndex(index: number): void {}
}
Здесь мы сразу описали тип
MyLinkedListNode для одной ноды списка и сам класс.Во-первых, в классе мы завели переменную head, которая по умолчанию равна null. Это и есть ссылка на голову списка, то есть на его первый элемент.
Во-вторых, нельзя просто так получить размер связанного списка, так как для подсчета количества нод нужно обойти весь список от его головы до хвоста. Чтобы упростить нам жизнь и дальнейшие вычисления мы завели внутреннюю переменную size в классе, которая инициализируется нулем при создании класса и показывает размер списка. При выполнении операций добавления переменная будет увеличиваться на 1, а при удалении - уменьшаться на 1.
algorithmics-blog.github.io
Проектирование связанного списка
Подробный разбор решения задачи с примерами на языках TypeScript и GO
👍2🔥1
🔸Получение элемента из списка
Метод предназначен для получения значения узла по указанному индексу.
В первую очередь нужно проверить корректность индекса. Если он меньше 0 или больше или равен размеру списка size, возвращается -1, так как такой индекс недопустим.
Далее необходимо пройти по списку от его головы и найти элемент с нужным индексом. Для этого мы запускаем цикл, который выполняется до тех пор, пока i < index. Инициализируем переменную curr, которая изначально равна head то есть ссылке на первый элемент списка. Далее на каждой итерации цикла в переменную curr записывается ссылка на следующий элемент в списке через curr.next.
Если удалось найти нужный элемент в списке, то возвращаем его значение в качестве ответа, иначе возвращаем -1.
🔸Добавление элемента в список по индексу
В первую очередь нужно проверить корректность индекса. Если он меньше 0 или больше или равен размеру списка size, то выходим из функции и не выполняем вставку.
Следующим шагом увеличиваем внутреннюю переменную size на единицу, так происходит добавление элемента.
Если индекс равен 0, то происходит вставка в начало списка. Это означает, что нам достаточно создать новый элемент, указать в его next ссылку на текущий head списка и заменить текущий head новым элементом, после чего выйти из функции.
Если же индекс не равен 0, то нам нужно добавить элемент перед тем, который находится на позиции равной index. Мы выделили отдельный внутренний метод findPrevNode. Вызвав этот метод мы получаем предшествующий переданному индексу узел prev. Если такой узел существует, то нам достаточно в next нового элемента добавить ссылку из prev.next, а в prev.next положить ссылку на новый элемент. Таким образом новый элемент встраивается в цепочку узлов списка на заданную позицию.
🔸Добавление элемента в начало списка
Так как у нас уже есть универсальный метод для вставки элементов по индексу, мы можем им воспользоваться для вставки в начало. Для этого просто вызовем метод с нулевым индексом
🔸Добавление элемента в конец списка
Так как у нас уже есть универсальный метод для вставки элементов по индексу, мы можем им воспользоваться для вставки в конец. Для этого просто вызовем метод с индексом равным длине списка
🔸Удаление элемента
В первую очередь нужно проверить корректность индекса. Если индекс меньше 0 или больше или равен размеру списка, метод завершает работу, так как такой индекс некорректен.
Далее необходимо уменьшить значение переменной size на единицу, так как происходит удаление.
Если индекс равен нулю, значит происходит удаление первого элемента. В этом случае достаточно изменить head списка на head.next.
Если же индекс не равен нулю, то нужно сначала найти элемент, который находится перед удаляемым. Затем нужно проставить ссылку с предыдущего на следующий элемент prev.next = prev.next.next.
Посмотреть реализацию в блоге
#linked_list #medium
Метод предназначен для получения значения узла по указанному индексу.
В первую очередь нужно проверить корректность индекса. Если он меньше 0 или больше или равен размеру списка size, возвращается -1, так как такой индекс недопустим.
Далее необходимо пройти по списку от его головы и найти элемент с нужным индексом. Для этого мы запускаем цикл, который выполняется до тех пор, пока i < index. Инициализируем переменную curr, которая изначально равна head то есть ссылке на первый элемент списка. Далее на каждой итерации цикла в переменную curr записывается ссылка на следующий элемент в списке через curr.next.
Если удалось найти нужный элемент в списке, то возвращаем его значение в качестве ответа, иначе возвращаем -1.
🔸Добавление элемента в список по индексу
В первую очередь нужно проверить корректность индекса. Если он меньше 0 или больше или равен размеру списка size, то выходим из функции и не выполняем вставку.
Следующим шагом увеличиваем внутреннюю переменную size на единицу, так происходит добавление элемента.
Если индекс равен 0, то происходит вставка в начало списка. Это означает, что нам достаточно создать новый элемент, указать в его next ссылку на текущий head списка и заменить текущий head новым элементом, после чего выйти из функции.
Если же индекс не равен 0, то нам нужно добавить элемент перед тем, который находится на позиции равной index. Мы выделили отдельный внутренний метод findPrevNode. Вызвав этот метод мы получаем предшествующий переданному индексу узел prev. Если такой узел существует, то нам достаточно в next нового элемента добавить ссылку из prev.next, а в prev.next положить ссылку на новый элемент. Таким образом новый элемент встраивается в цепочку узлов списка на заданную позицию.
🔸Добавление элемента в начало списка
Так как у нас уже есть универсальный метод для вставки элементов по индексу, мы можем им воспользоваться для вставки в начало. Для этого просто вызовем метод с нулевым индексом
this.addAtIndex(0, val)🔸Добавление элемента в конец списка
Так как у нас уже есть универсальный метод для вставки элементов по индексу, мы можем им воспользоваться для вставки в конец. Для этого просто вызовем метод с индексом равным длине списка
this.addAtIndex(this.size, val)🔸Удаление элемента
В первую очередь нужно проверить корректность индекса. Если индекс меньше 0 или больше или равен размеру списка, метод завершает работу, так как такой индекс некорректен.
Далее необходимо уменьшить значение переменной size на единицу, так как происходит удаление.
Если индекс равен нулю, значит происходит удаление первого элемента. В этом случае достаточно изменить head списка на head.next.
Если же индекс не равен нулю, то нужно сначала найти элемент, который находится перед удаляемым. Затем нужно проставить ссылку с предыдущего на следующий элемент prev.next = prev.next.next.
Посмотреть реализацию в блоге
#linked_list #medium
algorithmics-blog.github.io
Проектирование связанного списка
Подробный разбор решения задачи с примерами на языках TypeScript и GO
👍2🔥1
Максимальная сумма парных элементов связного списка
Продолжаем изучение связанных списков и сегодня у нас новая задача.
Сложность: 🟡 Средняя
ℹ️ Описание
Реализуйте функцию, которая будет искать максимальную сумму парных элементов связного списка.
Парный элемент для i'го считается элемент с индексом n - i - 1, где 0 <= i <= n / 2 - 1. То есть, для первого элемента списка парным будет считаться последний элемент списка, для второго - предпоследний и так далее.
⚠️ Ограничения
— Список всегда имеет четное количество элементов
— Количество элементов лежит в диапазоне от 2 до 100 000
— Значение элемента лежит в диапазоне от 1 до 100 000
1️⃣ Пример
Элементы списка: [5,4,2,1]
Ответ: 6
Пояснение: В списке есть 2 пары элементов: [5, 1] и [4, 2]. Сумма обоих пар равна 6.
2️⃣ Пример
Входные данные: [4,2,2,3]
Ответ: 7
Пояснение: В списке есть 2 пары элементов: [4, 3] и [2, 2]. Максимальная сумма равна 7.
3️⃣ Пример
Входные данные: [1,100000]
Ответ: 100001
✅ Реализация
У любой задачи всегда есть множество решений и эта — не исключение. Мы смогли придумать несколько и рассмотрим их по порядку.
Основная сложность этой задачи заключается в использовании связного списка в качестве структуры данных: мы не знаем длину списка и не можем быстро обращаться к элементам по индексу, из-за чего не получается быстро находить парный элемент для текущего узла.
Первая идея, которая приходит в голову — отказаться от использования связного списка в пользу массива. Это сделать несложно: достаточно один раз пройти по всему списку и перенести все элементы в массив. Теперь, имея на руках слайс, мы можем легко находить парные элементы, и задача сводится к простому поиску максимума среди сумм парных элементов.
➡️ Решение через преобразование в массив
Решение можно улучшить, сэкономив память: нам необязательно превращать весь список в массив. Достаточно переложить первую половину списка в стек, а затем пройти по второй половине, доставая для каждого следующего элемента его пару из стека.
Однако возникает другая проблема: как я уже упоминал, основное ограничение — это незнание длины списка, а значит, мы не можем сразу определить, где находится его середина. Это ограничение можно обойти с помощью небольшой хитрости, используя два указателя:
— currentListElement — будем перемещать по списку последовательно.
— oddElementList — будем двигать через два элемента за раз. В связном списке это делается следующим образом:
Таким образом, когда указатель oddElementList достигнет конца списка, указатель currentListElement будет указывать на начало второй половины нашего списка.
После этого останется только пройтись до конца списка указателем currentListElement, доставая для каждого следующего элемента его пару из стека и находя максимальную сумму.
➡️ Решение через стек
Итак, оптимальное решение
Вероятнее всего, в задаче не подразумевалось использование других структур данных (хотя, в явном виде такого ограничения нет). Поэтому мы можем попробовать решить задачу только с использованием связных списков.
Чтобы быстро находить пары, можно создать вспомогательный список, развернутый в обратном порядке. Для изменения порядка списка можно написать простую функцию reverseList (изменение происходит in-place без создания нового списка).
Как и в случае со стеком, можно развернуть не весь список, а только одну его половину. Итоговое решение будет очень похоже на решение со стеком, только вместо стека мы будем использовать первую половину списка, развернутую в обратном порядке.
Данное решение будет более оптимальным по памяти, так как изменение порядка происходит in-place и не требует дополнительного пространства под массив или стек.
➡️ Оптимальное решение
#medium #linked_list
Продолжаем изучение связанных списков и сегодня у нас новая задача.
Сложность: 🟡 Средняя
ℹ️ Описание
Реализуйте функцию, которая будет искать максимальную сумму парных элементов связного списка.
Парный элемент для i'го считается элемент с индексом n - i - 1, где 0 <= i <= n / 2 - 1. То есть, для первого элемента списка парным будет считаться последний элемент списка, для второго - предпоследний и так далее.
⚠️ Ограничения
— Список всегда имеет четное количество элементов
— Количество элементов лежит в диапазоне от 2 до 100 000
— Значение элемента лежит в диапазоне от 1 до 100 000
1️⃣ Пример
Элементы списка: [5,4,2,1]
Ответ: 6
Пояснение: В списке есть 2 пары элементов: [5, 1] и [4, 2]. Сумма обоих пар равна 6.
2️⃣ Пример
Входные данные: [4,2,2,3]
Ответ: 7
Пояснение: В списке есть 2 пары элементов: [4, 3] и [2, 2]. Максимальная сумма равна 7.
3️⃣ Пример
Входные данные: [1,100000]
Ответ: 100001
✅ Реализация
У любой задачи всегда есть множество решений и эта — не исключение. Мы смогли придумать несколько и рассмотрим их по порядку.
Основная сложность этой задачи заключается в использовании связного списка в качестве структуры данных: мы не знаем длину списка и не можем быстро обращаться к элементам по индексу, из-за чего не получается быстро находить парный элемент для текущего узла.
Первая идея, которая приходит в голову — отказаться от использования связного списка в пользу массива. Это сделать несложно: достаточно один раз пройти по всему списку и перенести все элементы в массив. Теперь, имея на руках слайс, мы можем легко находить парные элементы, и задача сводится к простому поиску максимума среди сумм парных элементов.
Решение можно улучшить, сэкономив память: нам необязательно превращать весь список в массив. Достаточно переложить первую половину списка в стек, а затем пройти по второй половине, доставая для каждого следующего элемента его пару из стека.
Однако возникает другая проблема: как я уже упоминал, основное ограничение — это незнание длины списка, а значит, мы не можем сразу определить, где находится его середина. Это ограничение можно обойти с помощью небольшой хитрости, используя два указателя:
— currentListElement — будем перемещать по списку последовательно.
— oddElementList — будем двигать через два элемента за раз. В связном списке это делается следующим образом:
oddElementList = oddElementList.Next.Next
Таким образом, когда указатель oddElementList достигнет конца списка, указатель currentListElement будет указывать на начало второй половины нашего списка.
После этого останется только пройтись до конца списка указателем currentListElement, доставая для каждого следующего элемента его пару из стека и находя максимальную сумму.
Итак, оптимальное решение
Вероятнее всего, в задаче не подразумевалось использование других структур данных (хотя, в явном виде такого ограничения нет). Поэтому мы можем попробовать решить задачу только с использованием связных списков.
Чтобы быстро находить пары, можно создать вспомогательный список, развернутый в обратном порядке. Для изменения порядка списка можно написать простую функцию reverseList (изменение происходит in-place без создания нового списка).
Как и в случае со стеком, можно развернуть не весь список, а только одну его половину. Итоговое решение будет очень похоже на решение со стеком, только вместо стека мы будем использовать первую половину списка, развернутую в обратном порядке.
Данное решение будет более оптимальным по памяти, так как изменение порядка происходит in-place и не требует дополнительного пространства под массив или стек.
#medium #linked_list
Please open Telegram to view this post
VIEW IN TELEGRAM
algorithmics-blog.github.io
Максимальная сумма парных элементов связного списка
Подробный разбор решения задачи с примерами на языках TypeScript и GO
1👍3❤2👌1👀1
Префиксное дерево (Trie)
Префиксное дерево, или Trie (произносится как «три») — это структура данных, которая позволяет эффективно хранить и искать строки по их префиксам. В отличие от других деревьев, в Trie каждый узел может содержать символ строки, а путь от корневого узла до любого узла представляет собой префикс какого-либо слова, хранимого в дереве. Важно помнить, что конечное слово в данной структуре не обязательно будет оканчиваться листовой нодой, так как слово целиком может являться префиксом другого слова, Поэтому, помимо прочего, ноды должны содержать признак того, являются ли они окончанием какого-либо из слов.
Вот пример структуры узла Trie.
Каждый узел имеет мапу children, где ключом является символ, а значением — следующий узел, представляющий символ в этом слове. Узел isEndOfWord помечает конец слова.
Простыми словами, если мы хотим добавить слова «cat» в дерево, нам нужно разбить его посимвольно и каждый символ будет представлять собой отдельную ноду. Иерархия нод будет выстроена в соответствии с порядком слов, то есть в нашем примере: «c» -> «a» -> «t».
Вот так можно визуализировать префиксное дерево, в котором содержаться слова cat, car, cart, care, dog, dot, и dove:
### Пример работы с Trie
Допустим, мы хотим сохранить слова «cat» и «car». Префиксное дерево будет выглядеть следующим образом:
1. Корневой узел содержит ссылки на узлы c, которые ведут к поддереву для символа a.
2. Узел a ветвится на узлы t и r, представляющие слова «cat» и «car».
3. В узлах t и r флаг isEndOfWord установлен в true, указывая, что здесь заканчиваются слова.
### Основные операции в Trie
1. Добавление слова — добавление слова в Trie выполняется за O(N), где N — длина слова. Мы последовательно проходим каждый символ слова и либо создаем новый узел, если он не существует, либо переходим к существующему.
2. Поиск слова — поиск также выполняется за O(N). Для поиска слова достаточно пройти по каждому символу слова. Если на каком-то этапе путь отсутствует, значит, слово не найдено.
3. Поиск по префиксу — уникальная особенность Trie. Чтобы найти все слова, начинающиеся с заданного префикса, можно просто дойти до конца префикса, а затем собрать все слова, начиная с этого узла.
### Преимущества и недостатки Trie
1. Trie отлично подходит для поиска по префиксам и проверки принадлежности слова к множеству. Это особенно полезно в задачах автодополнения и саджестов. Более того, я сталкивался с этой структурой в реальных сервисах - именно для реализации быстрого саджеста.
2. Относительно экономное потребление памяти для хранения словарей — общие префексы не дублируются, в отличии от варианта, если бы мы хранили тот же словарь в виде обычного массива. В реальных словарях количество слов ограничено и многие слова имеют общие префиксы.
3. Недостатком является узкая специализация данной структуры. Данная структура позволяет искать только по точному совпадению префикса. То есть, например, если вам нужно искать слово не по префиксу, а по любой возможной подстроке, или учесть опечатки — классический Trie становится бесполезным. Не смотря на то, что некоторые модификации данной структуры могут решить часть проблем, не факт что данная структура будет оптимальным выбором для решения подобных задач.
#trie
Префиксное дерево, или Trie (произносится как «три») — это структура данных, которая позволяет эффективно хранить и искать строки по их префиксам. В отличие от других деревьев, в Trie каждый узел может содержать символ строки, а путь от корневого узла до любого узла представляет собой префикс какого-либо слова, хранимого в дереве. Важно помнить, что конечное слово в данной структуре не обязательно будет оканчиваться листовой нодой, так как слово целиком может являться префиксом другого слова, Поэтому, помимо прочего, ноды должны содержать признак того, являются ли они окончанием какого-либо из слов.
Вот пример структуры узла Trie.
type TrieNode = {
children: { [key: string]: TrieNode };
isEndOfWord: boolean;
}
type TrieNode struct {
Children map[rune]*TrieNode
IsEndOfWord bool
}
Каждый узел имеет мапу children, где ключом является символ, а значением — следующий узел, представляющий символ в этом слове. Узел isEndOfWord помечает конец слова.
Простыми словами, если мы хотим добавить слова «cat» в дерево, нам нужно разбить его посимвольно и каждый символ будет представлять собой отдельную ноду. Иерархия нод будет выстроена в соответствии с порядком слов, то есть в нашем примере: «c» -> «a» -> «t».
Вот так можно визуализировать префиксное дерево, в котором содержаться слова cat, car, cart, care, dog, dot, и dove:
(root)
/ \
c d
/ |
a o
/ \ / | \
t* r* g* t* v
/ \ |
e* t* e*
### Пример работы с Trie
Допустим, мы хотим сохранить слова «cat» и «car». Префиксное дерево будет выглядеть следующим образом:
1. Корневой узел содержит ссылки на узлы c, которые ведут к поддереву для символа a.
2. Узел a ветвится на узлы t и r, представляющие слова «cat» и «car».
3. В узлах t и r флаг isEndOfWord установлен в true, указывая, что здесь заканчиваются слова.
### Основные операции в Trie
1. Добавление слова — добавление слова в Trie выполняется за O(N), где N — длина слова. Мы последовательно проходим каждый символ слова и либо создаем новый узел, если он не существует, либо переходим к существующему.
2. Поиск слова — поиск также выполняется за O(N). Для поиска слова достаточно пройти по каждому символу слова. Если на каком-то этапе путь отсутствует, значит, слово не найдено.
3. Поиск по префиксу — уникальная особенность Trie. Чтобы найти все слова, начинающиеся с заданного префикса, можно просто дойти до конца префикса, а затем собрать все слова, начиная с этого узла.
### Преимущества и недостатки Trie
1. Trie отлично подходит для поиска по префиксам и проверки принадлежности слова к множеству. Это особенно полезно в задачах автодополнения и саджестов. Более того, я сталкивался с этой структурой в реальных сервисах - именно для реализации быстрого саджеста.
2. Относительно экономное потребление памяти для хранения словарей — общие префексы не дублируются, в отличии от варианта, если бы мы хранили тот же словарь в виде обычного массива. В реальных словарях количество слов ограничено и многие слова имеют общие префиксы.
3. Недостатком является узкая специализация данной структуры. Данная структура позволяет искать только по точному совпадению префикса. То есть, например, если вам нужно искать слово не по префиксу, а по любой возможной подстроке, или учесть опечатки — классический Trie становится бесполезным. Не смотря на то, что некоторые модификации данной структуры могут решить часть проблем, не факт что данная структура будет оптимальным выбором для решения подобных задач.
#trie
1🔥7❤2👍1🎄1
Система поиска подсказок
Ранее мы уже разбирали задачу, в которой нужно было реализовать структуру данных trie. В этом посте я решил рассмотреть более прикладную задачу, связанную с использованием этой структуры.
Классические задачи для префиксного дерева включают поиск по префиксу: например, нахождение конкретного слова или подготовка автодополнений (саджестов) по заданным префиксам.
На первый взгляд, текущая задача кажется типичной: требуется найти саджесты по префиксу. К сожалению, в этот раз я прогадал: в задаче нужно взять массив продуктов и единожды найти множество саджестов по префиксу. Если переформулировать, пишущая нагрузка (любое преобразование входящего массива) либо сопоставима, либо выше читающей. В реальных приложениях такое редко встречается — чаще доминирует чтение.
Таким образом, хотя использование префиксного дерева могло бы быть разумным выбором в реальных условиях, для оптимального решения данной задачи на литкоде эта структура данных оказалась не самой удачной.
Сложность: 🟡 Средняя
ℹ️ Описание
Дан массив строк products, представляющий доступные названия продуктов, и строка searchWord, представляющая искомое слово, вводимое пользователем.
Реализуйте функцию, которая возвращает массив массивов, где:
— Каждый подмассив содержит список подсказок для соответствующего префикса строки searchWord. Первый подмассив соответствует префиксу из первого символа строки searchWord, второй — префиксу из первых двух символов, и так далее.
— Каждый подмассив включает до трех продуктов из products, отсортированных в лексикографическом порядке.
— Если для какого-либо префикса не найдено совпадений, соответствующий подмассив должен быть пустым.
⚠️ Ограничения
— 1 <= products.length <= 1000 — количество продуктов.
— 1 <= products[i].length <= 3000 — длина каждой строки продукта.
— 1 <= searchWord.length <= 1000 — длина строки поиска.
— Все строки состоят только из строчных латинских букв.
1️⃣ Пример
Продукты: products = ["mobile","mouse","moneypot","monitor","mousepad"]
Искомое слово: searchWord = "mouse"
Ответ:
2️⃣ Пример
Продукты: products = ["havana"]
Искомое слово: searchWord = "havana"
Ответ:
✅ Реализация
Как я писал в начале, первое что приходит в голову для решения этой задачи — преобразовать исходный массив в дерево и обходить его в глубину.
➡️ Решение через преобразование в префиксное дерево
Задача разделяется на 2 подзадачи:
— Имплементировать структуру данных Trie и преобразовать входящий массив
— Имплементировать метод Closest, который по префиксу вернет массив подсказок.
Помимо этого есть несколько решений по оптимизации: например, можно обходить дерево с самого большого возможного префикса. Тогда можно реализовать "всплытие" подсказок и избежать лишних обходов в глубину. Или же можно пожертвовать памятью и для каждого узла дерева сохранять набор подсказок в момент добавления нового слов.
➡️ Решение через бинарный поиск
Ранее мы уже разбирали задачу, в которой нужно было реализовать структуру данных trie. В этом посте я решил рассмотреть более прикладную задачу, связанную с использованием этой структуры.
Классические задачи для префиксного дерева включают поиск по префиксу: например, нахождение конкретного слова или подготовка автодополнений (саджестов) по заданным префиксам.
На первый взгляд, текущая задача кажется типичной: требуется найти саджесты по префиксу. К сожалению, в этот раз я прогадал: в задаче нужно взять массив продуктов и единожды найти множество саджестов по префиксу. Если переформулировать, пишущая нагрузка (любое преобразование входящего массива) либо сопоставима, либо выше читающей. В реальных приложениях такое редко встречается — чаще доминирует чтение.
Таким образом, хотя использование префиксного дерева могло бы быть разумным выбором в реальных условиях, для оптимального решения данной задачи на литкоде эта структура данных оказалась не самой удачной.
Сложность: 🟡 Средняя
ℹ️ Описание
Дан массив строк products, представляющий доступные названия продуктов, и строка searchWord, представляющая искомое слово, вводимое пользователем.
Реализуйте функцию, которая возвращает массив массивов, где:
— Каждый подмассив содержит список подсказок для соответствующего префикса строки searchWord. Первый подмассив соответствует префиксу из первого символа строки searchWord, второй — префиксу из первых двух символов, и так далее.
— Каждый подмассив включает до трех продуктов из products, отсортированных в лексикографическом порядке.
— Если для какого-либо префикса не найдено совпадений, соответствующий подмассив должен быть пустым.
⚠️ Ограничения
— 1 <= products.length <= 1000 — количество продуктов.
— 1 <= products[i].length <= 3000 — длина каждой строки продукта.
— 1 <= searchWord.length <= 1000 — длина строки поиска.
— Все строки состоят только из строчных латинских букв.
1️⃣ Пример
Продукты: products = ["mobile","mouse","moneypot","monitor","mousepad"]
Искомое слово: searchWord = "mouse"
Ответ:
[
["mobile","moneypot","monitor"], // список подсказок для префикса "m"
["mobile","moneypot","monitor"], // список подсказок для префикса "mo"
["mouse","mousepad"], // список подсказок для префикса "mou"
["mouse","mousepad"], // список подсказок для префикса "mous"
["mouse","mousepad"], // список подсказок для префикса "mouse"
]
2️⃣ Пример
Продукты: products = ["havana"]
Искомое слово: searchWord = "havana"
Ответ:
[
["havana"], // список подсказок для префикса "h"
["havana"], // список подсказок для префикса "ha"
["havana"], // список подсказок для префикса "hav"
["havana"], // список подсказок для префикса "hava"
["havana"], // список подсказок для префикса "havan"
["havana"], // список подсказок для префикса "havana"
]
✅ Реализация
Как я писал в начале, первое что приходит в голову для решения этой задачи — преобразовать исходный массив в дерево и обходить его в глубину.
Задача разделяется на 2 подзадачи:
— Имплементировать структуру данных Trie и преобразовать входящий массив
— Имплементировать метод Closest, который по префиксу вернет массив подсказок.
Помимо этого есть несколько решений по оптимизации: например, можно обходить дерево с самого большого возможного префикса. Тогда можно реализовать "всплытие" подсказок и избежать лишних обходов в глубину. Или же можно пожертвовать памятью и для каждого узла дерева сохранять набор подсказок в момент добавления нового слов.
Please open Telegram to view this post
VIEW IN TELEGRAM
algorithmics-blog.github.io
Система поиска подсказок
Подробный разбор решения задачи с примерами на языках TypeScript и GO
👍3❤2
Так как в этой задаче баланс между операциями записи и чтения смещен в сторону записи, нам необходимо минимизировать операции по модификации исходного массива. В данном случае нам на помощь может прийти сортировка и бинарный поиск:
— В отсортированном массиве подсказки для каждого префикса будут идти друг за другом, поэтому задача сведется к поиску первого элемента в массиве по префиксу и последующей проверки двух следующих элементов,
— С поиском первого элемента в отсортированном массиве хорошо справится бинарный поиск
➡️ Оптимальное решение
#medium #trie #binary_search
— В отсортированном массиве подсказки для каждого префикса будут идти друг за другом, поэтому задача сведется к поиску первого элемента в массиве по префиксу и последующей проверки двух следующих элементов,
— С поиском первого элемента в отсортированном массиве хорошо справится бинарный поиск
#medium #trie #binary_search
Please open Telegram to view this post
VIEW IN TELEGRAM
algorithmics-blog.github.io
Система поиска подсказок
Подробный разбор решения задачи с примерами на языках TypeScript и GO
2👍4❤3
Disjoint Set
Привет, друзья!
Сегодня мы с вами не будем решать конкретную задачу, а познакомимся с новой структурой данных.
Представим, что перед нами есть карта, на которой схематично обозначены 8 городов. При этом, города 0, 1, 2 и 3 соединены между собой дорогами. Города 4, 5 и 6 также соединены между собой, а город 7 обособлен и не имеет сообщения с другими.
Таким образом города являются вершинами графов, а дороги — их ребрами.
Города могут иметь прямое соединение, как например 4 и 6, или же транзитивное как в случае 0 и 3. В результате мы имеем три непересекающихся множества:
— [0, 1, 2, 3]
— [4, 5, 6]
— [7]
Теперь нам нужно построить эффективную структуру, которая позволит быстро понимать, соединены ли два города между собой, и даст возможность объединять два непересекающихся множества в одно.
Для подобных задач можно использовать структуру данных Disjoint Set, которую также иногда называют Union Find.
Базовая реализация
Базово такая структура данных должна поддерживать три основных метода
find — Находит рутовый элемент в множестве для указанного узла;
union — Объединяет два множества путем соединения двух вершин в них между собой;
connected — Проверяет соединены ли две вершины графа между собой, то есть входят ли они в одно множество.
Внутри структура будет хранить связи между вершинами графа в виде массива, где индекс массива обозначает номер города, а значение по индексу — индекс рутового узла в графе.
- В первом множестве решим, что рутовым узлом будет город с номером 0. Он же является рутовым узлом для самого себя.
- Во втором множестве выберем город с номером 4. Он также является рутовым узлом для самого себя.
- Семерка ни с чем не связана, поэтому она является рутовым узлом в своем множестве.
Таким образом для нашего случая массив должен иметь следующий вид.
Поиск
Теперь не сложно догадаться, что для реализации поиска достаточно получить индекс рутового узла для конкретного города по его индексу в массиве.
Проверка связности
Проверка связности тоже реализуется крайне легко. Нужно получить рутовые элементы для города x и y при помощи метода find и сравнить их. Если два города имеют один и тот же рутовый город в графе, то они связаны либо напрямую, либо транзитивно.
Объединение множеств
Теперь предположим, что нам нужно соединить города с номерами 3 и 4, тем самым объединив первое и второе множества.
Мы решаем, что у объединенного множества родительский элемент остается равным 0. Это означает, что города с номерами 3, 4 и 5 должны получить связь с ним, то есть обновить значение своего рутового узла на 0.
Таким образом наш массив должен получить следующие значения.
Теперь осталось имплементировать структуру данных по описанной логике.
Подробную реализацию можно посмотреть в нашем блоге
#disjoint_set #graph
Привет, друзья!
Сегодня мы с вами не будем решать конкретную задачу, а познакомимся с новой структурой данных.
Представим, что перед нами есть карта, на которой схематично обозначены 8 городов. При этом, города 0, 1, 2 и 3 соединены между собой дорогами. Города 4, 5 и 6 также соединены между собой, а город 7 обособлен и не имеет сообщения с другими.
Таким образом города являются вершинами графов, а дороги — их ребрами.
Города могут иметь прямое соединение, как например 4 и 6, или же транзитивное как в случае 0 и 3. В результате мы имеем три непересекающихся множества:
— [0, 1, 2, 3]
— [4, 5, 6]
— [7]
Теперь нам нужно построить эффективную структуру, которая позволит быстро понимать, соединены ли два города между собой, и даст возможность объединять два непересекающихся множества в одно.
Для подобных задач можно использовать структуру данных Disjoint Set, которую также иногда называют Union Find.
Базовая реализация
Базово такая структура данных должна поддерживать три основных метода
find(x int) int
find — Находит рутовый элемент в множестве для указанного узла;
union(x int, y int)
union — Объединяет два множества путем соединения двух вершин в них между собой;
connected(x int, y int)
connected — Проверяет соединены ли две вершины графа между собой, то есть входят ли они в одно множество.
Внутри структура будет хранить связи между вершинами графа в виде массива, где индекс массива обозначает номер города, а значение по индексу — индекс рутового узла в графе.
- В первом множестве решим, что рутовым узлом будет город с номером 0. Он же является рутовым узлом для самого себя.
- Во втором множестве выберем город с номером 4. Он также является рутовым узлом для самого себя.
- Семерка ни с чем не связана, поэтому она является рутовым узлом в своем множестве.
Таким образом для нашего случая массив должен иметь следующий вид.
[0, 0 , 0, 0, 4, 4, 4, 7]
Поиск
Теперь не сложно догадаться, что для реализации поиска достаточно получить индекс рутового узла для конкретного города по его индексу в массиве.
Проверка связности
Проверка связности тоже реализуется крайне легко. Нужно получить рутовые элементы для города x и y при помощи метода find и сравнить их. Если два города имеют один и тот же рутовый город в графе, то они связаны либо напрямую, либо транзитивно.
Объединение множеств
Теперь предположим, что нам нужно соединить города с номерами 3 и 4, тем самым объединив первое и второе множества.
Мы решаем, что у объединенного множества родительский элемент остается равным 0. Это означает, что города с номерами 3, 4 и 5 должны получить связь с ним, то есть обновить значение своего рутового узла на 0.
Таким образом наш массив должен получить следующие значения.
[0, 0 , 0, 0, 0, 0, 0, 7]
Теперь осталось имплементировать структуру данных по описанной логике.
Подробную реализацию можно посмотреть в нашем блоге
#disjoint_set #graph
algorithmics-blog.github.io
Disjoint Set
Подробный разбор решения задачи с примерами на языках TypeScript и GO
1🔥7👍1
Количество провинций
Давайте закрепим знания про Disjoint Set новой задачей.
Сложность: 🟡 Средняя
ℹ️ Описание
Есть n городов, некоторые из которых соединены между собой.
Если город a напрямую соединен c городом b, а город b напрямую соединен с городом c, тогда города a и c косвенно соединены между собой.
Провинция — это группа напрямую или косвенно связанных между собой городов.
Вам дана матрица isConnected размером n x n, где isConnected[i][j] = 1, если i-й город и j-й город напрямую соединены, и isConnected[i][j] = 0 в противном случае.
Верните общее количество провинций.
⚠️ Ограничения
— Размер матрицы n — это целое число в диапазоне от 1 до 200
— В качестве значений в матрице используются только 1 b 0
— isConnected[i][j] == isConnected[j][i]
1️⃣ Пример
Входные данные:
Ответ: 2
2️⃣ Пример
Входные данные:
Ответ: 3
✅ Реализация
У этой задачи достаточно много решений и все они достаточно сложные. Но мы можем легко решить задачу, если будем использовать ранее реализованный DisjointSet
Алгоритм решения:
— Создать инстанс структуры данных DisjointSet.
— Определить переменную numberOfProvinces равную n в начале состояния. Далее мы будем уменьшать ее значение при объединении городов в провинцию.
—Так как главная диагональ матрицы isConnected отображает соединение каждого города с самим собой, то мы можем ее не рассматривать. Также нам не требуется проверять всю матрицу так как isConnected[i][j] == isConnected[j][i], поэтому будем перебирать элементы над главной диагональю. Для этого запустим цикл в цикле по i и j от i = 0 и j = i + 1.
— Если два города соединены (isConnected[i][j] == 1) и они уже не находятся в одном множестве, то мы объединяем эти города в множество при помощи метода — то мы объединяем города i и j в одну провинцию.
В итоге после перебора элементов матрицы переменная numberOfProvinces будет показывать количество получившихся провинций.
▶️ Реализация алгоритма ◀️
🅾️ Оценка сложности
По времени
— Перебор матрицы занимает O(n^2)
— Поиск методом find занимает O(n)
— Объединение методом union занимает O(n)
Общая сложность по памяти O(n^2).
По памяти
Сложность O(n) для хранения состояния структуры DisjointSet.
#graph #medium #disjoint_set
Давайте закрепим знания про Disjoint Set новой задачей.
Сложность: 🟡 Средняя
ℹ️ Описание
Есть n городов, некоторые из которых соединены между собой.
Если город a напрямую соединен c городом b, а город b напрямую соединен с городом c, тогда города a и c косвенно соединены между собой.
Провинция — это группа напрямую или косвенно связанных между собой городов.
Вам дана матрица isConnected размером n x n, где isConnected[i][j] = 1, если i-й город и j-й город напрямую соединены, и isConnected[i][j] = 0 в противном случае.
Верните общее количество провинций.
⚠️ Ограничения
— Размер матрицы n — это целое число в диапазоне от 1 до 200
— В качестве значений в матрице используются только 1 b 0
— isConnected[i][j] == isConnected[j][i]
1️⃣ Пример
Входные данные:
isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Ответ: 2
2️⃣ Пример
Входные данные:
isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Ответ: 3
✅ Реализация
У этой задачи достаточно много решений и все они достаточно сложные. Но мы можем легко решить задачу, если будем использовать ранее реализованный DisjointSet
Алгоритм решения:
— Создать инстанс структуры данных DisjointSet.
— Определить переменную numberOfProvinces равную n в начале состояния. Далее мы будем уменьшать ее значение при объединении городов в провинцию.
—Так как главная диагональ матрицы isConnected отображает соединение каждого города с самим собой, то мы можем ее не рассматривать. Также нам не требуется проверять всю матрицу так как isConnected[i][j] == isConnected[j][i], поэтому будем перебирать элементы над главной диагональю. Для этого запустим цикл в цикле по i и j от i = 0 и j = i + 1.
— Если два города соединены (isConnected[i][j] == 1) и они уже не находятся в одном множестве, то мы объединяем эти города в множество при помощи метода — то мы объединяем города i и j в одну провинцию.
В итоге после перебора элементов матрицы переменная numberOfProvinces будет показывать количество получившихся провинций.
🅾️ Оценка сложности
По времени
— Перебор матрицы занимает O(n^2)
— Поиск методом find занимает O(n)
— Объединение методом union занимает O(n)
Общая сложность по памяти O(n^2).
По памяти
Сложность O(n) для хранения состояния структуры DisjointSet.
#graph #medium #disjoint_set
Please open Telegram to view this post
VIEW IN TELEGRAM
1🔥2❤1