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

Метод опорных векторов

SVM (Support Vector Machine) — это алгоритм машинного обучения, используемый для задач классификации и регрессии. Он работает на основе нахождения гиперплоскости, которая наилучшим образом разделяет данные на различные классы.

Гиперплоскость — векторное пространство с n измерениями может быть разделено с помощью гиперплоскости, которая является подпространством размерности n−1. В двухмерном пространстве это линия, в трехмерном — плоскость, а в общем случае — гиперплоскость.

Задача SVM заключается в нахождении гиперплоскости, которая максимизирует расстояние (зазор) между ближайшими точками разных классов. Эти ближайшие точки называются опорными векторами.

SVM стремится максимизировать расстояние между классами, что помогает улучшить обобщающую способность модели. Чем больше зазор, тем меньше вероятность ошибки на тестовых данных.

Логистическая регрессия

Это статистический метод, используемый для моделирования зависимости между одной или несколькими независимыми переменными и бинарной зависимой переменной (например, "да/нет", "1/0", "успех/неудача"). Этот метод особенно полезен в задачах классификации, где необходимо предсказать вероятность принадлежности объекта к одной из категорий.

Применение логистической регрессии:

- Классификация: Логистическая регрессия часто используется для классификации объектов на две категории. Например, предсказание, будет ли клиент купить продукт или нет, на основе его характеристик.

- Медицинские исследования: В медицине логистическая регрессия используется для предсказания вероятности заболевания (например, наличие или отсутствие болезни на основе различных факторов).

- Социальные науки: Применяется для анализа данных, где исследуется влияние различных факторов на бинарный результат (например, выборы, респонденты, ответившие "да" или "нет").

Полиномиальная регрессия

Это расширение линейной регрессии, которое позволяет моделировать более сложные зависимости между независимой переменной X и зависимой переменной Y. В отличие от линейной регрессии, где мы предполагаем линейную зависимость, полиномиальная регрессия использует полиномиальные функции для описания связи между переменными.

Преимущества полиномиальной регрессии
- Полиномиальная регрессия может моделировать нелинейные зависимости, что делает её более подходящей для сложных данных по сравнению с линейной регрессией.
- Коэффициенты можно легко интерпретировать как влияние каждого полиномиального термина на зависимую переменную.

Матричный метод линейной регрессии

Этот метод находит широкое применение в различных сферах жизни и бизнеса для анализа данных, например:

1. Финансовый анализ и прогнозирование
- Оценка рыночных рисков и доходностей.
- Прогнозирование цен на жилье.

2. Медицина и здравоохранение
- Оценка влияния факторов на здоровье.
- Анализ и прогнозирование медицинских затрат.

3. Маркетинг и бизнес-аналитика
- Прогнозирование спроса на товары и услуги.
- Анализ поведения клиентов.

4. Индустрия развлечений
- Рекомендательные системы.
- Прогнозирование кассовых сборов фильмов.

• infosec - один из самых ламповых каналов по информационной безопасности, где говорят об истории ИТ, публикуют актуальные новости и пишут технический материал по разным темам:

- Как зарождалась Флибуста?
- Сервисы для обеспечения безопасности в сети;
- Каким образом "компьютерные мастера" обманывают своих клиентов?
- Бесплатный бот, который проверит файлы на предмет угроз более чем 70 антивирусами одновременно.

• А еще у нас часто проходят розыгрыши самых актуальных и новых книг по ИБ. Так что присоединяйся, у нас интересно!

Линейная регрессия (Linear regression)

Один из простейший алгоритмов машинного обучения, описывающий зависимость целевой переменной от признака в виде линейной функции.

Цель линейной регрессии — поиск линии, которая наилучшим образом соответствует этим точкам.

Модель линейной регрессии выглядит следующим образом:
Y = aX + b, где:
X — независимая переменная,
Y — зависимая переменная (предсказываемое значение),
a — коэффициент наклона,
b — смещение (пересечение с осью Y).

