Всё про Алгоритмы и Структуры данных

Описание операции вставки в Trie Каждый узел в Trie состоит из нескольких ветвей. Каждая ветвь представляет собой возможный символ-ключ. Интересно то, что последний узел каждого поддерева Trit - будет являться концом слова. Простая структура Node выглядит примерно так: 1. Инициализация детей 2. флаг о конце слова Вставка в Trie - одна из простых операций. Каждый символ вставляется как отдельный узел Trie. Важно, обратить внимание, что дочерние элементы - это массив указателей(ссылок) на узлы дерева следующего уровня. Ключевой символ действует как индекс в дочернем массиве. Если входной ключ новый или расширенный - нам нужно построить таким образом ключи и пометить конец слова флагом конца. Длина ключа - определляет нашу глубину Trie.

Студенты заставили своего угарного препода по программированию создать телеграм-канал. Его обожают за умение просто и остроумно рассказывать про код, рекурсию и объяснять сложные алгоритмы так, что любой школьник сможет повторить. В свободное время он выводит онлайн-курсы на чистую воду и рассказывает как запросто прокачаться до сениора за полгода. Если ты работаешь или учишься в IT, подписка обязательна — https://t.me/+IRo8tmwSlh5lYzYy

Структура данных - Префиксное(нагруженное) дерево - Trie Сегодня (и последующие несколько дней) разберем еще одну продвинутую структуру данных: Trie Префиксное дерево (Trie) - эффективная структура данных для поиска информации. Используя Trie, сложность поиска у вас сведется к длине ключа, что является оптимальным пределом. Используя Trie - вы можете икать и вставлять ключ за О(M): где M максимальная длина строки. Однако будет штраф за то как это хранится. Еще плюсом Trie будет являеться то, что вы легко сможете вывести все слова в алфавитном порядке А также поможет вам эффективно решать задачи по поиску префикса(суффикса). Задачу подобную я скоро опубликую: она как раз была недавно в leetcode challenge

Код вставки элемента в XOR Linked List

Обход связного XOR списка Продолжаем тему XOR Linked List и сегодня поговорим про обходы данного листа. Перемещаться по списку XOR мы можем как в прямом, так и в обратном направлении. Просматривая список, нам нужно запоминать адреса узла, к которому ранее осуществлялся доступ, чтобы вычислить адрес следующего узла. Например когда мы находимся в узле С, у нас должен быть адрес B. Из XOR мы выщемляем адрес для C, а при помощи C (и функции npx) мы можем узнать адрес следующей ноды. Завтра посмотрим на SourceCode для полного понимания данного процесса.

Продолжение обсуждения про XOR Linked List Итак, я предлагаю перед тем как продолжать более детально смотреть на определенные примеры и задачи по данной теме. Всё таки немного глубже посмотреть на данную структуру. Я нашел идеальную статью по этой теме: https://www.linuxjournal.com/article/6828?page=0,0 Не обращайте внимание на дату создания. Ибо этот топик актуален до сих пор. Ну и плюсом будет в принципе глянуть на Linux Journal: там публиковалось очень много интересных топиков в свое время.

XOR Linked List Начнем рассматривать сложные структуры данных. Сегодня начнем одной из таких: XOR связный список. Обычный двусвязный список требует места для двух адресных полей для хранения адресов предыдущего и следующего узлов. Версия двусвязного списка с XOR может быть создана с использованием только одного пространства для адресного поля с каждым узлом. В связанном списке XOR вместо хранения фактических адресов памяти каждый узел хранит XOR адресов предыдущего и следующего узлов.

Очень простое объяснение сложности алгоритмов Иногда я нахожу на просторах интернета очень неплохие статьи, которыми могу поделиться. Сегодня одна из таких, которая позволит вам на базовом уровне разобраться что же такое сложность алгоритмов: https://thatcomputerscientist.com/big-o-notation-explained-as-easily-as-possible Для более глубокого изучения данного вопроса я порекомендую курс Роберта Седжевика: https://www.coursera.org/learn/analysis-of-algorithms Он максимально позволит вам овладеть данной темой.

