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

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

ℹ️ Описание

Дано две строки 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

Вижу, многие не знают о том, что у нас есть блог.

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

Пары одинаковых строк и колонок

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

ℹ️ Описание

Дана матрица grid размером n x n, которая состоит из целых положительных чисел.

Посчитайте количество пар (r[i], c[j]), где строка r[i] равна колонке c[j]

Строка и колонка считаются равными, если они состоят из одинаковых элементов в одинаковом порядке.

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

— Размер n находится в диапазоне от 1 до 200
— Значение каждого элемента в матрице находится в диапазоне от 1 до 10^5

1️⃣ Пример

Входные данные: grid = [[3,2,1],[1,7,6],[2,7,7]]

Ответ: 1

Есть одна одинаковая пара:
— (Строка 2, Колонка 1): [2,7,7]

2️⃣ Пример

Входные данные: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]

Ответ: 3

Есть три одинаковые пары:
— (Строка 0, Колонка 0): [3,1,2,2]
— (Строка 2, Колонка 2): [2,4,2,2]
— (Строка 3, Колонка 2): [2,4,2,2]

✅ Решение

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

Создаем карту подсчета строк:

Инициализируем пустую хеш-таблицу (объект в случае TypeScript) countMap, который будет хранить строки в виде ключей и их количество в виде значений.
Проходим по каждой строке матрицы. Для каждой строки создаем строковой ключ, конкатенируя все её элементы, разделенные точкой с запятой.
Если такой ключ уже существует в countMap, увеличиваем значение на единицу. В противном случае, устанавливаем значение равным единице.
Подсчет совпадающих столбцов:

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

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

#matrix #hash_table #medium

Максимальная глубина бинарного дерева

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

ℹ️ Описание

Найдите максимальную глубину бинарного дерева.

Максимальная глубина бинарного дерева — это количество узлов на самом длинном пути от корневого узла до самого дальнего листового узла.

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

— Количество узлов в дереве может быть от 0 до 10000
— Значение каждого узла находится в диапазоне от -100 до 100

✅ Решение

Для решения задачи нам достаточно реализовать простой поиск в глубину DFS (Depth First Search).

Реализуем дополнительную рекурсивную функцию dfs, которая принимает на вход два аргумента:
— текущий узел дерева node
— текущую глубину погружения level

В качестве ответа функция будет возвращать максимальную глубину ветки дерева.

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

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

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

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

#tree #binary_tree #easy

Листоподобные деревья

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

ℹ️ Описание

Дано два бинарных дерева. Все листовые узлы дерева образуют последовательность значений.
Например, для дерева на картинке последовательность значений будет равна (6, 7, 4, 9, 8).

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

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

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

— Количество узлов в каждом дереве находится в диапазоне [1, 200]
— Узлы обоих деревьев имеют значения в диапазоне [0, 200]

✅ Решение

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

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

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

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

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

#tree #binary_tree #easy

Всем привет!

У меня есть небольшое хобби - я люблю коллекционировать профессиональную литературу. Громко сказано, на пара полок с Таненбаумом, «Философией Java» и прочими томами служили украшением моего домашнего рабочего места, пока я не перешел на кочевой образ жизни 🙂 Правда, если быть честным, большинство книг я прочел едва ли наполовину, но все же 🙂

К чему это я? Поделитесь в комментариях, пожалуйста, книгами, которые вам понравились и которые вы считаете полезными и важными для прочтения.

Начну с себя: одна из лучших книг в моей коллекции — «Designing Data-Intensive Applications» Мартина Клеппмана (она же всем известная «книжка с кабанчиком», она же «Высоконагруженные приложения. Программирование, масштабирование, поддержка»).

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

Самая длинная подстрока, являющаяся валидной скобочной последовательностью

Всем привет!
Сегодня продолжаем одновременно 2 начинания: решать сложные задачи и решать задачи на валидные скобочные последовательности 🙂

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

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

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

ℹ️ Описание

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

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

— Длина каждой строки от 0 до 30 000 символов
— Строка состоит из символов '(' и ')'

1️⃣ Пример
Входные данные

s := "(()"

Ответ

2

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

2️⃣ Пример
Входные данные

s := ")()())"

Ответ

4

Самая длинная правильная скобочная последовательность - ()().

3️⃣ Пример
Входные данные