Для оценки точности регрессии используют разные метрики, например MSE (mean squared error — средняя квадратическая ошибка). Чем ниже MSE, тем лучше модель.

K-й самый большой элемент в массиве

Проблема: Дан несортированный массив целых чисел nums и целое число k. Необходимо реализовать алгоритм, который возвращает k-й по величине элемент массива.

Под k-м самым большим элементом мы подразумеваем k-й самый большой элемент в отсортированном порядке, а не k-й отдельный элемент.

В решение не используется сортировка.

Пример:
Input: nums = [2,3,1,1,5,5,4], k = 3
Output: 4

Вес последнего камня

Проблема: Дан массив целых чисел, где Stones[i] представляет вес i-го камня.
Представим, что мы играем в игру с камнями. На каждом ходу выбираем два самых тяжелых камня и разбиваем их вместе. Предположим, что два самых тяжелых камня имеют вес x и y, причем x <= y.

Результат удара может быть:
- Если x == y, оба камня уничтожаются, и
- Если x != y, камень веса x уничтожается, а камень веса y приобретает новый вес y - x.

В конце игры остается не более одного камня. Необходимо реализовать алгоритм, который возвращает вес последнего оставшегося камня. Если камней не осталось, верните 0.

Пример: Input: stones = [2,3,6,2,4]
Output: 1

Найти повторяющееся число

Проблема: Дан массив целых чисел nums, содержащий n + 1 целое число. Каждое целое число в nums находится в диапазоне [1, n] включительно.

Каждое целое число встречается ровно один раз, за ​​исключением одного целого числа, которое встречается два или более раз. Необходимо реализовать алгоритм, который возвращает число, которое встречается более одного раза.

Решение не изменяет числа массива и использует O(1) дополнительное пространство.

Один из наиболее эффективных методов использует идею цикла (tortoise and hare), аналогичную той, которая используется в проблеме обнаружения цикла в связном списке.

Пример 1: Input: nums = [1,2,3,2,2]
Output: 2

Пример 2: Input: nums = [1,2,3,4,4]
Output: 4

Завершился финал международного чемпионата по программированию Yandex Cup 2024

Финал в Ташкенте собрал 200 человек из 18 стран. Участники боролись за рекордный призовой фонд в размере 16 млн рублей — компания увеличила первоначальную сумму на 3,5 млн рублей для поддержки специалистов в области машинного обучения.

Главной темой соревнования стала «Цифровая цивилизация». Задачи участников включали в себя расшифровку древних письменностей, восстановление артефактов и анализ торговых путей, что позволило прикоснуться к истории и быту древних цивилизаций через призму технологий.

Одной из ключевых зон финала чемпионата в Ташкенте стал «Музей Айтичности», где гости и финалисты могли представить, как бы выглядели современные технологии через тысячу лет. Экспозиция включала художественную галерею, отражающую жизнь современных разработчиков и раскопки IT-офисов компаний.

Медиана двух отсортированных массивов

Проблема: Даны два целочисленных массива nums1 и nums2 размера m и n соответственно, каждый из которых отсортирован в порядке возрастания. Необходимо реализовать алгоритм, который возвращает медианное значение среди всех элементов двух массивов.

Медиана набора чисел — это значение, отделяющее верхнюю половину от нижней половины данных.

Решение работает за O(log(m+n)) времени.

Пример 1: Input: nums1 = [1,2], nums2 = [3]
Output: 2.0

Пример 2: Input: nums1 = [1,3], nums2 = [2,4]
Output: 2.5

Поиск в повернутом отсортированном массиве

Проблема: Дан массив длины n, который изначально был отсортирован по возрастанию. Далее его поворачивали от 1 до n раз. Например, массив nums = [1,2,3,4,5,6] может выглядеть следующим образом:
[3,4,5,6,1,2], если его повернули 4 раза.
[1,2,3,4,5,6], если он был повернут 6 раз.

