Пример решения задачи #12. Python LeetCode, Integer to Roman

Вариант решения задачи на языке программирования Python с LeetCode.
Категория: Алгоритмы.
Название задачи: Integer to Roman.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
Семь различных символов представляют римские цифры со следующими значениями:

Symbol: I, Value: 1.
Symbol: V, Value: 5.
Symbol: X, Value: 10.
Symbol: L, Value: 50.
Symbol: C, Value: 100.
Symbol: D, Value: 500.
Symbol: M, Value: 1000.

Римские цифры образуются путем добавления преобразований значений десятичных знаков от самого высокого к самому низкому. Преобразование значения десятичного знака в римское число имеет следующие правила:

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

Если значение начинается с 4 или 9, используйте субтрактивную форму , представляющую один символ, вычитаемый из следующего символа, например, 4 на 1 ( I) меньше 5 ( V): IV и 9 на 1 ( I) меньше 10 ( X): IX. Используются только следующие субтрактивные формы: 4 ( IV), 9 ( IX), 40 ( XL), 90 ( XC), 400 ( CD) и 900 ( CM).

Только степени 10 ( I, X, C, M) могут быть добавлены последовательно не более 3 раз для представления кратных 10. Вы не можете добавить 5 ( V), 50 ( L) или 500 ( D) несколько раз. Если вам нужно добавить символ 4 раза, используйте вычитательную форму .

Дано целое число, преобразуйте его в римскую цифру.

Решение:

Python

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """

        # Создаем словарь для соответствия арабских цифр и римских символов
        roman_numerals = {
            1000: 'M',
            900: 'CM',
            500: 'D',
            400: 'CD',
            100: 'C',
            90: 'XC',
            50: 'L',
            40: 'XL',
            10: 'X',
            9: 'IX',
            5: 'V',
            4: 'IV',
            1: 'I'
        }

        # Создаем пустую строку для результата
        result = ""

        # Проходим по ключам словаря в порядке убывания
        for value, symbol in sorted(roman_numerals.items(), reverse=True):
            # Пока число больше или равно текущему значению:
            while num >= value:
                # Добавляем соответствующий римский символ к результату
                result += symbol
                # Вычитаем значение из числа
                num -= value

        return result

Объяснение кода

Словарь roman_numerals:
Создается словарь, где ключи - это десятичные значения, а значения - соответствующие римские символы.

Важно, что ключи расположены в порядке убывания, чтобы мы могли эффективно обрабатывать число.

Словарь учитывает как обычные значения (1, 5, 10 и т.д.), так и специальные случаи для вычитательных форм (4, 9, 40 и т.д.).

Инициализация result:
Создается пустая строка, в которую будет записываться окончательный результат в римских цифрах.

Итерация по словарю:
Мы проходим по элементам словаря в порядке убывания ключей.
Для каждого ключа (десятичного значения) и соответствующего значения (римского символа):
Проверяем, больше ли оставшееся число (num) текущего значения.
Если да, то добавляем римский символ к результату и вычитаем значение из числа.
Этот процесс повторяется, пока число не станет меньше текущего значения.

Возврат результата:
После завершения цикла, в строке result будет содержаться римское представление исходного числа.

Источник решения: hdhai.com