Backtracking алгоритм (Поиск с возвратом) Один из самых известных алгоритмов по решению специфичных задач поиска - является Backtracking алгоритм. Это по факту даже техника для рекурсивного решения проблем, пытаясь построить решение постепенно, удаляя те решения, которые не удовлетворяют условиям. Данным алгоритмом решается ряд задач (очень схожих по смыслу): нахождение позиций шахматным фигурам, решение судоку, проблемы с раскраской, различные пазлы, гимильтоновый цикл и другие схожие тематики. Обратите внимание на картинку - там представлен способ решения нашей задачи N-Queens. Картинка очень удобна для понимания самого подхода и поможет вам уже воспроизвести алгоритм (рекурсивный) самостоятельно!

Наивное решение проблемы N-королев Вчера была интересная задача и я надеюсь, она многим понравилась! Однако пора приступить к способам ее решения. Начну я с самого простого способа (по факту перебора). Скорее всего вы этим способом и пользовались при выставлении королев(ферзей) на доске. Итак: 1. Создать цикл с проверкой того, что есть непроверенные конфигурации 2. Внутри цикла генерировать новую конфигурацию и если королевы не атакуют, тогда распечатать эту конфигурацию. Проблема данного подхода, я думаю, очевидна! Это глупый и наивный перебор абсолютно всех вариантов и он займет недопустимое количество времени. А вот хорошее решение, я сегодня уже подскажу, но расскажу о нем завтра. Есть такой подход как BackTracking - попробуйте посмотреть в его направлении.

Задача N - королев Многие, посмотрев сериал Queens Gambit начали играть снова в шахматы, не так ли? Однако спешу вас расстроить, шахматы потеряли свою актуальность ибо любая машина вас сможет обыграть. Случается это потому, что можно очень легко просчитать любой ваш следующий ход или вашу цель. Я хочу сегодня поговорить об одной задаче: N-Queen. Суть задачи заключается в том, как расположить на шахматной доске NxN, N королев. Чтобы ни одна из королев не нападала на другую стояющую рядом. Давайте сегодня, я вам дам время подумать и понять как такую задачу можно решить. Пару советов: 1. попробуйте визуализировать данную проблему 2. не подсматривайте решения, ибо их много. Попробуйте решить самостоятельно. А потом мы уже обсудим виды решений

​Математика в жизни не пригодится? Задача: Женя знает математику на уровне «посчитать зарплату после вычета налога» и «оставить курьеру 10% чаевых», при этом хочет работать в IT-сфере. Какова вероятность, что Женя сможет трудоустроиться? Ответ: Недостаточно данных. Зато данных всегда хватает в работе аналитиков и специалистов по Data Science. Выполнять задачи этим специалистам помогают электронные таблицы, базы данных, языки программирования и математика. Если ваши математические навыки остались, как у Жени, на уровне 7 класса школы, прокачайте их на курсе «Математика для анализа данных» от Практикума. И вероятность вашего трудоустройства пойдёт вверх 📈 Программа курса разработана с учётом требований IT-рынка и содержит все необходимые разделы: - Линейная алгебра: матрицы, векторы, нормы и определители. - Математический анализ: функции и их свойства, производные и интегралы. - Линейная регрессия, коллинеарность, визуализация и другие приложения алгебры в анализе данных. - Теория вероятностей и статистика: гипотезы, A/B-тесты и бутстрэп. А в конце курса студенты проходят математическое собеседование в тренажёре-симуляторе. Итого: Начать учиться можно бесплатно и в любой момент. Специальная подготовка не нужна. После регистрации и оплаты вы получаете доступ к полному курсу, рассчитанному на 4 месяца. Обучение стоит 30 000 ₽ единоразово или в рассрочку — от 1 631 ₽/мес.

