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

Проблема: Дан массив целых чисел, где температура[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]

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

Проблема: Дан массив целых чисел 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
}

Поиск в 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

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

Проблема: Дан целочисленный массив 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

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

Проблема: Дан массив длины 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

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

Проблема: Дан массив длины 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

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

Проблема: Даны два целочисленных массива 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

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

Проблема: Дан массив целых чисел 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

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

Проблема: Дан массив целых чисел, где 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

SVM с линейным ядром

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

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

Опорные векторы - это точки, которые находятся на границе зазора между классами и которые непосредственно влияют на положение гиперплоскости.

Зазор (margin) - это расстояние между гиперплоскостью и ближайшими точками каждого класса. Задача SVM заключается в максимизации этого зазора.

Есть два типа зазора:
1. Классификация с жёстким зазором (hard margin), когда все обучающие образцы должны быть правильно классифицированы и находиться за пределами полосы разделения.
2. Классификация с мягким зазором (soft margin), когда вводится допущение, что некоторые обучающие образцы могут нарушать условие правильной классификации или попадать в полосу разделения

SVM с полиномиальным ядром

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

Влияние гиперпараметров
- Степень полинома d: Чем выше степень, тем более сложной становится граница между классами. При высоких значениях степень модели может стать излишне сложной и переобучиться.
- 𝛾: Этот параметр регулирует влияние отдельных признаков. Если γ слишком велико, модель может плохо обобщаться на новых данных.
- c0: Этот параметр смещает границу принятия решения, добавляя гибкость при нахождении разделяющей гиперплоскости.

Когда использовать полиномиальное ядро:
1. Данные содержат признаки, которые имеют полиномиальные зависимости.
2. Линейное ядро не может адекватно разделить классы.
3. Модель требует нелинейной границы, но с более низким уровнем сложности, чем при использовании RBF-ядра.

SVM с RBF ядром

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

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

Когда использовать RBF ядро:
1. Линейные модели или полиномиальные ядра не дают хороших результатов, так как границы между классами слишком сложны.
2. Требуется максимальная гибкость в создании нелинейных границ между классами.
3. Данные имеют высокую сложность, и полиномиальные ядра не могут точно разделить классы.

Алгоритм k-ближайших соседей

k-Nearest Neighbors (k-NN) — это метод машинного обучения, основанный на принципе нахождения k ближайших точек данных (соседей) в пространстве признаков, которые наиболее близки к новой точке, и на их основе делается предсказание.

Алгоритм k-NN не строит модели и не использует обучение в привычном смысле. Вместо этого он просто сохраняет все тренировочные данные и использует их для предсказаний.

k — это количество ближайших соседей, на основе которых алгоритм делает предсказание для новой точки данных. Это ключевой гиперпараметр модели.

Для того чтобы найти ближайших соседей новой точки, алгоритм использует метрики расстояния, такие как: Евклидово расстояние, Манхэттенское расстояние и другие, например, косинусное расстояние или Минковского.

Найдя расстояние до всех точек в тренировочных данных, алгоритм выбирает 𝑘 ближайших соседей.

Метод случайного леса

Случайный лес (Random Forest) — это ансамблевый метод машинного обучения, который строит несколько деревьев решений и объединяет их предсказания для получения более точного результата.

В основе метода лежит идея бэггинга (Bootstrap Aggregating), где каждое дерево обучается на случайной подвыборке данных с возвращением. Кроме того, случайный лес вносит дополнительную случайность, выбирая случайное подмножество признаков при каждом разбиении узла дерева.

Основные преимущества случайного леса:
- Снижение переобучения: Путем комбинирования предсказаний нескольких деревьев модель становится более устойчивой к переобучению.
- Работа с большими наборами данных: Модель эффективно справляется с высокоразмерными данными и может обрабатывать как числовые, так и категориальные признаки.
- Устойчивость к шуму и выбросам: Случайные леса более устойчивы к аномалиям и выбросам по сравнению с одиночными деревьями решений.