Учитывая повернутый отсортированный массив nums и число (target), которое надо найти, алгоритм должен возвращать индекс target в пределах nums или -1, если он отсутствует. Предполагается, что все элементы в отсортированном повернутом массиве уникальны.

Решение, работающее за время O(n), тривиально, поэтому реализацию должна быть за время O(log n).

Пример 1: Input: nums = [3,4,5,6,1,2], target = 1
Output: 4

Пример 2: Input: nums = [3,5,6,0,1,2], target = 4
Output: -1

Erid: 2VtzqubHjSF
⚡️Всероссийский Хакатон ФИЦ 2024

🚀Попробуйте себя в одном из предложенных кейсов:

Кейс №2. Выявление трендов в сфере бухгалтерского учета, поиск «болей» бухгалтера: разработать алгоритм для поиска новых трендов и проблем бухгалтера.

Кейс №8. Формирование фото и видео контента с использованием нейросетей на основе биографии и фото персоны.

Кейс №10. Цифровая карта подземных коммуникаций с использованием Cesium.

Кейс №12. Цифровой сервис для ведения реестра зеленых насаждений города Москвы.

Кейс №17. Стартовый (профилактический) комплаенс: предотвращение рисков с помощью AI.

Кейс №19. Parallax-scroll лендинг для сайта Insidium.

И другие 19 кейсов смотрите на сайте: https://фиц2024.рф/hackathon

Хакатон пройдет в 2 этапа: Отборочный этап в Онлайн, Финал в Офлайн.

🏆Призовой фонд: 6 000 000 руб.
🔥Дедлайн регистрации: 28 ноября, 23:59
📅Даты отборочного этапа: 29 ноября - 2 декабря
🦾Даты финала: 3 - 4 декабря

Зарегистрируйтесь для участия в хакатоне: https://фиц2024.рф/hackathon

Реклама: ООО «Акселератор Возможностей» ИНН: 9704005146

Найти минимум в повернутом отсортированном массиве

Проблема: Дан массив длины n, который изначально был отсортирован по возрастанию. Далее его поворачивали от 1 до n раз. Например, массив nums = [1,2,3,4,5,6] может выглядеть следующим образом:
[3,4,5,6,1,2], если его повернули 4 раза.
[1,2,3,4,5,6], если он был повернут 6 раз.

Обратим внимание, что поворот массива 4 раза перемещает последние четыре элемента массива в начало. Вращение массива 6 раз дает исходный массив.

Предполагая, что все элементы в повернутом отсортированном массиве уникальны, реализуемый алгоритм должен возвращать минимальный элемент этого массива. Решение, работающее за время O(n), тривиально, поэтому реализацию должна быть за время O(log n).

Пример 1: Input: nums = [3,4,5,6,1,2]
Output: 1

Пример 2: Input: nums = [4,5,0,1,2,3]
Output: 0

❓Хотите создавать идеальные C++ API, которые не ломаются на первой же нагрузке?

👉 Тогда не пропустите этот бесплатный вебинар! 3 декабря в 20:00 мск — открытый урок, который кардинально изменит ваш подход к проектированию API на C++!

**Что вас ждет?**
- Понимание плохого и хорошего API: как отличить чудовищное API от шедевра?
- Умение правильно именовать сущности и разбивать их на атомарные элементы. Прокачаем навыки, чтобы не было «кучи кода» и «головной боли».
- Идеи data-oriented подхода для создания API в высоконагруженных приложениях.

Кому это будет полезно?
- Разработчикам, кто только знакомится с C++ или переходит с других языков.
- C++-программистам, которые хотят прокачать свои навыки разработки API.

Вы научитесь проектировать удобный, стабильный и эффективный API для C++, который будет работать как часы.

⭐️ Спикер Андрей Рыжиков — разработчик в НИИ обработки аэрокосмических изображений.

Успейте записаться на открытый урок и получите скидку на большое обучение «C++ Developer».

