Дан набор символов и их веса (обычно пропорциональные вероятностям). Найдите двоичный код без префиксов (набор кодовых слов) с минимальной ожидаемой длиной кодового слова.
Ссылка: https://www.hackerrank.com/challenges/tree-huffman-decoding/problem
Мыслительный процесс:
Просто следуйте инструкциям и используйте двоичный код для извлечения символьной информации. Если 0, мы перемещаемся влево, а если 1, мы перемещаемся вправо. Если дочерних элементов больше нет, мы считываем значение листа и добавляем его в строку. Нам нужно будет сбросить текущий узел до корневого, чтобы мы могли прочитать следующий символ. Вот код:
Решение Python 3:
Сложность:
время: 0 (n)
память: о (п)
Комментарии и предложения приветствуются!
