Dota2 Senate

Данная задача относится к моему «любимому» типу — попробуй пойми что от тебя хотят.

Первая сложность задачи не в поиске самого решения, а в попытках сократить контекст и описания с половины экрана до нескольких строчек, убирая весь лор про Dota2, сенаторов и регламенты проведения голосований.
Безусловно, в реальных условиях так часто и бывает — вам приносят бизнес задачу/проблему, которую вы должны решить, а не готовое ТЗ, где все структурировано расписано на понятном вам языке. Но для задач на собеседовании это перебор. Время сильно ограничено, вы стрессуете и вместо того, чтобы думать над задачей - пытаетесь продраться через витиеватое описание.

Сложность: 🟡 Средняя

ℹ️ Описание

В мире Dota2 существует 2 партии Radiant и Dire.
Для того чтобы внести изменение в игру Dota2 необходимо провести голосование сената, каждый член которого принадлежит одной из двух партий.

Голосование идет раундами, в каждом раунде по очереди опрашивается каждый сенатор.
Сенатор может выполнить одно из двух действий:
- лишить следующего сенатора из противоположной партии права голоса;
- объявить победу своей партии, если не осталось сенаторов с правом голоса из противоположной партии.
Раунд начинается с крайнего левого сенатора.

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

⚠️ Ограничения

- Количество сенаторов (длина входящей строки) находится в диапазоне от 1 до 10000
- Входящая строка состоит из символов R и D


1️⃣ Пример

Входящие данные

RD

Ответ

Radiant

2️⃣ Пример

Входящие данные

RDD

Ответ

Dire

✅ Решение

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

Правильный подход для решения этой задачи — воспользоваться структурой данных «очередь», поместив в нее сенаторов в заданом порядке.
Тогда весь процесс сведется к двум действиям:
- Забрать из начала очереди сенатора, а после того как тот совершит ход (лешит права голоса ближайшего сенатора из противоположной партии), помещать его в конец очереди.
- Удалить из очереди сенаторов без права голоса.

Итоговый ответ мы получим, когда в очереди останутся представители только одной партии.

Посмотреть реализацию и подробный разбор примера в блоге

🅾️ Оценка сложности

По времени

O(n) — так как нам придется несколько раз проитерироваться по очереди.

По памяти

O(n) — так как мы выделяем память для работы с очередью.

#queue #medium

Самый низкий общий предок двоичного дерева

Сложность: 🟡 Средняя

ℹ️ Описание

Вам дано двоичное дерево. Найдите наименьшего общего предка (LCA) двух заданных узлов в дереве.

Согласно определению LCA в Википедии: «Наименьший общий предок определяется между двумя узлами p и q как самый нижний узел в дереве T, который имеет как p, так и q в качестве потомков (где мы позволяем узлу быть потомком самого себя).»

⚠️ Ограничения

— Количество узлов в дереве находится в диапазоне от 2 до 10^5.
— Значения каждого узла в дереве находятся в диапазоне от -10^9 до 10^9.
— Значения всех узлов в дереве уникальны.
— p != q.
— p и q всегда существуют в дереве.


1️⃣ Пример

Входные параметры: дерево выше, p = 5, q = 1.

Ответ: 3

Объяснение: LCA узлов 5 и 1 равен 3.

2️⃣ Пример

Входные параметры: дерево выше, p = 5, q = 4.

Ответ: 5

Объяснение: LCA узлов 5 и 4 равен 5, поскольку узел может быть потомком самого себя согласно определению LCA.


✅ Решение

Решение этой задачи достаточно интуитивно. Сначала мы пройдем по дереву вглубь. В тот момент, когда встретится любой из узлов p или q, вернем логический флаг. Флаг помогает определить, нашли ли мы нужные узлы на каком-либо из путей. Тогда наименьшим общим предком будет узел, для которого обе рекурсии поддерева возвращают флаг true. Это также может быть узел, который сам является одним из узлов p или q и для которого одна из рекурсий поддерева возвращает флаг true.

Для реализации будем использовать рекурсивный подход с замыканием для хранения переменной lca.

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

O(n) — так как в худшем случае нам нужно посетить все n узлов в дереве.

По памяти

O(n) — так как максимальный объем пространства, используемого стеком рекурсии, будет равен n.

#tries #medium

Угадай число