Для участия зарегистрируйтесь: https://clck.ru/3EqbbS

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576, www.otus.ru

Поедание бананов

Проблема: Дан целочисленный массив piles, где piles[i] — количество бананов в i-й стопке. Вам также дано целое число h, которое представляет собой количество часов, в течение которых вам нужно съесть все бананы.

Необходимо установить норму потребления бананов в час, равную k. Каждый час вы можете выбрать стопку бананов и съесть k бананов из этой стопки. Если в кучке меньше k бананов, вы можете съесть эту кучу, но не сможете съесть другую кучу в тот же час.

Реализуемый алгоритм должен возвращать минимальное целое число k такое, что вы сможете съесть все бананы за h часов.

Пример 1:
Input: piles = [1,4,3,2], h = 9
Output: 2

Пример 2:
Input: piles = [25,10,23,4], h = 4
Output: 25

Erid: 2Vtzqv6YtFZ

⚡️Всероссийский Хакатон ФИЦ 2024

🚀Попробуйте себя в одном из предложенных кейсов:
1. Система контроля и управления доступом:
- Разработка системы контроля и управления доступом в реальном времени. Система будет включать API для управления сотрудниками, точками доступа и интеграцию с системой видеонаблюдения.

2. Parallax-scroll лендинг для сайта Insidium:
- Разработка одностраничного приложения (SPA) с административной панелью, позволяющей редактировать контент лендинг-страницы.

3. Цифровой сервис для ведения реестра зеленых насаждений города Москвы:
- Разработать сервис по работе с панорамами города Москва c возможностью разметки и подключению существующих open-source моделей для решения задач.

4. Цифровой помощник юриста:
- Разработка веб-сервиса для автоматической генерации различных типовых юридических документов на основе данных, введенных пользователем, с возможностью последующей правки сгенерированного документа.

И другие 19 кейсов смотрите на сайте: https://фиц2024.рф/hackathon

Хакатон пройдет в 2 этапа: Отборочный этап в Онлайн, Финал в Офлайн.

🏆Призовой фонд: 6 000 000 руб.
🔥Дедлайн регистрации: 26 ноября, 23:59
📅Даты отборочного этапа: 29 ноября - 2 декабря
🦾Даты финала: 3 - 4 декабря

Зарегистрируйтесь для участия в хакатоне: https://фиц2024.рф/hackathon

Реклама: ООО «Акселератор Возможностей» ИНН: 9704005146

Поиск в 2D-матрице

Проблема: Дана двумерная целочисленная матрица (matrix) размера m x n и число (target), которое надо найти в матрице. Каждая строка матрицы сортируется в порядке неубывания. Первое целое число каждой строки больше последнего целого числа предыдущей строки. Необходимо реализовать алгоритм, который возвращает true, если число найдено в матрице, или false в противном случае.

Пример:
Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 10
Output: true

Самый большой прямоугольник в гистограмме

Проблема: Дан массив целых чисел heights, где heights[i] представляет высоту столбца. Ширина каждого столбца равна 1.

Необходимо реализовать алгоритм, который возвращает площадь наибольшего прямоугольника, который может быть сформирован среди столбцов.

function largestRectangleArea(heights) {
    heights.append(0) 
    stack = empty stack
    max_area = 0

    for i from 0 to length(heights) - 1 {
        while stack is not empty and 
        heights[i] < heights[stack.top()] {
            height = heights[stack.pop()]
            width = if stack is empty ? i : i - stack.top() - 1
            max_area = max(max_area, height * width)
        }
        stack.push(i)
    }
    return max_area
}

🚀 Приглашаем на бесплатный вебинар по C++! 🚀

Дата: 19 ноября 2024 года
Время: 20:00
Тема: Как протестировать C++ код и оценить степень собственной лени