Для чего и как построить Z-массив Идея состоит в том: чтобы объеденить темплейт и текст и создать единую строку, а после для нее построить Z-array. Если что, на все это нам понадобиться не больше чем линейное время. А вот для построения самого Z-array нам уже понадобиться квадратичная функция. Для построения нам придется поддерживать определенный интервал L,R, который по факту и содержит необходимую подстроку. Шаги следующие: 1.Если i-шаг> R, то нет префиксной подстроки, которая начинается перед i и заканчивается после i. Поэтому сбрасываются L и R и вычисляются новые 2. Если i <= R, то K = i - L, и тем самым Zi >= min(ZK, R-i + 1) Появляются 2 случая тогда: 1. Если ZK < R-i + 1 то нет префиксной подстроки и интервал остается прежним 2. Если наоборот больше: то можно расширить интервал

Z - алгоритм Задача данного алгоритма найти все вхождения шаблона в текст за линейное время. Пусть для текста равна n, а длина шаблона - m, тогда общее затраченное время составит O(m+n) с линейной пространственной сложностью. Для этого мы строим специальный Z-массив. Что такое Z массив? Для строки str0..n-1 массив Z имеет ту же длину, что и строка. Элемент Zi массива Z хранит длину самой длинной подстроки, начиная с Zi, которая таке является префиксом str0..n-1 Пример: str = "aaaaaa" Z = {x, 5, 4, 3, 2, 1}

Задача на бинарные строки Давайте сначала разберемся что такое бинарные строки! На самом деле тут ничего сложного: это строки которые могут содержать только 2 различных символа. К примеру a и b: abbbbaaa А теперь после теории, перейдем к задаче. Преобразуйте данную строку в строку, в которой не будет содержаться значение подстроки "ab". Чтобы убрать "ab", мы можем пользоваться операциями, в которой мы заменим эту подстроку на "bba". Основная цель данной задачи, найти общее количество операций, которые необходимы для преобразование данной строки. Input : s = 'abbaa' Output : 2 Объяснение: Тут, 'ab'baa заменяется на s = bbabaa bb'ab'aa а тут на s = bbbbaaa Нам потребовалось 2 операции на это. Попробуйте решить данную задачу.

🎉 Среди студентов МГУ прошло голосование на 3 лучших телеграм-канала по программированию. Поздравляем победителей: Просто Python – канал для всех, кто хочет освоить самый перспективный язык 2022 года. Гайды для новичков, шпаргалки, фишки, программы и многое другое. Этичный Хакер – уроки по хакингу, инструкциии по взлому, деанону, защите устройств и бесплатными курсами по информационной безопасности. IT-Сэнсэй - хранилище бесплатных курсов и плейлистов по программированию от топовых онлайн-школ и преподавателей.

Разница между 2мя большими числами 1. Поверните обе строки (чтобы конец стал началом) - reverse string operation. Создайте пустую строку для результата 2. Продолжайте вычитать цифры одну за одной из 0го индекса(в повернутых строка) - до конца меньшей строки, добавьте разницу, если она положительна в конец результата. Если разница отрицательна, то прибавьте 10 и отслеживайте перенос как +1, если положительный, то перенос равен 0 3. Снова переверните результативную строку Как видите: чтобы посчтитать разницу между 2мя строками - мы используем обычную математику(якобы в столбик)

Разница между 2мя большими числами Даны два числа в виде строк. Числа могут быть очень большими (не помещаться в long long int), задача - найти разницу этих двух чисел.

Структура данных - строки Строки определяются как массив символов. Разница между символьным массивом и строкой заключается в том, что строка заканчивается специальным символом "\0" Объвить строку так же просто как объявить одномерный массив. Обращаю особое ваше внимание, что каждый символ строки хранится отдельно в ячейке. И как одномерный массив - строки имеют всё те же свойства.

Топологическая сортировка Самый простой вариант данной сортировки - это изменение DFS обхода. В DFS мы начинаем с вершины, сначала выводим ее на печать, а зачем рекурсивно вызываем DFS для смежных вершин. В топологической сортировке - мы будем использовать стек! Мы не будем печатать сразу наши вершины, мы будем сначала вызывать рекурсивно топологическую сортировку для всех вершин, а после их записывать в стек. В результате мы распечатаем содержимое стека. Самое важное, что вершина помещается только тогда, когда все ее смежные вершины находятся в стеке.