Сегодня мы рассмотрим вместе с вами еще одну классическую задачу из учебников.

Сложность: 🟢 Легкая

ℹ️ Описание

Мы играем в игру, где вы должны угадать загаданное число.
Игра заключается в следующем.

— Я выбираю число от 1 до n.
— Вы должны угадать, какое число я выбрал.
— Каждый раз, когда вы угадаете неправильно, я скажу вам, больше или меньше выбранное мной число, чем ваше предположение.

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

int guess(int num)

Метод возвращает следующие результаты:

— -1 если ваша догадка больше, чем выбранное мной число;
— 1 если ваша догадка меньше выбранного мной числа;
— 0 если ваша догадка равна выбранному мною числу.

Угадайте число, которое я загадал.

⚠️ Ограничения

Загадываемое число всегда находится в диапазоне от 1 до 2^31 - 1

1️⃣ Пример

Исходные данные: n = 10, загадано число 6

Ответ: 6

2️⃣ Пример

Исходные данные: n = 1, загадано число 1

Ответ: 1

3️⃣ Пример

Исходные данные: n = 2, загадано число 1

Ответ: 1

✅ Решение

Это классическая задача, которая решается при помощи бинарного поиска.

Нам нужно итеративно выполнять несколько шагов.

1. Найти крайнюю левую и правую границы интервала, то есть 1 и n соответственно.
2. Найти середину этого интервала и проверить полученное число:
— если полученное число больше загаданного, то правую границу нужно сместить на mid - 1;
— если полученное число меньше загаданного, то левую границу нужно сместить на mid + 1;
— если полученное число равно загаданному, то мы нашли ответ.

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

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

O(log n) так как мы перебираем диапазон чисел бинарным поиском.

По памяти

0(1) так как мы не выделяем дополнительной памяти.

#binary_search

Количество последних вызовов

Сложность: 🟢 Легкая

ℹ️ Описание

Вам дан класс RecentCounter, который подсчитывает количество последних вызовов за определенный период времени. Реализуйте этот класс.

Конструктор RecentCounter инициализирует счетчик с нулевым количеством последних вызовов.
Класс имеет метод ping, который принимает в качестве аргумента параметр t (время в миллисекундах последнего вызова) и в качестве ответа возвращает количество вызовов, произошедших за последние 3000 мс.

Гарантируется, что каждый вызов ping использует строго большее значение t, чем предыдущий вызов.

⚠️ Ограничения

— Значение t находится в диапазоне от 1 до 10^9
— Каждый пример будет вызывать ping со строго возрастающими значениями t
— Для проверки будет совершено не более 10^4 вызовов метода ping

1️⃣ Пример

```golang



counter := Constructor()

counter.Ping(1)
counter.Ping(100)
counter.Ping(3001)
counter.Ping(3002)
counter.Ping(3003)
```

Ответ: 4

Пояснение: За последние 3000 мс было сделано 4 вызова в следующее время [100, 3001, 3002, 3003].

2️⃣ Пример

counter := Constructor()

counter.Ping(1)
counter.Ping(100)
counter.Ping(3001)

Ответ: 3

Пояснение: За последние 3000 мс было сделано 4 вызова в следующее время [1, 100, 3001].

✅ Решение

Эта задача решается буквально в несколько строчек.

Для хранения вызовов определим массив calls внутри класса, который при инициализации экземпляра получает значение пустого массива.

Далее в реализации метода ping сначала надо добавить время нового вызова в массив calls, а потом удалить из начала все элементы, которые вываливаются из интервала в 3000 миллисекунд, тем самым реализовав простую очередь. В конце нужно лишь вернуть длину оставшегося массива.

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

Основная временная сложность нашего метода ping заключается в цикле, который в худшем случае будет выполнять 3000 итераций для извлечения всех устаревших элементов, а в лучшем случае — одну итерацию. Исходя из этого сложность равна O(3000) = O(1).

По памяти

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

#queue #easy

Максимальный зигзагообразный путь в бинарном дереве

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

Сложность: 🟡 Средняя

ℹ️ Описание

Напишите функцию, которая будет вычислять длину самого длинного зигзагообразного пути в бинарном дереве. Путь может начинаться НЕ с корневого элемента дерева.

⚠️ Ограничения

Количество элементов в дереве от 1 до 50000


✅ Решение

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

