В ходе собеседований для ежедневных тренировок был задан ряд вопросов по программированию.
Эту проблему задала компания Amazon, основанная на сжатии данных, в которой запрашивалась реализация серийного кодирования строк.
Кодирование длин серий - это простейший метод сжатия данных. Основная идея этого состоит в том, чтобы представить повторяющиеся последовательные символы как единый счетчик и символ. Кодирование длин серий - это быстрый и простой метод кодирования строк.
Например-
Он относится к категории сжатия без потерь и, следовательно, является обратимым.
Сжатие без потерь - это класс алгоритмов сжатия данных, который позволяет идеально восстанавливать исходные данные из сжатых данных.-wikipedia
Основным недостатком этого метода является то, что, когда нет повторяющихся строк, вывод будет с увеличенным размером бит или вместо сжатия он будет расширяться.
Вопрос- Реализуйте кодирование и декодирование длин серий. Вы можете предположить, что кодируемая строка не имеет цифр и состоит исключительно из буквенных символов. Вы можете предположить, что декодируемая строка действительна.
Решение:
Мы можем реализовать encode
, перебирая нашу входную строку и сохраняя текущий счетчик любого текущего символа, и как только мы встречаем другой, добавляя счетчик (в виде строки) и фактический символ к нашей строке результата.
def encode(s): if not s: return ''
result = '' current_char = s[0] current_count = 0 for i, char in enumerate(s, 1): if char == current_char: current_count += 1 else: result += str(current_count) + current_char current_char = char current_count = 1 result += str(current_count) + current_char return result
Мы можем реализовать decode
, перебирая закодированную строку и проверяя каждый символ на наличие цифры. Если это так, то вычислите правильный счетчик, и как только мы найдем соответствующий ему символ, расширим результат с помощью количества символов, а затем сбросим счетчик.
def decode(s):
count = 0
result = ''
for char in s:
if char.isdigit():
count = count * 10 + int(char)
else:
# char is alphabetic
result += char * count
count = 0
return result
Спасибо за чтение, хорошего дня! 🙂