Плюс один
Для решения сегодняшней задачи мы с вами вспомним школьную программу, а именно — как складывать числа столбиком.
Сложность: 🟢 Легкая
ℹ️ Описание
Дано большое целое число, представленное в виде целочисленного массива digits, где digits[i] — это i-я цифра целого числа. Цифры упорядочены от наиболее значимого к наименее значимому, слева направо. Число не содержит ведущих нулей.
Увеличьте число на единицу и верните полученный массив цифр.
⚠️ Ограничения
— В массиве цифр может быть от 1 до 100 элементов
— В массиве содержатся только цифры от 0 до 9
— Число не содержит ведущих нулей
1️⃣ Пример
Входящие данные
Ответ
2️⃣ Пример
Входящие данные
Ответ
3️⃣ Пример
Входящие данные
Ответ
✅ Решение
Чтобы решить задачу, нужно реализовать подход со сложением чисел в столбик.
Каждая цифра в массиве представляет собой один разряд числа. Сначала нужно прибавить к младшему разряду (крайнему справа) единицу согласно условиям задачи, а потом следовать простому алгоритму.
1. Если сумма меньше 10, то вместо текущего разряда нужно записать эту сумму.
2. Если сумма больше 10, то вместо текущего разряда нужно записать остаток от деления суммы на 10, а к следующему разряду прибавить единицу. Для всех последующих разрядов нужно повторить эти же действия.
3. Если мы обрабатываем старший разряд (крайний слева) и сумма больше 10, то в текущий разряд мы добавляем остаток от деления суммы на 10 и добавляем еще один разряд, в который записываем единицу.
Перебирать исходный массив будем справа налево, добавляя результат вычислений для каждого разряда в конец результирующего массива. В результате мы получим инвертированный массив, поэтому в конце остается только развернуть его относительно центра.
Посмотреть реализацию в блоге
🅾️ Оценка сложности
По времени
O(n) — так как мы дважды итерируемся по всему массиву.
По памяти
O(n) — так как мы выделяем память для хранения результирующего массива.
#arrays #easy #math
Для решения сегодняшней задачи мы с вами вспомним школьную программу, а именно — как складывать числа столбиком.
Сложность: 🟢 Легкая
ℹ️ Описание
Дано большое целое число, представленное в виде целочисленного массива digits, где digits[i] — это i-я цифра целого числа. Цифры упорядочены от наиболее значимого к наименее значимому, слева направо. Число не содержит ведущих нулей.
Увеличьте число на единицу и верните полученный массив цифр.
⚠️ Ограничения
— В массиве цифр может быть от 1 до 100 элементов
— В массиве содержатся только цифры от 0 до 9
— Число не содержит ведущих нулей
1️⃣ Пример
Входящие данные
Ответ
2️⃣ Пример
Входящие данные
Ответ
3️⃣ Пример
Входящие данные
Ответ
✅ Решение
Чтобы решить задачу, нужно реализовать подход со сложением чисел в столбик.
Каждая цифра в массиве представляет собой один разряд числа. Сначала нужно прибавить к младшему разряду (крайнему справа) единицу согласно условиям задачи, а потом следовать простому алгоритму.
1. Если сумма меньше 10, то вместо текущего разряда нужно записать эту сумму.
2. Если сумма больше 10, то вместо текущего разряда нужно записать остаток от деления суммы на 10, а к следующему разряду прибавить единицу. Для всех последующих разрядов нужно повторить эти же действия.
3. Если мы обрабатываем старший разряд (крайний слева) и сумма больше 10, то в текущий разряд мы добавляем остаток от деления суммы на 10 и добавляем еще один разряд, в который записываем единицу.
Перебирать исходный массив будем справа налево, добавляя результат вычислений для каждого разряда в конец результирующего массива. В результате мы получим инвертированный массив, поэтому в конце остается только развернуть его относительно центра.
Посмотреть реализацию в блоге
🅾️ Оценка сложности
По времени
O(n) — так как мы дважды итерируемся по всему массиву.
По памяти
O(n) — так как мы выделяем память для хранения результирующего массива.
#arrays #easy #math
👍4🔥4❤1
Разворот слов в строке
Подобные задачи чаще всего попадаются на собеседованиях — на первый взгляд задача кажется очень простой, особенно если воспользоваться встроенными функциями языка - trim, split и так далее - задача решается в несколько строчек кода.
Но, обычно, в таких задачах интервьеры просят НЕ использовать эти функции и реализовать все самим. И в этот момент частенько «зависаешь» на реализации.
Сложность: 🟡 Средняя
ℹ️ Описание
Необходимо написать функцию, которая будет переставлять слова в строке в обратном направлении. Слова в строке разделены пробелами, пробелов между слов может быть несколько, а также пробелы могут стоять в начале и конце исходной строки.
В итоговой строке слова должны быть разделены одним пробелом, а также не должно быть пробелов в начале и конце строки.
⚠️ Ограничения
— Длина строки может быть в диапазоне от 1 до 10000
— Строка содержит только буквы латинского алфавита, числа и пробелы.
— В каждой строке есть как минимум одно слово
1️⃣ Пример
Входящие данные
Ответ
2️⃣ Пример
Входящие данные
Ответ
3️⃣ Пример
Входящие данные
Ответ
✅ Решение
Данную задачу можно решить легким трюком: ответ мы получим, если избавимся от лишних пробелов, после перевернем каждое слово в строке и в конце перевернем полностью всю строку. Давайте рассмотрим задачу на примере
1. Удаляем лишние пробелы внутри строки и получаем строку
2. Далее переворачиваем каждое слово внутри строки и получаем строку
3. Последним шагом переворачиваем всю строку и получаем требуемый результат
Посмотреть реализацию в блоге
🅾️ Оценка сложности
По времени
O(n) — так как мы несколько раз итерируемся по всей строке.
По памяти
O(n) — так как мы выделяем память для работы с новой строкой.
#strings #medium
Подобные задачи чаще всего попадаются на собеседованиях — на первый взгляд задача кажется очень простой, особенно если воспользоваться встроенными функциями языка - trim, split и так далее - задача решается в несколько строчек кода.
Но, обычно, в таких задачах интервьеры просят НЕ использовать эти функции и реализовать все самим. И в этот момент частенько «зависаешь» на реализации.
Сложность: 🟡 Средняя
ℹ️ Описание
Необходимо написать функцию, которая будет переставлять слова в строке в обратном направлении. Слова в строке разделены пробелами, пробелов между слов может быть несколько, а также пробелы могут стоять в начале и конце исходной строки.
В итоговой строке слова должны быть разделены одним пробелом, а также не должно быть пробелов в начале и конце строки.
⚠️ Ограничения
— Длина строки может быть в диапазоне от 1 до 10000
— Строка содержит только буквы латинского алфавита, числа и пробелы.
— В каждой строке есть как минимум одно слово
1️⃣ Пример
Входящие данные
«the sky is blue»
Ответ
«blue is sky the»
2️⃣ Пример
Входящие данные
« hello world »
Ответ
«world hello»
3️⃣ Пример
Входящие данные
«a good example»
Ответ
«example good a»
✅ Решение
Данную задачу можно решить легким трюком: ответ мы получим, если избавимся от лишних пробелов, после перевернем каждое слово в строке и в конце перевернем полностью всю строку. Давайте рассмотрим задачу на примере
«a good example».
1. Удаляем лишние пробелы внутри строки и получаем строку
«a good example»
2. Далее переворачиваем каждое слово внутри строки и получаем строку
«a doog elpmaxe»
3. Последним шагом переворачиваем всю строку и получаем требуемый результат
«example good a»
Посмотреть реализацию в блоге
🅾️ Оценка сложности
По времени
O(n) — так как мы несколько раз итерируемся по всей строке.
По памяти
O(n) — так как мы выделяем память для работы с новой строкой.
#strings #medium
🔥5👍2👏1
Мы очень рады, что наши разборы задач интересны и полезны такому большому количеству людей.
Спасибо, что читаете нас!
Мы стараемся для вас ❤️
Please open Telegram to view this post
VIEW IN TELEGRAM
❤15🍾6🥰4👏1
Декодирование строки
Сложность: 🟡 Средняя
ℹ️ Описание
Вам дана закодированная строка, верните ее декодированную версию.
В строке используется следующее правило кодирования: k[encoded_string], означает что закодированная внутри квадратных скобок строка должна повторяться ровно k раз. Обратите внимание, что k гарантированно является положительным целым числом.
При этом входная строка всегда гарантированно валидная, то есть в ней нет лишних пробелов и квадратные скобки имеют правильную форму. Кроме того, цифры в строке предназначены только для повторяющихся чисел k. Например, не будет ввода типа 3a или 2[4].
Обратите внимание на то, что закодированные строки могут вкладываться друг в друга.
⚠️ Ограничения
— Длина входной строки находится в диапазоне от 1 до 30
— Входная строка содержит только латинские буквы в нижнем регистре, цифры и квадратные скобки
— Входная строка всегда валидная
— Значения k находятся в диапазоне от 1 до 300
— Длина результирующей строки не превышает 10^5
1️⃣ Пример
Входящие данные
Ответ
2️⃣ Пример
Входящие данные
Ответ
3️⃣ Пример
Входящие данные
Ответ
✅ Решение
Эту задачу можно решить рекурсивным способом. Для этого определим следующий алгоритм.
1. Создаем результирующую пустую строку, которая будет использоваться для накопления декодированного результата.
2. Далее перебираем строку посимвольно и проверяем следующие условия:
- Если текущий символ является буквой (от ‘a’ до ‘z’), добавляем его в результат res и переходим к следующему символу.
- Если встречается цифра, это означает начало закодированного блока. Число перед [ (количество повторений) считывается посимвольно. Так как k может быть многозначным числом, используется накопление count в цикле, где каждая новая цифра добавляется к count с учетом ее разрядности (умножение на 10).
3. После определения count и нахождения открывающей скобки [, алгоритм ищет соответствующую закрывающую скобку ]. Это делается с помощью счетчика bracket, который увеличивается при нахождении [ и уменьшается при нахождении ], позволяя обрабатывать вложенные скобки.
4. Как только найдена соответствующая закрывающая скобка, вырезается подстрока между [ и ] и для нее рекурсивно вызывается функция decodeString. Результат этого вызова повторяется count раз и добавляется к итоговому результату res.
5. Индекс i устанавливается на позицию закрывающей скобки, чтобы продолжить обход строки после обработанного блока.
Посмотреть реализацию в блоге
🅾️ Оценка сложности
По времени
O(maxk * n), где maxk — максимальное значение k, а n — длина данной строки s.
По памяти
O(n) — это пространство, используемое для хранения внутреннего стека вызовов для рекурсии. Поскольку мы рекурсивно декодируем каждый вложенный шаблон, максимальная глубина стека рекурсивных вызовов не будет превышать n.
#strings #medium
Сложность: 🟡 Средняя
ℹ️ Описание
Вам дана закодированная строка, верните ее декодированную версию.
В строке используется следующее правило кодирования: k[encoded_string], означает что закодированная внутри квадратных скобок строка должна повторяться ровно k раз. Обратите внимание, что k гарантированно является положительным целым числом.
При этом входная строка всегда гарантированно валидная, то есть в ней нет лишних пробелов и квадратные скобки имеют правильную форму. Кроме того, цифры в строке предназначены только для повторяющихся чисел k. Например, не будет ввода типа 3a или 2[4].
Обратите внимание на то, что закодированные строки могут вкладываться друг в друга.
⚠️ Ограничения
— Длина входной строки находится в диапазоне от 1 до 30
— Входная строка содержит только латинские буквы в нижнем регистре, цифры и квадратные скобки
— Входная строка всегда валидная
— Значения k находятся в диапазоне от 1 до 300
— Длина результирующей строки не превышает 10^5
1️⃣ Пример
Входящие данные
"3[a]2[bc]"
Ответ
"aaabcbc"
2️⃣ Пример
Входящие данные
"3[a2[c]]"
Ответ
"accaccacc"
3️⃣ Пример
Входящие данные
"2[abc]3[cd]ef"
Ответ
"abcabccdcdcdef"
✅ Решение
Эту задачу можно решить рекурсивным способом. Для этого определим следующий алгоритм.
1. Создаем результирующую пустую строку, которая будет использоваться для накопления декодированного результата.
2. Далее перебираем строку посимвольно и проверяем следующие условия:
- Если текущий символ является буквой (от ‘a’ до ‘z’), добавляем его в результат res и переходим к следующему символу.
- Если встречается цифра, это означает начало закодированного блока. Число перед [ (количество повторений) считывается посимвольно. Так как k может быть многозначным числом, используется накопление count в цикле, где каждая новая цифра добавляется к count с учетом ее разрядности (умножение на 10).
3. После определения count и нахождения открывающей скобки [, алгоритм ищет соответствующую закрывающую скобку ]. Это делается с помощью счетчика bracket, который увеличивается при нахождении [ и уменьшается при нахождении ], позволяя обрабатывать вложенные скобки.
4. Как только найдена соответствующая закрывающая скобка, вырезается подстрока между [ и ] и для нее рекурсивно вызывается функция decodeString. Результат этого вызова повторяется count раз и добавляется к итоговому результату res.
5. Индекс i устанавливается на позицию закрывающей скобки, чтобы продолжить обход строки после обработанного блока.
Посмотреть реализацию в блоге
🅾️ Оценка сложности
По времени
O(maxk * n), где maxk — максимальное значение k, а n — длина данной строки s.
По памяти
O(n) — это пространство, используемое для хранения внутреннего стека вызовов для рекурсии. Поскольку мы рекурсивно декодируем каждый вложенный шаблон, максимальная глубина стека рекурсивных вызовов не будет превышать n.
#strings #medium
👍6🔥2❤1🙏1
Dota2 Senate
Данная задача относится к моему «любимому» типу — попробуй пойми что от тебя хотят.
Первая сложность задачи не в поиске самого решения, а в попытках сократить контекст и описания с половины экрана до нескольких строчек, убирая весь лор про Dota2, сенаторов и регламенты проведения голосований.
Безусловно, в реальных условиях так часто и бывает — вам приносят бизнес задачу/проблему, которую вы должны решить, а не готовое ТЗ, где все структурировано расписано на понятном вам языке. Но для задач на собеседовании это перебор. Время сильно ограничено, вы стрессуете и вместо того, чтобы думать над задачей - пытаетесь продраться через витиеватое описание.
Сложность: 🟡 Средняя
ℹ️ Описание
В мире Dota2 существует 2 партии
Для того чтобы внести изменение в игру Dota2 необходимо провести голосование сената, каждый член которого принадлежит одной из двух партий.
Голосование идет раундами, в каждом раунде по очереди опрашивается каждый сенатор.
Сенатор может выполнить одно из двух действий:
- лишить следующего сенатора из противоположной партии права голоса;
- объявить победу своей партии, если не осталось сенаторов с правом голоса из противоположной партии.
Раунд начинается с крайнего левого сенатора.
Напишите функцию, которая будет рассчитывать результаты голосования сената.
⚠️ Ограничения
- Количество сенаторов (длина входящей строки) находится в диапазоне от 1 до 10000
- Входящая строка состоит из символов
1️⃣ Пример
Входящие данные
Ответ
2️⃣ Пример
Входящие данные
Ответ
✅ Решение
На первый взгляд задача может решиться простым сравнением количества сенаторов из каждой партии.
На самом деле такое решение будет не верно, так как не учитывает порядок голосования. Это легко понять на примере
Правильный подход для решения этой задачи — воспользоваться структурой данных «очередь», поместив в нее сенаторов в заданом порядке.
Тогда весь процесс сведется к двум действиям:
- Забрать из начала очереди сенатора, а после того как тот совершит ход (лешит права голоса ближайшего сенатора из противоположной партии), помещать его в конец очереди.
- Удалить из очереди сенаторов без права голоса.
Итоговый ответ мы получим, когда в очереди останутся представители только одной партии.
Посмотреть реализацию и подробный разбор примера в блоге
🅾️ Оценка сложности
По времени
O(n) — так как нам придется несколько раз проитерироваться по очереди.
По памяти
O(n) — так как мы выделяем память для работы с очередью.
#queue #medium
Данная задача относится к моему «любимому» типу — попробуй пойми что от тебя хотят.
Первая сложность задачи не в поиске самого решения, а в попытках сократить контекст и описания с половины экрана до нескольких строчек, убирая весь лор про Dota2, сенаторов и регламенты проведения голосований.
Безусловно, в реальных условиях так часто и бывает — вам приносят бизнес задачу/проблему, которую вы должны решить, а не готовое ТЗ, где все структурировано расписано на понятном вам языке. Но для задач на собеседовании это перебор. Время сильно ограничено, вы стрессуете и вместо того, чтобы думать над задачей - пытаетесь продраться через витиеватое описание.
Сложность: 🟡 Средняя
ℹ️ Описание
В мире Dota2 существует 2 партии
Radiant и Dire.Для того чтобы внести изменение в игру Dota2 необходимо провести голосование сената, каждый член которого принадлежит одной из двух партий.
Голосование идет раундами, в каждом раунде по очереди опрашивается каждый сенатор.
Сенатор может выполнить одно из двух действий:
- лишить следующего сенатора из противоположной партии права голоса;
- объявить победу своей партии, если не осталось сенаторов с правом голоса из противоположной партии.
Раунд начинается с крайнего левого сенатора.
Напишите функцию, которая будет рассчитывать результаты голосования сената.
⚠️ Ограничения
- Количество сенаторов (длина входящей строки) находится в диапазоне от 1 до 10000
- Входящая строка состоит из символов
R и D1️⃣ Пример
Входящие данные
RD
Ответ
Radiant
2️⃣ Пример
Входящие данные
RDD
Ответ
Dire
✅ Решение
На первый взгляд задача может решиться простым сравнением количества сенаторов из каждой партии.
На самом деле такое решение будет не верно, так как не учитывает порядок голосования. Это легко понять на примере
RDRDRDRDRDDD.Правильный подход для решения этой задачи — воспользоваться структурой данных «очередь», поместив в нее сенаторов в заданом порядке.
Тогда весь процесс сведется к двум действиям:
- Забрать из начала очереди сенатора, а после того как тот совершит ход (лешит права голоса ближайшего сенатора из противоположной партии), помещать его в конец очереди.
- Удалить из очереди сенаторов без права голоса.
Итоговый ответ мы получим, когда в очереди останутся представители только одной партии.
Посмотреть реализацию и подробный разбор примера в блоге
🅾️ Оценка сложности
По времени
O(n) — так как нам придется несколько раз проитерироваться по очереди.
По памяти
O(n) — так как мы выделяем память для работы с очередью.
#queue #medium
algorithmics-blog.github.io
Сенат Dota2
Подробный разбор решения задачи с примерами на языках TypeScript и GO
👍10
Самый низкий общий предок двоичного дерева
Сложность: 🟡 Средняя
ℹ️ Описание
Вам дано двоичное дерево. Найдите наименьшего общего предка (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
Сложность: 🟡 Средняя
ℹ️ Описание
Вам дано двоичное дерево. Найдите наименьшего общего предка (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
🔥5👍4❤2
Угадай число
Сегодня мы рассмотрим вместе с вами еще одну классическую задачу из учебников.
Сложность: 🟢 Легкая
ℹ️ Описание
Мы играем в игру, где вы должны угадать загаданное число.
Игра заключается в следующем.
— Я выбираю число от 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
Сегодня мы рассмотрим вместе с вами еще одну классическую задачу из учебников.
Сложность: 🟢 Легкая
ℹ️ Описание
Мы играем в игру, где вы должны угадать загаданное число.
Игра заключается в следующем.
— Я выбираю число от 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
👍7❤4🔥2
Количество последних вызовов
Сложность: 🟢 Легкая
ℹ️ Описание
Вам дан класс 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️⃣ Пример
Ответ: 3
Пояснение: За последние 3000 мс было сделано 4 вызова в следующее время [1, 100, 3001].
✅ Решение
Эта задача решается буквально в несколько строчек.
Для хранения вызовов определим массив calls внутри класса, который при инициализации экземпляра получает значение пустого массива.
Далее в реализации метода ping сначала надо добавить время нового вызова в массив calls, а потом удалить из начала все элементы, которые вываливаются из интервала в 3000 миллисекунд, тем самым реализовав простую очередь. В конце нужно лишь вернуть длину оставшегося массива.
Посмотреть реализацию в блоге
🅾️ Оценка сложности
По времени
Основная временная сложность нашего метода ping заключается в цикле, который в худшем случае будет выполнять 3000 итераций для извлечения всех устаревших элементов, а в лучшем случае — одну итерацию. Исходя из этого сложность равна O(3000) = O(1).
По памяти
Сложность O(1), так как максимальная длина нашего массива вызовов — 3000 элементов. По условию задачи, каждое новое значение в нем является целым числом и строго больше предыдущего, поэтому мы точно можем определить максимальный размер массива.
#queue #easy
Сложность: 🟢 Легкая
ℹ️ Описание
Вам дан класс 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
❤3👍1🔥1
Максимальный зигзагообразный путь в бинарном дереве
Продолжаем закреплять тему деревьев. В общем виде, если вы встречаете задачу на деревья или графы, с большой долей вероятности стоит вспоминать и модифицировать поиск в ширину/глубину.
Сложность: 🟡 Средняя
ℹ️ Описание
Напишите функцию, которая будет вычислять длину самого длинного зигзагообразного пути в бинарном дереве. Путь может начинаться НЕ с корневого элемента дерева.
⚠️ Ограничения
Количество элементов в дереве от 1 до 50000
✅ Решение
Для решение задачи нам потребуется вспомнить как работает алгоритм поиска в глубину и немного модифицировать его. Основная сложность данной задачи в том, что наш путь не обязан начинаться от корня дерева, он может «всплывать» из более глубоких слоев дерева, поэтому на каждой ноде нам нужно оперировать четырьмя величинами:
- Длиной пути, начинающегося от текущего элемента направо.
- Длиной пути, начинающегося от текущего элемента налево.
- Длиной максимального пути «снизу» с левой дочерней ноды.
- Длиной максимального пути «снизу» с правой дочерней ноды.
Поднимаясь по слоям дерева во время рекурсивного обхода нам будет достаточно вычислять и возвращать максимум из этих величин.
Посмотреть примеры и реализацию в блоге
🅾️ Оценка сложности
По времени
O(n) —так как нам нужно совершить поиск в глубину по бинарному дереву, перебрав все n его элементов.
По памяти
O(n) — так как мы используем рекурсивный подход. Это означает, что мы будем хранить в памяти n переменных во время вычисления стека рекурсии.
#tries #medium
Продолжаем закреплять тему деревьев. В общем виде, если вы встречаете задачу на деревья или графы, с большой долей вероятности стоит вспоминать и модифицировать поиск в ширину/глубину.
Сложность: 🟡 Средняя
ℹ️ Описание
Напишите функцию, которая будет вычислять длину самого длинного зигзагообразного пути в бинарном дереве. Путь может начинаться НЕ с корневого элемента дерева.
⚠️ Ограничения
Количество элементов в дереве от 1 до 50000
✅ Решение
Для решение задачи нам потребуется вспомнить как работает алгоритм поиска в глубину и немного модифицировать его. Основная сложность данной задачи в том, что наш путь не обязан начинаться от корня дерева, он может «всплывать» из более глубоких слоев дерева, поэтому на каждой ноде нам нужно оперировать четырьмя величинами:
- Длиной пути, начинающегося от текущего элемента направо.
- Длиной пути, начинающегося от текущего элемента налево.
- Длиной максимального пути «снизу» с левой дочерней ноды.
- Длиной максимального пути «снизу» с правой дочерней ноды.
Поднимаясь по слоям дерева во время рекурсивного обхода нам будет достаточно вычислять и возвращать максимум из этих величин.
Посмотреть примеры и реализацию в блоге
🅾️ Оценка сложности
По времени
O(n) —так как нам нужно совершить поиск в глубину по бинарному дереву, перебрав все n его элементов.
По памяти
O(n) — так как мы используем рекурсивный подход. Это означает, что мы будем хранить в памяти n переменных во время вычисления стека рекурсии.
#tries #medium
algorithmics-blog.github.io
Максимальный зигзагообразный путь в бинарном дереве
Подробный разбор решения задачи с примерами на языках TypeScript и GO
❤1👍1
console.log(`
__
_ / /|
|\\ \/_/
\_\| / __
\/_/__\ .-=='/~\
____,__/__,_____,______)/ /{~}}}
-,------,----,-----,---,\'-' {{~}}
jgs '-==.\}/
`)
Сегодня не будет задач!
Cегодня мы поздравляем всех наших подписчиц с прекрасным женским днем.
Будьте красивыми, счастливыми и прокаченными в алгоритмах!
С праздником!
Please open Telegram to view this post
VIEW IN TELEGRAM
💋6👍3❤2🔥1🤔1💔1
Переместите нули
Сложность: 🟢 Легкая
ℹ️ Описание
Вам дан целочисленный массив 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
Сложность: 🟢 Легкая
ℹ️ Описание
Вам дан целочисленный массив 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
👍4🔥2❤1
Дети с наибольшим количеством конфет
Сложность: 🟢 Легкая
ℹ️ Описание
Есть 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
Сложность: 🟢 Легкая
ℹ️ Описание
Есть 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
❤1🔥1👏1
Определите, близки ли две строки
Сложность: 🟡 Средняя
ℹ️ Описание
Вам дано две строки. Верните 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
Сложность: 🟡 Средняя
ℹ️ Описание
Вам дано две строки. Верните 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
🔥6😁2❤1👏1🤡1
Разворот связанного списка
Привет, друзья. В этот вторник хочется решить что-то новое, но ненапряжное, поэтому давайте расмотрим задачу на связанные списки. С ними мы еще не работали.
Сложность: 🟢 Легкая
ℹ️ Описание
Вам дан односвязный список. Переверните список и верните его.
Список представлен следующей структурой.
⚠️ Ограничения
— Количество узлов в связанном списке находится в диапазоне от 1 до 5000
— Значение каждого узла находится в диапазоне от -5000 до 5000
✅ Решение
Для реализации данной задачи нам всего лишь необходимо перебрать все узлы связанного списка и поменять местами указатели на следующий и предыдущий узлы.
Посмотреть реализацию в блоге
🅾️ Оценка сложности
По времени
Сложность O(n), так как мы итерируемся по всем узлам списка.
По памяти
Сложность O(1), так как мы не выделяем дополнительную память.
#linked_list #easy
Привет, друзья. В этот вторник хочется решить что-то новое, но ненапряжное, поэтому давайте расмотрим задачу на связанные списки. С ними мы еще не работали.
Сложность: 🟢 Легкая
ℹ️ Описание
Вам дан односвязный список. Переверните список и верните его.
Список представлен следующей структурой.
class ListNode {
val: number
next: ListNode | null
}
⚠️ Ограничения
— Количество узлов в связанном списке находится в диапазоне от 1 до 5000
— Значение каждого узла находится в диапазоне от -5000 до 5000
✅ Решение
Для реализации данной задачи нам всего лишь необходимо перебрать все узлы связанного списка и поменять местами указатели на следующий и предыдущий узлы.
Посмотреть реализацию в блоге
🅾️ Оценка сложности
По времени
Сложность O(n), так как мы итерируемся по всем узлам списка.
По памяти
Сложность O(1), так как мы не выделяем дополнительную память.
#linked_list #easy
👍4🔥2❤1
Является ли строка подпоследовательностью
Сложность: 🟢 Легкая
ℹ️ Описание
Дано две строки s и t. Напишите функцию, которая возвращает true, если s является подпоследовательностью t, или false в противном случае.
Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (может быть ни одного) символов без нарушения относительного положения остальных символов. (т. е. «ace» является подпоследовательностью abcde, а «aec» — нет).
⚠️ Ограничения
— Длина строки s находится в диапазоне от 0 до 100
— Длина строки t находится в диапазоне от 0 до 10000
— В строках могут присутствовать только латинские буквы в нижнем регистре
1️⃣ Пример
Входные данные
Ответ
2️⃣ Пример
Входные данные
Ответ
✅ Решение
Для решения задачи воспользуемся самым простым способом, а именно движением по обеим строкам с помощью двух указателей.
Мы запускаем цикл по всем символам строки t и сравниваем их с символами строки s. Для отслеживания позиции в строке s мы будем использовать указатель pos.
- Если символы совпадают, мы двигаем указатель строки pos на одну позицию вперед.
- Если после прохода по всем символам строки t указатель pos указывает на конец строки s, значит строка s является подпоследовательностью строки t.
- Если во время очередной итерации выполняется это же условие, то мы моем досрочно завершить выполнение функции и вернуть true, так как дальнейший проход по строке t не имеет смысла.
Посмотреть реализацию в блоге
#strings #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
❤4👍3🔥3
Привет, друзья. Простите нас за молчание, просто админы ушли в отпуск 😄
Через неделю мы вернемся к вам с новыми задачами, а пока что вы можете следить за нашими приключениями в Намибии в этом канале.
Через неделю мы вернемся к вам с новыми задачами, а пока что вы можете следить за нашими приключениями в Намибии в этом канале.
Telegram
Digital Nomad
Привет! Меня зовут Алексей
Я разработчик и цифровой кочевник.
Уже более двух лет я езжу по миру и делюсь здесь своим опытом и впечатлениями.
Автор @avivasyuta
Я разработчик и цифровой кочевник.
Уже более двух лет я езжу по миру и делюсь здесь своим опытом и впечатлениями.
Автор @avivasyuta
🔥4
Сжатие строки
Как и обещали, возвращаемся к вам с отпуска с новыми силами. Сегодня хочется разобрать одну из очень популярных и классических задач с собеседований - пишем свой простенький архиватор 🙂
Сложность: 🟡 Средняя
ℹ️ Описание
Дана строка в виде массива символов. Необходимо написать функцию, которая сожмет входящий массив и вернет количество символов в сжатом массиве по следующему принципу:
— Если символ повторяется больше одного раза подряд, нужно заменить всю подстроку на строку ['a', 'n'], где a - исходный символ, n - количество повторений этого символа, идущих подряд. В случае если n — многозначное число, каждая цифра должна быть добавлена отдельным символом.
— Если буква не повторяется - оставить ее без изменений.
Все изменения нужно совершить in-place, в качестве ответа функции вернуть количество символов в сжатой строке.
⚠️ Ограничения
— Длина входящего массива от 1 до 2000 символов
— Элементы массива - символы латиницы, цифры или знаки
1️⃣ Пример
Входные данные
Ответ
Исходный массив должен быть преобразован в
2️⃣ Пример
Входные данные
Ответ
3️⃣ Пример
Входные данные
Ответ
Исходный массив должен быть преобразован в
✅ Решение
Задача решается достаточно элементарно, главная загвоздка - замена элементов in-place.
Для решение задачи нам понадобятся несколько индексов:
— Индекс текущего элемента lastElemIdx
— Индекс начала последовательности одинаковых элементов firstElemIdx
— Индекс элемента, который будет заменен при сжатии строки newPositionIdx. Для эффективности решения мы будем заменять элементы исходного массива, а после «отрежем» хвост. В противном случае нам бы пришлось вырезать повторяющиеся символы, смещая хвост массива на n элементов влево, что значительно замедлит алгоритм.
Далее нам достаточно аккуратно обойти и модифицировать исходный массив.
Посмотреть реализацию в блоге
#arrays #medium
Как и обещали, возвращаемся к вам с отпуска с новыми силами. Сегодня хочется разобрать одну из очень популярных и классических задач с собеседований - пишем свой простенький архиватор 🙂
Сложность: 🟡 Средняя
ℹ️ Описание
Дана строка в виде массива символов. Необходимо написать функцию, которая сожмет входящий массив и вернет количество символов в сжатом массиве по следующему принципу:
— Если символ повторяется больше одного раза подряд, нужно заменить всю подстроку на строку ['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
🔥3👍2💅1
Максимальное количество пар 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
Сложность: 🟡 Средняя
ℹ️ Описание
Вам дан целочисленный массив 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
algorithmics-blog.github.io
Максимальное количество пар K-суммы
Подробный разбор решения задачи с примерами на языках TypeScript и GO
👍3🔥3❤2
Максимальное количество гласных в подстроке заданного размера
Сложность: 🟡 Средняя
ℹ️ Описание
Дана строка s и максимальный размер подстроки k.
Необходимо написать функцию, которая вернет максимальное количество глассных в любой из подстрок строки s размером k.
⚠️ Ограничения
— Длина строки от 1 до 100000
— Строка состоит только из латинских букв в нижнем регистре
— Размер подстроки находится в диапазоне от 1 до длины исходной строки s.
1️⃣ Пример
Входные данные
Ответ
В исходной строке есть подстрока длиной 3 состоящая исключительно из гласных iii.
2️⃣ Пример
Входные данные
Ответ
Так как исходная строка состоит полностью из гласных, любая подстрока длиной 2 также будет состоять из гласных.
3️⃣ Пример
Входные данные
Ответ
В исходной строке есть несколько подстрок (`lee`/`eet`/`ode`), в любой из которых максимальное количество гласных равно 2.
✅ Решение
Данная задача является ярким представителем класса задач, которые решаются с помощью скользящего окна:
- Нам необходимо создать окно длиной k (исходно левая граница окна равна 0, а правая - `k-1`)
- Двигать наше окно увеличивая левый и правый индекс на 1 на каждом шаге
- Считать сколько гласных попадает в наше окно на каждом шаге
Также важно помнить, что для каждого нового окна нам не обязательно с нуля считать количество гласных, мы всегда сможем быстро рассчитать ответ исходя из количества гласных в предыдущем окне и изменения нового окна относительно предыдущего, то есть нам достаточно смотреть только на границы окна.
Посмотреть реализацию в блоге
#strings #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
algorithmics-blog.github.io
Максимальное количество гласных в подстроке заданного размера
Подробный разбор решения задачи с примерами на языках TypeScript и GO
👍3🔥1
Максимальный средний подмассив
Сложность: 🟢 Легкая
ℹ️ Описание
Вам дан целочисленный массив 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
Сложность: 🟢 Легкая
ℹ️ Описание
Вам дан целочисленный массив 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
algorithmics-blog.github.io
Максимальный средний подмассив
Подробный разбор решения задачи с примерами на языках TypeScript и GO
👍3🔥1😱1
Сколько нужно стрел, чтобы лопнуть все воздушные шары
Сложность: 🟡 Средняя
ℹ️ Описание
К плоской стене, представляющей плоскость 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
Сложность: 🟡 Средняя
ℹ️ Описание
К плоской стене, представляющей плоскость 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
👍2🔥2❤1