На вебинаре поговорим о том, зачем разработчикам писать юнит-тесты, и какую пользу они несут. Посмотрим популярные фреймворки тестирования, такие как GTest и Boost, разберем несколько практических примеров. Затем попробуем оценить, достаточно ли тестов мы написали для своего кода.

На занятии:
1. Научимся подключать фреймворки тестирования к своему проекту при помощи CMake.
2. Напишем готовые к запуску тесты.
3. Поговорим о том, как измерить покрытие тестами кода, какие инструменты для этого существуют.

В результате:
1. Придем к тому, что вместе с кодом стоит сразу писать и юнит-тесты к нему.
2. В будущем с легкостью интегрируем любой фреймворк тестирования в свой проект.
3. Научимся не только писать тесты, но и мерить их покрытие.

👉🏻О курсе "Специализация C++ Developer" на Otus:
Длительность курса: 10 месяцев.
Формат: Онлайн.

Программа курса:
· Введение в язык C++: основы синтаксиса, структура программ, базовые конструкции.
· Классы и структуры: ООП, наследование, полиморфизм, шаблоны.
· Основы unit-тестирования: подключение фреймворков, написание тестов, измерение покрытия.
· Стандартная библиотека и полезные алгоритмы: контейнеры, ввод-вывод, алгоритмы.

📌Скидка 15%: действует до 17 ноября!

Не упустите шанс стать профессионалом в C++! Присоединяйтесь к вебинару и узнайте больше о курсе.
🔗 Регистрация на вебинар

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576, www.otus.ru

Температура воздуха

Проблема: Дан массив целых чисел, где температура[i] представляет собой дневную температуру в i-й день.

Необходимо реализовать алгоритм, который возвращает результат массива, где result[i] — это количество дней после i-го дня до появления более высокой температуры в будущий день. Если в будущем не будет дня, когда в i-й день будет более высокая температура, вместо этого установите result[i] в ​​0.

Пример 1:
Input: temperatures = [30,38,30,36,35,40,28]
Output: [1,4,1,2,1,0,0]

Пример 2:
Input: temperatures = [22,21,20]
Output: [0,0,0]

Обратная польская запись

Проблема: Дан массив строковых токенов, который представляет допустимое арифметическое выражение в обратной польской нотации. В результате возвращает целое число, представляющее оценку выражения.

Операнды могут быть целыми числами или результатами других операций. К операторам относятся «+», «-», «*» и «/». Предположим, что деление целых чисел всегда сокращается до нуля.

Пример:
Input: tokens = ["1","2","+","3","*","4","-"]
Output: 5
Объяснение: ((1 + 2) * 3) - 4 = 5

Проверка скобок

Проблема: Дана строка s, состоящая из следующих символов: '(', ')', '{', '}', '[' и ']'. Входная строка s действительна тогда и только тогда, когда:
- Каждая открытая скобка закрывается закрывающей скобкой одного и того же типа.
- Открытые скобки закрываются в правильном порядке.
- Каждой закрывающей скобке соответствует открытая скобка того же типа.

В результате надо вывести true, если s — допустимая строка, и false в противном случае.

Пример 1:
Input: s = "([{}])"
Output: true

Пример 2:
Input: s = "[(])"
Output: false

Покупка и продажа крипты

Проблема: Дан целочисленный массив цен, где prices[i] — цена AlgoCoin на i-й день. Можно выбрать один день для покупки одного AlgoCoin и выбрать другой день в будущем для его продажи.

В результате надо вывести максимальную прибыль, которую можно получить. Кроме того, есть возможность отказаться от совершения каких-либо транзакций, и в этом случае прибыль будет равна 0.

Пример 1:
Input: prices = [10,1,5,6,7,1]
Output: 6
Пояснение: купить за prices[1] и продать по prices[4]. В итоге, прибыль = 7 – 1 = 6.

Пример 2:
Input: prices = [10,8,7,5,2]
Output: 0
Пояснение: Невозможно совершить прибыльные сделки, поэтому максимальная прибыль равна 0.

Улавливание дождевой воды

