Топологическая сортировка
Самый простой вариант данной сортировки - это изменение DFS обхода. В DFS мы начинаем с вершины, сначала выводим ее на печать, а зачем рекурсивно вызываем DFS для смежных вершин. В топологической сортировке - мы будем использовать стек!
Мы не будем печатать сразу наши вершины, мы будем сначала вызывать рекурсивно топологическую сортировку для всех вершин, а после их записывать в стек. В результате мы распечатаем содержимое стека.
Самое важное, что вершина помещается только тогда, когда все ее смежные вершины находятся в стеке.
Data Science: Алгоритмы и Структуры данных
Самый простой вариант данной сортировки - это изменение DFS обхода. В DFS мы начинаем с вершины, сначала выводим ее на печать, а зачем рекурсивно вызываем DFS для смежных вершин. В топологической сортировке - мы будем использовать стек!
Мы не будем печатать сразу наши вершины, мы будем сначала вызывать рекурсивно топологическую сортировку для всех вершин, а после их записывать в стек. В результате мы распечатаем содержимое стека.
Самое важное, что вершина помещается только тогда, когда все ее смежные вершины находятся в стеке.
Data Science: Алгоритмы и Структуры данных
Структура данных - строки
Строки определяются как массив символов. Разница между символьным массивом и строкой заключается в том, что строка заканчивается специальным символом "\0"
Объвить строку так же просто как объявить одномерный массив. Обращаю особое ваше внимание, что каждый символ строки хранится отдельно в ячейке. И как одномерный массив - строки имеют всё те же свойства.
Data Science: Алгоритмы и Структуры данных
Строки определяются как массив символов. Разница между символьным массивом и строкой заключается в том, что строка заканчивается специальным символом "\0"
Объвить строку так же просто как объявить одномерный массив. Обращаю особое ваше внимание, что каждый символ строки хранится отдельно в ячейке. И как одномерный массив - строки имеют всё те же свойства.
Data Science: Алгоритмы и Структуры данных
Разница между 2мя большими числами
Даны два числа в виде строк. Числа могут быть очень большими (не помещаться в long long int), задача - найти разницу этих двух чисел.
Data Science: Алгоритмы и Структуры данных
Даны два числа в виде строк. Числа могут быть очень большими (не помещаться в long long int), задача - найти разницу этих двух чисел.
Data Science: Алгоритмы и Структуры данных
Разница между 2мя большими числами
1. Поверните обе строки (чтобы конец стал началом) - reverse string operation. Создайте пустую строку для результата
2. Продолжайте вычитать цифры одну за одной из 0го индекса(в повернутых строка) - до конца меньшей строки, добавьте разницу, если она положительна в конец результата. Если разница отрицательна, то прибавьте 10 и отслеживайте перенос как +1, если положительный, то перенос равен 0
3. Снова переверните результативную строку
Как видите: чтобы посчтитать разницу между 2мя строками - мы используем обычную математику(якобы в столбик)
Data Science: Алгоритмы и Структуры данных
1. Поверните обе строки (чтобы конец стал началом) - reverse string operation. Создайте пустую строку для результата
2. Продолжайте вычитать цифры одну за одной из 0го индекса(в повернутых строка) - до конца меньшей строки, добавьте разницу, если она положительна в конец результата. Если разница отрицательна, то прибавьте 10 и отслеживайте перенос как +1, если положительный, то перенос равен 0
3. Снова переверните результативную строку
Как видите: чтобы посчтитать разницу между 2мя строками - мы используем обычную математику(якобы в столбик)
Data Science: Алгоритмы и Структуры данных
Задача на бинарные строки
Давайте сначала разберемся что такое бинарные строки! На самом деле тут ничего сложного: это строки которые могут содержать только 2 различных символа. К примеру a и b: abbbbaaa
А теперь после теории, перейдем к задаче.
Преобразуйте данную строку в строку, в которой не будет содержаться значение подстроки "ab". Чтобы убрать "ab", мы можем пользоваться операциями, в которой мы заменим эту подстроку на "bba". Основная цель данной задачи, найти общее количество операций, которые необходимы для преобразование данной строки.
Input : s = 'abbaa'
Output : 2
Объяснение:
Тут, 'ab'baa заменяется на s = bbabaa
bb'ab'aa а тут на s = bbbbaaa
Нам потребовалось 2 операции на это.
Попробуйте решить данную задачу.
Data Science: Алгоритмы и Структуры данных
Давайте сначала разберемся что такое бинарные строки! На самом деле тут ничего сложного: это строки которые могут содержать только 2 различных символа. К примеру a и b: abbbbaaa
А теперь после теории, перейдем к задаче.
Преобразуйте данную строку в строку, в которой не будет содержаться значение подстроки "ab". Чтобы убрать "ab", мы можем пользоваться операциями, в которой мы заменим эту подстроку на "bba". Основная цель данной задачи, найти общее количество операций, которые необходимы для преобразование данной строки.
Input : s = 'abbaa'
Output : 2
Объяснение:
Тут, 'ab'baa заменяется на s = bbabaa
bb'ab'aa а тут на s = bbbbaaa
Нам потребовалось 2 операции на это.
Попробуйте решить данную задачу.
Data Science: Алгоритмы и Структуры данных
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}
Data Science: Алгоритмы и Структуры данных | Чат 💬
Задача данного алгоритма найти все вхождения шаблона в текст за линейное время. Пусть для текста равна 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}
Data Science: Алгоритмы и Структуры данных | Чат 💬
❤2
Please open Telegram to view this post
VIEW IN TELEGRAM
Для чего и как построить 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. Если наоборот больше: то можно расширить интервал
Data Science: Алгоритмы и Структуры данных | Чат 💬
Идея состоит в том: чтобы объеденить темплейт и текст и создать единую строку, а после для нее построить 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. Если наоборот больше: то можно расширить интервал
Data Science: Алгоритмы и Структуры данных | Чат 💬
16 сентября в Arena Breakout: Infinite выходит седьмой сезон — «Утопия»
Если не сталкивались с игрой: это бесплатный тактический шутер про вылазки за добычей. Заходишь на локацию со своим снаряжением, набираешь лут и пытаешься уйти живым. Погиб — потерял всё, что было с собой.
Что завозят в новом сезоне:
• Заражённая зона — три карты превращаются в биоопасные локации с ночью, туманом и ливнем, по ним бродят шесть видов мутантов. Другие игроки при этом никуда не делись
• Режим на выживание — отдельный PvE без риска: снаряжение с собой не берёшь и ничего не теряешь, просто отбиваешься от волн и открываешь усиления
• Торговец прямо в рейде — можно обменять припасы и разведданные или докупить снаряжение
• Два новых ствола, сезонные обвесы и переработанная стрельба: дальность выше, попадания в голову ощутимее
• На старте бесплатно выдают прокачиваемую сапёрную лопату, скины и билеты, а между игроками разыгрывают 200 000 очков
Игра бесплатная, качается в Steam, российский регион поддерживается → https://abi.go.link/2wzTb
Если не сталкивались с игрой: это бесплатный тактический шутер про вылазки за добычей. Заходишь на локацию со своим снаряжением, набираешь лут и пытаешься уйти живым. Погиб — потерял всё, что было с собой.
Что завозят в новом сезоне:
• Заражённая зона — три карты превращаются в биоопасные локации с ночью, туманом и ливнем, по ним бродят шесть видов мутантов. Другие игроки при этом никуда не делись
• Режим на выживание — отдельный PvE без риска: снаряжение с собой не берёшь и ничего не теряешь, просто отбиваешься от волн и открываешь усиления
• Торговец прямо в рейде — можно обменять припасы и разведданные или докупить снаряжение
• Два новых ствола, сезонные обвесы и переработанная стрельба: дальность выше, попадания в голову ощутимее
• На старте бесплатно выдают прокачиваемую сапёрную лопату, скины и билеты, а между игроками разыгрывают 200 000 очков
Игра бесплатная, качается в Steam, российский регион поддерживается → https://abi.go.link/2wzTb
Задача N - королев
Многие, посмотрев сериал Queens Gambit начали играть снова в шахматы, не так ли? Однако спешу вас расстроить, шахматы потеряли свою актуальность ибо любая машина вас сможет обыграть. Случается это потому, что можно очень легко просчитать любой ваш следующий ход или вашу цель.
Я хочу сегодня поговорить об одной задаче: N-Queen. Суть задачи заключается в том, как расположить на шахматной доске NxN, N королев. Чтобы ни одна из королев не нападала на другую стояющую рядом.
Давайте сегодня, я вам дам время подумать и понять как такую задачу можно решить. Пару советов:
1. попробуйте визуализировать данную проблему
2. не подсматривайте решения, ибо их много. Попробуйте решить самостоятельно. А потом мы уже обсудим виды решений
Data Science: Алгоритмы и Структуры данных | Чат 💬
Многие, посмотрев сериал Queens Gambit начали играть снова в шахматы, не так ли? Однако спешу вас расстроить, шахматы потеряли свою актуальность ибо любая машина вас сможет обыграть. Случается это потому, что можно очень легко просчитать любой ваш следующий ход или вашу цель.
Я хочу сегодня поговорить об одной задаче: N-Queen. Суть задачи заключается в том, как расположить на шахматной доске NxN, N королев. Чтобы ни одна из королев не нападала на другую стояющую рядом.
Давайте сегодня, я вам дам время подумать и понять как такую задачу можно решить. Пару советов:
1. попробуйте визуализировать данную проблему
2. не подсматривайте решения, ибо их много. Попробуйте решить самостоятельно. А потом мы уже обсудим виды решений
Data Science: Алгоритмы и Структуры данных | Чат 💬
Telegram
Data Science: Алгоритмы и Структуры данных
Мы не претендуем на оригинальность контента, мы лишь собираем материал из открытых источников.
Ссылка: @Portal_v_IT
Сотрудничество, авторские права: @oleginc, @tatiana_inc
Канал на бирже: https://telega.in/c/structuredata
Ссылка: @Portal_v_IT
Сотрудничество, авторские права: @oleginc, @tatiana_inc
Канал на бирже: https://telega.in/c/structuredata
Машинное обучение: анализ временных рядов Azure Machine Learning для поиска аномалий
В данной статье автор рассказывает, как использовать модуль Time Series Anomaly Detection сервиса машинного обучения Azure Machine Learning для определения аномальных показателей датчиков.
➡️ Читать статью
Data Science: Алгоритмы и Структуры данных | Чат 💬
В данной статье автор рассказывает, как использовать модуль Time Series Anomaly Detection сервиса машинного обучения Azure Machine Learning для определения аномальных показателей датчиков.
Data Science: Алгоритмы и Структуры данных | Чат 💬
Please open Telegram to view this post
VIEW IN TELEGRAM