- Длиной пути, начинающегося от текущего элемента направо.
- Длиной пути, начинающегося от текущего элемента налево.
- Длиной максимального пути «снизу» с левой дочерней ноды.
- Длиной максимального пути «снизу» с правой дочерней ноды.

Поднимаясь по слоям дерева во время рекурсивного обхода нам будет достаточно вычислять и возвращать максимум из этих величин.

Посмотреть примеры и реализацию в блоге

🅾️ Оценка сложности

По времени

O(n) —так как нам нужно совершить поиск в глубину по бинарному дереву, перебрав все n его элементов.

По памяти

O(n) — так как мы используем рекурсивный подход. Это означает, что мы будем хранить в памяти n переменных во время вычисления стека рекурсии.

#tries #medium

Переместите нули

Сложность: 🟢 Легкая

ℹ️ Описание

Вам дан целочисленный массив nums. Переместите в нём все нули в конец, сохраняя относительный порядок ненулевых элементов.

Обратите внимание, что вы должны сделать это in-place, не копируя массив.

⚠️ Ограничения

— Длина массива от 1 до 10000 элементов
— Каждый элемент массива может принимать значение в диапазоне от -2^31 до 2^31 - 1

1️⃣ Пример

Входные данные:

nums = [0,1,0,3,12]

Ответ

[1,3,12,0,0]

2️⃣ Пример

Входные данные:

nums = [0]

Ответ

[0]

✅ Решение

Решение задачи крайне простое.

Нам нужно завести два индекса. Первый — обычный индекс i, который инкриминируется на каждой итерации. Второй firstZeroIndex — индекс первого нулевого элемента в массиве, который изначально равен 0.

Далее мы итерируемся по всем элементам массива и, как только встречаем ненулевой элемент, меняем его местами с нулем, который стоит под индексом firstZeroIndex. Дополнительно увеличиваем firstZeroIndex, если произошла перестановка.

Таким образом все нули будут «всплывать» в конец массива за один проход..

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

Сложность O(n), так как мы итерируемся по всем элементам массива.

По памяти

Сложность O(1), так как мы не выделяем дополнительную память, зависящую от длины массива.

#arrays #easy

Дети с наибольшим количеством конфет

Сложность: 🟢 Легкая

ℹ️ Описание

Есть n детей с конфетами.

Вам дан целочисленный массив candies, где candies[i] представляет количество конфет, которые есть у i-го ребенка, и целое число extraCandies, обозначающее количество дополнительных конфет, которые у вас есть.

Верните массив result длины n, где result[i] имеет значение true, если после предоставления i-му ребенку всех дополнительных конфет у него будет наибольшее количество конфет среди всех детей, или false в противном случае.

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

⚠️ Ограничения

— Длина массива candies находится в диапазоне от 1 до 100
— У каждого ребенка может быть не менее 1 и не более 100 конфет
— Значение extraCandies находится в диапазоне от 1 до 50

1️⃣ Пример

Входные данные:

candies = [2,3,5,1,3]
extraCandies = 3

Ответ

[true,true,true,false,true]

2️⃣ Пример

Входные данные:

candies = [4,2,1,1,2]
extraCandies = 1

Ответ

[true,false,false,false,false]

✅ Решение

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

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

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

По памяти

Сложность по памяти линейная O(n), так как мы создаем массив длиной n для хранения ответа.

#arrays #easy

Определите, близки ли две строки

Сложность: 🟡 Средняя

ℹ️ Описание

Вам дано две строки. Верните true, если обе строки являются близкими, и false в противном случае.

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

Операция 1: Поменяйте местами любые два существующих символа (swap). Например, abcde -> aecdb (букву b поменяли местами с буквой e).

Операция 2: Преобразуйте каждое появление одного существующего символа в другой существующий символ и сделайте то же самое с другим символом. Например, aacabb -> bbcbaa (все буквы a превращаются в буквы b, а все буквы b превращаются в буквы a).

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

⚠️ Ограничения

— Длина каждого слова находится в диапазоне от 1 до 10^5
— Оба слова содержат только строчные буквы латинского алфавита

1️⃣ Пример

Входные данные: word1 = "abc", word2 = "bca"

Ответ: true

Объяснение

Вы можете получить word1 из word2 за 2 операции.

Примените операцию 1: «abc» -> «acb»
Примените операцию 1: «acb» -> «bca»

2️⃣ Пример

