Как и обещали, возвращаемся к вам с отпуска с новыми силами. Сегодня хочется разобрать одну из очень популярных и классических задач с собеседований - пишем свой простенький архиватор 🙂
Сложность: 🟡 Средняя
ℹ️ Описание
Дана строка в виде массива символов. Необходимо написать функцию, которая сожмет входящий массив и вернет количество символов в сжатом массиве по следующему принципу:
— Если символ повторяется больше одного раза подряд, нужно заменить всю подстроку на строку ['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