Проблема: Дан массив высот неотрицательных целых чисел, которые представляют карту высот. Каждое значение heights[i] представляет высоту полосы, ширина которой равна 1.

В результате должно вернуться максимальная площадь воды, которая может задерживаться между решетками.

Контейнер для воды

Проблема: Дан целочисленный массив heights, где heights[i] представляет высоту i-ой колонки.

Можно выбрать любые две колонки, чтобы сформировать контейнер. В результате должно вернуться максимальное количество воды, которое может хранить контейнер.

function maxArea(heights) {
    left = 0
    right = length(heights) - 1
    max_area = 0

    while left < right {
        height = min(heights[left], heights[right])
        width = right - left
        current_area = height * width
        max_area = max(max_area, current_area)

        if heights[left] < heights[right] { 
            left += 1 
        }
        else { right -= 1 }
    }
    return max_area
}

👨‍💻 Потренируйтесь проходить собеседования с разработчиками из Яндекса, VK, Ozon, Тинькофф и других ведущих компаний, а также получите подробный отзыв о том, на какую зарплату и грейд вы можете расчитывать, или над чем вам еще стоит поработать.

Потренироваться проходить собеседования

Сумма трёх целых чисел

Проблема: Дан целочисленный массив nums. Необходимо реализовать алгоритм, который вернет все тройки [nums[i], nums[j], nums[k]], где nums[i] + nums[j] + nums[k] == 0, и индексы i, j и k различны.

Вывод не должен содержать повторяющихся троек. Можно вернуть результат и тройки в любом порядке.

Пример 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Объяснение:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

Пример 2:
Input: nums = [0,0,0]
Output: [[0,0,0]]

⁉️ Хотите усовершенствовать навыки программирования, прокачать алгоритмическое мышление и претендовать на более интересные вакансии?

Добро пожаловать на курс «Алгоритмы и структуры данных»!

- сможете повысить производительность программ и улучшить качество кода
- приобретёте опыт реализации классических алгоритмов
- поймёте, как создавать собственные алгоритмы для решения бизнес-задач

👨‍💻🛠👨🏻‍💻 Курс для бэкенд- и фронтенд-разработчиков, а также для начинающих программистов (на любом языке программирования).

Обучайтесь у экспертов из ведущих компаний, решайте задачи из практики и подтвердите повышение квалификации
в выпускном проекте.

🗓Курс стартует 30 октября
➡️ Чтобы начать обучение, пройдите вступительный тест

🔴 Записаться на курс «Алгоритмы и структуры данных»: https://otus.pw/nTy5/

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

Самая длинная последовательность

Проблема: Дан массив целых чисел nums. Необходимо реализовать алгоритм, который вернет длину самой длинной последовательности элементов.

Самая длинная последовательность — это последовательность элементов, в которой каждый элемент ровно на 1 больше предыдущего элемента.

Пример 1:
Input: nums = [2,20,4,10,3,4,5]
Output: 4

Пример 2:
Input: nums = [0,3,2,5,4,6,1,1]
Output: 7

Хотите узнать, как реализовать идеальную хэш-таблицу, которая работает за О(L) время?

Ждем вас на открытом вебинаре 21 октября в 20:00 мск, где мы разберем:

- как создать алгоритм ассоциативного массива на основе идеальной хэш-таблицы;
- как исключить коллизии с помощью двухступенчатой хэш-таблицы;
- как выполнить визуальное тестирование с англо-русским словарем на 2.000 слов.

👨‍💻🛠👨🏻‍💻 Урок для Junior-разработчиков на любых языках программирования.

🚀 Спикер Евгений Волосатов — программист баз данных и преподаватель с огромным и разнообразным опытом, автор статей и учебных программ по C#, Java, PHP.

🆓 Встречаемся в преддверии старта курса «Алгоритмы и структуры данных». Все участники вебинара получат специальную цену на обучение!