Входные данные: word1 = "a", word2 = "aa"

Ответ: false

Объяснение

Невозможно получить word2 из word1 или наоборот за любое количество операций.

3️⃣ Пример

Входные данные: word1 = "cabbba", word2 = "abbccc"

Ответ: true

Объяснение

Вы можете получить word1 из `word2 за 3 операции.

Примените операцию 1: «cabbba» -> «caabbb»
Примените операцию 2: «caabbb» -> «baaccc»
Примените операцию 2: «baaccc» -> «abbccc»

✅ Решение

Посмотреть решение в блоге

#strings #medium

Разворот связанного списка

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

Сложность: 🟢 Легкая

ℹ️ Описание

Вам дан односвязный список. Переверните список и верните его.

Список представлен следующей структурой.

class ListNode {
    val: number
    next: ListNode | null
}

⚠️ Ограничения

— Количество узлов в связанном списке находится в диапазоне от 1 до 5000
— Значение каждого узла находится в диапазоне от -5000 до 5000

✅ Решение

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

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

Сложность O(n), так как мы итерируемся по всем узлам списка.

По памяти

Сложность O(1), так как мы не выделяем дополнительную память.

#linked_list #easy

Является ли строка подпоследовательностью

Сложность: 🟢 Легкая

ℹ️ Описание

Дано две строки s и t. Напишите функцию, которая возвращает true, если s является подпоследовательностью t, или false в противном случае.

Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (может быть ни одного) символов без нарушения относительного положения остальных символов. (т. е. «ace» является подпоследовательностью abcde, а «aec» — нет).

⚠️ Ограничения

— Длина строки s находится в диапазоне от 0 до 100
— Длина строки t находится в диапазоне от 0 до 10000
— В строках могут присутствовать только латинские буквы в нижнем регистре

1️⃣ Пример

Входные данные

s = "abc"
t = "ahbgdc"

Ответ

true

2️⃣ Пример

Входные данные

s = "axc"
t = "ahbgdc"

Ответ

false

✅ Решение

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

Мы запускаем цикл по всем символам строки t и сравниваем их с символами строки s. Для отслеживания позиции в строке s мы будем использовать указатель pos.

- Если символы совпадают, мы двигаем указатель строки pos на одну позицию вперед.
- Если после прохода по всем символам строки t указатель pos указывает на конец строки s, значит строка s является подпоследовательностью строки t.
- Если во время очередной итерации выполняется это же условие, то мы моем досрочно завершить выполнение функции и вернуть true, так как дальнейший проход по строке t не имеет смысла.

Посмотреть реализацию в блоге

#strings #easy

Привет, друзья. Простите нас за молчание, просто админы ушли в отпуск 😄

Через неделю мы вернемся к вам с новыми задачами, а пока что вы можете следить за нашими приключениями в Намибии в этом канале.

Сжатие строки

Как и обещали, возвращаемся к вам с отпуска с новыми силами. Сегодня хочется разобрать одну из очень популярных и классических задач с собеседований - пишем свой простенький архиватор 🙂

Сложность: 🟡 Средняя

ℹ️ Описание

Дана строка в виде массива символов. Необходимо написать функцию, которая сожмет входящий массив и вернет количество символов в сжатом массиве по следующему принципу:
— Если символ повторяется больше одного раза подряд, нужно заменить всю подстроку на строку ['a', 'n'], где a - исходный символ, n - количество повторений этого символа, идущих подряд. В случае если n — многозначное число, каждая цифра должна быть добавлена отдельным символом.
— Если буква не повторяется - оставить ее без изменений.

Все изменения нужно совершить in-place, в качестве ответа функции вернуть количество символов в сжатой строке.

⚠️ Ограничения

— Длина входящего массива от 1 до 2000 символов
— Элементы массива - символы латиницы, цифры или знаки

1️⃣ Пример

Входные данные

chars = ["a","a","b","b","c","c","c"]

Ответ

6

Исходный массив должен быть преобразован в

chars = ["a","2","b","2","c","3"]

2️⃣ Пример

Входные данные

chars = ["a"]

Ответ

1

3️⃣ Пример

Входные данные

chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Ответ

4

Исходный массив должен быть преобразован в

chars = ["a","b","1","2"]

✅ Решение

Задача решается достаточно элементарно, главная загвоздка - замена элементов in-place.

Для решение задачи нам понадобятся несколько индексов:
— Индекс текущего элемента lastElemIdx
— Индекс начала последовательности одинаковых элементов firstElemIdx
— Индекс элемента, который будет заменен при сжатии строки newPositionIdx. Для эффективности решения мы будем заменять элементы исходного массива, а после «отрежем» хвост. В противном случае нам бы пришлось вырезать повторяющиеся символы, смещая хвост массива на n элементов влево, что значительно замедлит алгоритм.

Далее нам достаточно аккуратно обойти и модифицировать исходный массив.

Посмотреть реализацию в блоге

#arrays #medium

Максимальное количество пар K-суммы

Сложность: 🟡 Средняя

ℹ️ Описание

Вам дан целочисленный массив nums и целое число k.

За одну операцию вы можете выбрать из массива два числа, сумма которых равна k, и удалить их из массива.

Верните максимальное количество операций, которые вы можете выполнить с массивом.

⚠️ Ограничения

— Длина массива находится в диапазоне от 1 до 10^5
— Каждый элемент массива может принимать значение в диапазоне от 1 до 10^9
— k находится в диапазоне от 1 до 10^9

1️⃣ Пример

Входные данные

nums = [1,2,3,4], k = 5

Ответ: 2

Вы можете удалить две пары чисел: (1,4) и (2,3), сумма которых равна 5.

2️⃣ Пример

Входные данные

nums = [3,1,3,4,3], k = 6

Ответ: 1

Вы можете удалить одну пару чисел: (3,3), сумма которых равна 6.


✅ Решение

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

Запускаем цикл по всем элементам массива и для каждого числа рассчитываем разность diff между k и текущим числом num.

Если в объекте digits уже есть запись для diff, это означает, что ранее было найдено число, которое в сумме с текущим числом num даст k. Если это так, то уменьшаем количество доступных чисел diff на единицу, и счетчик пар res увеличивается на один, так как найдена новая пара.

Если же такого числа нет, то текущее число num добавляется в digits, увеличивая счетчик количества этого числа на единицу, чтобы в будущем его можно было использовать для создания пары с другим числом.

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

Посмотреть реализацию в блоге

#arrays #medium

Максимальное количество гласных в подстроке заданного размера

Сложность: 🟡 Средняя

ℹ️ Описание

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

⚠️ Ограничения

— Длина строки от 1 до 100000
— Строка состоит только из латинских букв в нижнем регистре
— Размер подстроки находится в диапазоне от 1 до длины исходной строки s.

1️⃣ Пример

Входные данные

s = "abciiidef"
k = 3

Ответ

3

В исходной строке есть подстрока длиной 3 состоящая исключительно из гласных iii.

2️⃣ Пример

Входные данные

s = "aeiou"
k = 2

Ответ

2

Так как исходная строка состоит полностью из гласных, любая подстрока длиной 2 также будет состоять из гласных.

3️⃣ Пример

Входные данные

s = "leetcode"
k = 3

Ответ

2

В исходной строке есть несколько подстрок (`lee`/`eet`/`ode`), в любой из которых максимальное количество гласных равно 2.

✅ Решение

Данная задача является ярким представителем класса задач, которые решаются с помощью скользящего окна:
- Нам необходимо создать окно длиной k (исходно левая граница окна равна 0, а правая - `k-1`)
- Двигать наше окно увеличивая левый и правый индекс на 1 на каждом шаге
- Считать сколько гласных попадает в наше окно на каждом шаге

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

Посмотреть реализацию в блоге

#strings #medium

Максимальный средний подмассив

Сложность: 🟢 Легкая

ℹ️ Описание

Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите непрерывный подмассив длиной k, имеющий максимальное среднее значение, и верните это значение.

Принимается любой ответ с ошибкой расчета менее 10^-5.

⚠️ Ограничения

— k гарантированно меньше или равно длине массива nums
— Количество элементов в массиве может быть в диапазоне от 1 до 10^5
— Каждый элемент массива может принимать значение в диапазоне от -10^4 до 10^4

1️⃣ Пример

Входные данные

nums = [1,12,-5,-6,50,3]
k = 4

Ответ

12.75

2️⃣ Пример

Входные данные

nums = [5]
k = 1

Ответ

5

✅ Решение

Для решения задачи мы будем использовать метод скользящего окна.

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

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

Таким образом, после завершения всех итераций по массиву, в переменной maxSum будет храниться максимальное значение суммы подмассива длиною k. В самом конце только остается поделить эту сумму на k таким образом получив среднее значение подмассива.

Посмотреть реализацию в блоге

#arrays #easy

Сколько нужно стрел, чтобы лопнуть все воздушные шары

Сложность: 🟡 Средняя

ℹ️ Описание

К плоской стене, представляющей плоскость XY, приклеено несколько сферических воздушных шаров. Шары представлены в виде двумерного целочисленного массива points, где points[i] = [xstart, xend] обозначает шар, горизонтальный диаметр которой простирается между xstart и xend. Вы не знаете точных координат Y воздушных шаров.

Вы можете выстрелить стрелой прямо вертикально (в положительном направлении Y) из разных точек вдоль оси X. Воздушный шар с xstart, xend разрывается стрелой, выпущенной в x, если x start <= x <= xend. Нет ограничений на количество выпущенных стрел.

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

⚠️ Ограничения

— В массиве points может быть от 1 до 105 элементов
— 2^31 <= xstart < xend <= 2^31 - 1

1️⃣ Пример

Входные данные

points = [[10,16],[2,8],[1,6],[7,12]]

Ответ: 2

Пояснение

— Выстрелите стрелой в точку x = 6, лопнув шарики [2, 8] и [1, 6].
— Выстрелите стрелой в точку x = 11, лопнув шарики [10, 16] и [7, 12].

2️⃣ Пример

Входные данные

points = [[1,2],[3,4],[5,6],[7,8]]

Ответ: 4

Пояснение

Для каждого воздушного шара нужно выпустить одну стрелу, всего получится 4 стрелы.

3️⃣ Пример

Входные данные

points = [[1,2],[2,3],[3,4],[4,5]]

Ответ: 2

Пояснение

— Выстрелите стрелой в точку x = 2, лопнув шарики [1, 2] и [2, 3].
— Выстрелите стрелой в точку x = 4, лопнув шарики [3, 4] и [4, 5].

✅ Решение

Для решения этой задачи первым делом надо отсортировать массив points по правой границе шаров. Такая сортировка поможет нам с легкостью определить, сколько стрел нужно выпустить, чтобы лопнуть все шары.

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

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

Исходя из этого мы можем сформировать крайне простой алгоритм:

— Итерируемся по всем шарам в отсортированном массиве.
— Запоминаем координату последнего выстрела, которую по умолчанию выставляем в минимально возможное значение.
— Если начальная координата текущего шара больше координаты последнего выстрела, то это означает, что нам нужен сделать выстрел по правой границе шара и увеличить счетчик выпущенных стрел на 1.
— Если начальная координата текущего шара меньше или равна координате последнего выстрела, то это означает, что шар пересекается с предыдущим и нам не нужно делать новый выстрел, потому что он уже был сбит предыдущей стрелой.

Посмотреть реализацию в блоге

#arrays #medium

Привет. Сегодня я бы хотел обсудить с вами один интересный вопрос, который не касается алгоритмов, но напрямую относится к работе.

Наткнулся в интернетах на жаркий тред, где обсуждают нормально ли писать сообщения по работе в нерабочее время.

В чем суть. Есть условно два стула.

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

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

Расскажите, что вы думаете по этому поводу? Какой вариант для вас более предпочтительный? Или может у вас есть другие идеи?

Стек наиболее часто встречающихся элементов

Всем привет!
Мы решили попробовать разбавить легкие и средние задачи — сложными 🙂
На самом деле эта задача лежала у меня в черновиках довольно долго. Настолько, что я успел несколько раз забыть как работает куча, а также за это время мы успели завести этот канал и несколько раз обновить блог (кстати, зацените новый формат. Кажется, стало немного симпатичнее).

Итак, задача по реализации модифицированного стека: который позволяет сперва доставать наиболее частотные элементы, а в случае наличия групп элементов с одинаковой частотой - работать как классический стек между этими группами.
На самом деле, наиболее приближенная задача из практических — Priority queue. Только в нашем случае вместо приоритетов — частоты, а вместо алгоритма FIFO - LIFO.

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

Сложность: 🤬 Сложная

ℹ️ Описание

Необходимо реализовать структуру данных, которая позволит сохранять и доставать целочисленные элементы. Для этого необходимо реализовать 3 функции:
1. Constructor() FreqStack конструктор, инициализирующий структуры данных.
2. FreqStack.Push(val int) метод структуры данных, позволяющий сохранить целочисленный элемент внутрь структуры данных FreqStack
3. FreqStack.Pop() int метод структуры данных, удаляющий и возвращающий элемент из структуры данных. Сперва извлекаются наиболее частотные элементы. При наличии групп эллементов, имеющих одинаковую частоту, извлекать элементы из групп с одинаковой частотой по принципу стека (LIFO)

⚠️ Ограничения

— Добавляемые/извлекаемые элементы лежат в диапазоне от 0 до 1 000 000 000
— Максимальное количество вызовов функций Push и Pop - 20 000
— Гарантируется, что перед вызовом функции Pop в FreqStack будет как минимум один элемент

1️⃣ Пример

stack := Constructor()

stack.Push(5)
stack.Push(7)
stack.Push(5)
stack.Push(7)
stack.Push(4)
stack.Push(5)

Out:

stack.Pop() // 5
stack.Pop() // 7
stack.Pop() // 5
stack.Pop() // 4

Пояснение

— Первым извлекается элемент 5, так как он самый частотный в стеке. При этом извлекается та 5, которая была добавлена последней (по принципу стека)
— Вторым извлекается элемент 7, так как в стеке оба элемента 5 и 7 встречаются по 2 раза, но последняя 7 была добавлена позже, чем последняя 5 (5, которую мы добавили последним Push'ом мы извлекли первым вызовом Pop)
— Третьим элементом извлекается элемент 5, так как теперь это самый частотный элемент в стеке
— Четвертым извлекается элемент 4, так как теперь в стеке все элементы имеют одинаковую частоту (каждый элемент встречается один раз), а элемент 4 был добавлен в стек последним


✅ Решение

Как я говорил ранее, для решения задачи нам придется вспомнить как работает куча. Так как куча по своей сути древовидная структура — мы можем реализовать ее через обычный массив.

Посмотреть реализацию и объяснения в блоге.

#heap #hard

Минимальное количество переворотов, чтобы сделать A | B == C

Привет, друзья.

Несмотря на выходный день, у нас вами разбор новой задачи. В этот раз рассматриваем тему битовых манипуляций.

Сложность: 🟡 Средняя

ℹ️ Описание

Даны три целых положительных числа a, b и c.

Необходимо найти минимальное количество переворотов битов в a и b, чтобы результат операции a OR b (побитовая операция ИЛИ) был равен c. Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или c 0 на 1 в его двоичном представлении.

⚠️ Ограничения

Значение каждого аргумента находится в диапазоне от 1 до 10^9

1️⃣ Пример

Входные данные: a = 2, b = 6, c = 5

Ответ: 3

2️⃣ Пример

Входные данные: a = 4, b = 2, c = 7

Ответ: 1

3️⃣ Пример

Входные данные: a = 1, b = 2, c = 3

Ответ: 0

✅ Решение

Чтобы решить задачу, нам необходимо представить числа a, b и c в двоичном виде и произвести их сравнение побитно. Недостающие биты в числах мы заполняем ведущими нулями.

Если бит числа c равен 1, это означает, что в a и b как минимум один бит на этой же позиции должен быть равен 1, чтобы условие a | b == c было истинным. Если же оба бита в a и b равны 0, то нам необходимо изменить любой из битов на единицу. Не важно какой именно бит, потому что это не меняет результат.

Если бит числа c равен 0, это означает, что биты и в числе a, и в числе b должны быть равны нулю, чтобы условие a | b == c было истинным. В этом случае нам нужно изменять биты в a и b только в том случае, если они равны 1.

❓ Как получить двоичное представление числа ❓

На самом деле число не нужно переводить в двоичную систему счисления. Достаточно воспользоваться небольшим математическим хаком.

- Чтобы получить младший бит числа в двоичном представлении (крайний справа) необходимо взять остаток от деления числа на 2. Это работает потому что у четных чисел младший бит всегда равен 0, а у нечетных — 1.

- Чтобы откинуть младший бит у числа достаточно разделить его на 2 без остатка. В таком случае мы получим новое число, которое в двоичном представлении равно предыдущему числу без младшего бита.

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

Посмотреть реализацию в блоге

#bit_manipulation #medium