s := ""

Ответ

0

✅ Решение

Можно попробовать пойти с помощью брутфорса — взять всю строку (как самую длинную возможную подстроку) и проверить её на валидность. После уменьшить длину подстроки на единицу и проверить на валидность 2 возможные подстроки длиной n-1. Потом ещё на единицу и проверить три возможные подстроки длиной n-2. И так далее, пока не наткнёмся на первую валидную подстроку. Но такое решение будет слишком долгим — на LeetCode вы даже не сможете пройти все тест-кейсы из-за таймаута.

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

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

#stack #hard

Преобразование строки в целое число (atoi)

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

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

ℹ️ Описание

Реализуйте функцию myAtoi(string s), которая преобразует строку в 32-битное знаковое целое число.

Функция должна следовать следующим правилам при чтении строки:

— Пропустить любые ведущие пробелы
— Проверить наличие знака (+ или -)
— Читать следующие символы до тех пор, пока они составляют последовательность цифр.
— Преобразовать эти цифры в целое число.
— Если первая непустая последовательность символов не является допустимым целым числом, вернуть 0.
— Если полученное значение превышает диапазон 32-битного знакового целого числа, вернуть INT_MAX (2^31 - 1) или INT_MIN (-2^31).

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

— Длина строки находится в диапазоне от 0 до 200
— Строка s состоит из английских букв (как заглавных, так и строчных), цифр, пробелов и знаков «+», «-» и «.»

1️⃣ Пример

Входные данные: "42"
Ответ: 42

2️⃣ Пример

Входные данные: " -42"
Ответ: -42

3️⃣ Пример

Входные данные: "4193 with words"
Ответ: 4193

4️⃣ Пример

Входные данные: "words and 987"
Ответ: 0

5️⃣ Пример

Входные данные: "-91283472332"
Ответ: -2147483648

✅ Решение

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

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

После этого нам нужно проверить присутствует ли в строке определение знака числа. Для этого заведем переменную sign.

— Если встречаем в строке символ +, то устанавливаем значение sign равным 1.
— Если встречаем в строке символ -, то устанавливаем значение sign равным -1.
— Если в строке присутствовал знак числа, то еще необходимо увеличить index на единицу.

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

— Если char < "0" или char > "9", то символ не является числом. Как только мы встретили не числовой символ в строке, то дальнейший разбор необходимо прекратить.
—Если смвол является числом, то его необходимо добавить к результирующему числу. Для этого надо воспользоваться следующей формулой res = res * 10 + char - '0'. Это позволяет прибавить цифру справа к существующему числу.

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

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

В заключение, в ответе нужно вернуть res умноженный на знак sign.

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

#string #medium

Вес Хэмминга

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

Вес Хэмминга (Hamming weight) также известный как популяционное число (population count), представляет собой количество единичных (установленных) битов в двоичном представлении числа.
Формально, для числа 𝑛 вес Хэмминга определяется как сумма всех битов числа 𝑛 в его двоичной форме.

Примеры

1️⃣ Число 5

- Двоичное представление: 101
- Вес Хэмминга: 2 (два бита установлены в 1)

2️⃣ Число 13

- Двоичное представление: 1101
- Вес Хэмминга: 3 (три бита установлены в 1)

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

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

— Криптография. В криптографических алгоритмах вес Хэмминга может использоваться для оценки случайности и сложности ключей.

— Обработка сигналов. Вес Хэмминга может применяться для анализа и фильтрации сигналов, а также для оценки шума.

Наименования битов

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

1. Старший бит (Most Significant Bit, MSB)

Это бит, который имеет наибольший вес в двоичном числе и находится в крайней левой позиции.
Например, в числе 1000 (в двоичной системе) старший бит равен 1.

2. Младший бит (Least Significant Bit, LSB)

Это бит, который имеет наименьший вес в двоичном числе и находится в крайней правой позиции.
Например, в числе 1000 (в двоичной системе) младший бит равен 0.

3. Средние биты (Intermediate Bits)

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

4. Установленный бит

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

5. Значимый бит

Значимые биты — это биты, которые существенно влияют на значение числа. Обычно это все биты, начиная с первого установленного бита до младшего бита.
Например, в числе 0010110 (в двоичной системе) значимые биты — 10110.

6. Последний установленный бит (Last Set Bit)

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