🔴 Регистрируйтесь прямо сейчас, чтобы не пропустить мероприятие: https://otus.pw/8X3Xe/

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

Произведения всех элементов массива, кроме текущего

Проблема: Дан целочисленный массив nums. Необходимо реализовать алгоритм, который вернет массив, где iый элемент является произведением всех элементов nums, кроме nums[i] (каждое произведение гарантированно умещается в 32-битное целое число).

Для решения задачи без использования операции деления и за O(n) времени, можно использовать метод предварительного вычисления произведений. Идея заключается в том, чтобы использовать два прохода по массиву: один для вычисления произведений слева от текущего элемента и другой для вычисления произведений справа от текущего элемента.

Пример:
Input: nums = [-1,0,1,2,3]
Output: [0,-6,0,0,0]

"K" элементов в списке

Проблема: Дан целочисленный массив nums и целое число k. Необходимо реализовать алгоритм, который вернет k наиболее часто встречающихся элементов массива. Можно вернуть вывод в любом порядке.

Пример 1:
Input: nums = [1,2,2,3,3,3], k = 2
Output: [2,3]

Пример 2:
Input: nums = [7,7], k = 1
Output: [7]

Хотите узнать, как превратить массив в пирамиду и ускорить сортировку данных?

Ждем вас на бесплатном вебинаре 14 октября в 20:00 мск, где мы разберем:

- как реализовать алгоритм сортировки выбором с линейной сложностью;
- как превратить массив в пирамиду (кучу) для быстрого доступа к максимальному элементу;
- как создать алгоритм пирамидальной сортировки с квазилинейной сложностью — О(N log N);
- визуальные примеры работы алгоритма на конкретных числах.

🚀 Спикер Евгений Волосатов — программист баз данных и преподаватель с огромным и разнообразным опытом, автор статей и учебных программ по C#, Java, PHP.

Встречаемся в преддверии старта курса «Алгоритмы и структуры данных». Все участники вебинара получат специальную цену на обучение!

Регистрируйтесь прямо сейчас, чтобы не пропустить мероприятие: https://otus.pw/JPJs/

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

Группы анаграмм

Проблема: Дан массив строк strs. Необходимо реализовать алгоритм, который сгруппирует все анаграммы в подгруппы. Можно вернуть вывод в любом порядке.

Анаграмма — это строка, содержащая те же символы, что и другая строка, но порядок символов может быть другим.

Пример 1:
Input: strs = ["act","pots","tops","cat","stop","hat"]
Output: [["hat"],["act", "cat"],["stop", "pots", "tops"]]

Пример 2:
Input: strs = ["x"]
Output: [["x"]]

Два целых числа

Проблема: Дан массив целых чисел nums и целочисленный target. Необходимо реализовать алгоритм, который вернет индексы i и j такие, что nums[i] + nums[j] == target и i != j. Можно предположить, что каждый input имеет ровно одну пару индексов i и j, удовлетворяющих условию. Сначала верните ответ с меньшим индексом.

Пример 1:
Input: nums = [3,4,5,6], target = 7
Output: [0,1]


Пример 2:
Input: nums = [-3,4,3,90], target=0
Output: [0,2]

Анаграмма

Проблема: Даны две строки s и t. Необходимо реализовать алгоритм, который возвращает true, если эти две строки являются анаграммами друг друга, в противном случае верните false.

Анаграмма — это строка, содержащая те же символы, что и другая строка, но порядок символов может быть другим.

Пример 1:
Input: s = "racecar", t = "carrace"
Output: true

Пример 2:
Input: s = "jar", t = "jam"
Output: false

Повторяющееся целое число

Проблема: Дан целочисленный массив array. Необходимо реализовать алгоритм, который возвращает true, если какое-либо значение встречается в массиве более одного раза, в противном случае возвращается false.

Пример 1:
Input: nums = [1, 2, 3, 3]
Output: true

Пример 2:
Input: nums = [1, 2, 3, 4]
Output: false

