Integer to Roman

Q: Какова временная сложность алгоритма преобразования целого числа в римское?

O(1) . Входное значение не превышает 3999, поэтому жадный цикл проверяет 13 строк таблицы и добавляет не более 15 символов. Если бы допускались большие числа, записанные с повторяющейся M , время росло бы пропорционально num / 1000 .

Q: Почему 3999 — наибольшее допустимое число?

M — самая большая буква, и ни одна буква не может встречаться подряд четыре раза, поэтому MMM — это предел для тысяч, а 3999 записывается как MMMCMXCIX . Большие числа записывали с помощью дополнительных знаков, например черты над буквой, чтобы умножить её на 1000.

СреднеМатематика и моделирование Жадные алгоритмы

+10

В римских цифрах используются семь букв: M — 1000, D — 500, C — 100, L — 50, X — 10, V — 5 и I — 1. Буквы идут от большей к меньшей и складываются, поэтому 7 — это VII. Нельзя повторять одну букву четыре раза подряд: числа 4, 9, 40, 90, 400 и 900 записываются как IV, IX, XL, XC, CD и CM: меньшая буква вычитается из стоящей после неё большей. Только в этих шести парах сначала ставится меньшая буква.

Дано целое число num. Верните его римскую запись.

Функция

intToRoman(num: integer) → string

numinteger: целое число от 1 до 3999
Возвращаетstring: римская цифра для num заглавными буквами

Ограничения

1 ≤ num ≤ 3999

Примеры

Ввод: num = 49
Вывод: "XLIX"
Пояснение: 49 — это 40 + 9, поэтому запись состоит из XL, затем IX: XLIX. IL использовать нельзя, потому что I вычитается только в IV и IX.

Ввод: num = 2026
Вывод: "MMXXVI"
Пояснение: В 2026 году нет цифр 4 и 9, поэтому пары не нужны, и буквы складываются: 1000 + 1000 + 10 + 10 + 5 + 1 — это MMXXVI.

Ввод: num = 944
Вывод: "CMXLIV"
Пояснение: 944 — это 900 + 40 + 4, и каждая часть — это вычитающая пара: CM, XL и IV объединяются в CMXLIV.

Дополнительный вопрос

Дана строка. Можешь проверить, что это римское число в стандартной форме, принимая XLIX и отклоняя IIII, IL и VX?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Добавьте шесть вычитаемых пар в алфавит в качестве самостоятельных символов, и запись числа превратится в размен: всегда берите наибольшее значение, которое ещё подходит. Вводимое число не превышает 3999, поэтому объём работы невелик и фиксирован.

Сначала запишите это в аддитивной форме, а затем сократите длинные формы.

Идея

Сначала игнорируй пары: напиши столько M, сколько поместится, затем D и так далее до I. Для 944 получится DCCCCXXXXIIII. Эта аддитивная форма отличается от стандартной только там, где цифра равна 4 или 9, и в этих местах всегда используется одна из шести строк с краткой формой: DCCCC — это CM, CCCC — это CD, LXXXX — это XC, XXXX — это XL, VIIII — это IX, а IIII — это IV.

Замени DCCCC до CCCC, иначе 900 превратится в DCD; то же самое справедливо для десятков и единиц. Аддитивная форма содержит не более 18 букв (3999), поэтому сложность составляет O(1); за это приходится заплатить вторым проходом и несколькими временными строками.

Алгоритм

Для каждой из семи букв от M до I добавляй её, пока значение num не меньше её значения, и каждый раз вычитай это значение.
Замени DCCCC на CM, затем CCCC на CD.
Замени LXXXX на XC, затем XXXX на XL.
Замени VIIII на IX, затем IIII на IV.
Верни строку.

def intToRoman(num):
    letters = [(1000, "M"), (500, "D"), (100, "C"), (50, "L"), (10, "X"), (5, "V"), (1, "I")]
    numeral = ""
    for value, letter in letters:
        while num >= value:
            numeral += letter
            num -= value
    # Each long form appears at most once; the longer one goes first.
    fixes = [("DCCCC", "CM"), ("CCCC", "CD"), ("LXXXX", "XC"),
             ("XXXX", "XL"), ("VIIII", "IX"), ("IIII", "IV")]
    for long_form, short_form in fixes:
        numeral = numeral.replace(long_form, short_form)
    return numeral

Жадность по 13 значениям

Идея

Упорядочьте семь букв и шесть пар по значению: M 1000, CM 900, D 500, CD 400, C 100, XC 90, L 50, XL 40, X 10, IX 9, V 5, IV 4, I 1. Всегда правильно брать наибольшее подходящее значение. Любое значение младшего десятичного разряда меньше наименьшего значения следующего разряда, поэтому цикл завершается на разряд раньше, чем переходит к следующему. Внутри разряда значения 9, 5, 4 и 1 записывают каждую цифру стандартным способом: 9 — это символ 9, числа от 5 до 8 — символ 5 и до трёх символов 1, 4 — символ 4, а числа от 1 до 3 — символы 1.

Для 3746 цикл записывает MMM, D, CC, XL, V, I: MMMDCCXLVI. В таблице 13 строк, а ответ содержит не более 15 букв, поэтому объём работы — O(1), за один проход.

Алгоритм

Перечисли 13 значений с соответствующими символами, от 1000 до 1, включая пары.
Начни с пустой строки.
Для каждой строки, пока num больше или равен значению, добавляй символ и вычитай это значение.
Верни строку, когда обработаешь все строки.

def intToRoman(num):
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    parts = []
    for value, symbol in zip(values, symbols):
        while num >= value:  # take the largest value that still fits
            parts.append(symbol)
            num -= value
    return "".join(parts)

Ловушки и крайние случаи

Размещение D перед CM в таблице. В результате для 900 получается DCD.
Использование if вместо while для каждой строки. Для 3000 требуется три раза использовать M; с if получается MCMDCDCXCX.
Придумывание других пар. 99 — это XCIX, а не IC, а 45 — это XLV, а не VL.
В C — слишком маленький буфер. Самый длинный ответ, для 3888, содержит 15 букв, поэтому с завершающим нулём требуется 16 байт; для аддитивной формы требуется 19.

Частые вопросы3

Какова временная сложность алгоритма преобразования целого числа в римское?

O(1). Входное значение не превышает 3999, поэтому жадный цикл проверяет 13 строк таблицы и добавляет не более 15 символов. Если бы допускались большие числа, записанные с повторяющейся M, время росло бы пропорционально num / 1000.

Можешь ли ты преобразовать целое число в римские цифры, не перебирая значения в цикле?

Да. Для каждого разряда храните таблицу со строками для его цифр, например "", C, CC, CCC, CD, D, DC, DCC, DCCC, CM для сотен. Найдите строку для каждой цифры числа num и объедините строки. Это также O(1), при этом хранится 34 строки.

Почему 3999 — наибольшее допустимое число?

M — самая большая буква, и ни одна буква не может встречаться подряд четыре раза, поэтому MMM — это предел для тысяч, а 3999 записывается как MMMCMXCIX. Большие числа записывали с помощью дополнительных знаков, например черты над буквой, чтобы умножить её на 1000.

def intToRoman(num):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

num = 49

Ожидаемый вывод

"XLIX"