Вычисление лексикографически следующей битовой перестановки

Дано число v, представляющее собой текущее расположение битов, и необходимо вычислить следующую лексикографическую перестановку битов с заданным количеством единиц.

Например, если задано 3 бита и текущее расположение битов:
00010011,
то следующими будут:
00010101,
00010110,
00011001,
00011010,
00011100,
00100011 и так далее.

*Функция __builtin_ctz(v) компилятора GNU C для процессоров x86 возвращает количество замыкающих нулей. Для компиляторов Microsoft для x86 используется intrinsic _BitScanForward. Обе функции генерируют инструкцию bsf, но могут быть доступны эквиваленты для других архитектур. Если их нет, можно использовать один из методов подсчета подряд идущих нулевых битов.

Подсчет количества байтов между m и n

Макрос countbetween предназначен для подсчета количества байтов в слове x, которые находятся в диапазоне m < значение < n. Он использует макрос hasbetween, чтобы сначала найти все байты, которые удовлетворяют этому условию, а затем подсчитывает их количество.

Точное определение нахождения байта со значением между m и n

Этот макрос использует побитовые и арифметические операции для проверки, содержит ли слово x байт со значением между m и n. hasbetween дает точный результат, но использует больше операций для достижения этого по сравнению с макросом likelyhasbetween.

Определение, содержит ли слово байт со значением между m и n

Когда m < n, следующая техника позволяет проверить, содержит ли слово x байт со значением, таким образом, что m < значение < n. Эта техника использует 7 арифметических/логических операций, если n и m являются константами.

Однако, иногда может давать ложные срабатывания (false positives), т.е. оно может сообщить, что значение находится в диапазоне, когда это не так.

Подсчет количества байтов, больше заданного значения

Для подсчета количества байтов в x, значение которых больше n, можно использовать макрос countmore, который использует 6 операций.

Определение наличия байта, больше заданного значения, в 32-битном слове

Для проверки, содержит ли слово x байт со значением, превышающим n, можно использовать макрос hasmore. Он использует всего 3 арифметических/логических операции, если n является константой.

Предполагается, что x ≥ 0 и 0 ≤ n ≤ 127.

Подсчет количества байтов, меньше заданного значения

Макрос countless предназначен для подсчета количества байтов в 32-битном слове, значение которых меньше заданного числа n. Этот макрос выполняет задачу с использованием 7 арифметических и логических операций. Он позволяет эффективно обрабатывать данные, минимизируя количество операций и, следовательно, увеличивая производительность.

Определение наличия байта, меньше заданного значения, в 32-битном слове

Этот метод проверяет, содержит ли 32-битное слово байт с значением, которое меньше заданного числа n, используя всего 4 операции. Он эффективен и быстро выполняет задачу путем вычитания маскированного значения, инвертирования исходного слова и маскирования старших битов.

Определение наличия байта с определенным значением в 32-битном слове

Иногда возникает необходимость проверить, содержит ли любое 8-битное значение в 32-битном слове определенное значение. Для этого можно использовать операцию XOR, чтобы проверить совпадение каждого байта с искомым значением, и затем определить, содержит ли результат нулевой байт.

Определение наличия нулевого байта в 32-битном слове

Определение наличия нулевого байта является важной задачей при работе с данными и строками. Эффективные методы для выполнения этой проверки могут значительно улучшить производительность программ. Один из таких методов использует побитовые операции для минимизации числа операций и повышения скорости.

Оптимизированный метод определения наличия нулевого байта в 32-битном слове

Определение наличия нулевого байта в 32-битном слове — важная задача, которая часто встречается при обработке строк и других данных.

Преимущества метода
- Эффективность: Метод использует всего 4 операции, что делает его чрезвычайно быстрым.
- Компактность: Код прост и легко интегрируется в любые программы.
- Надежность: Метод точно определяет наличие нулевого байта, минимизируя количество ложных срабатываний.