Roman to Integer

Q: Почему вы вычитаете символ, который меньше следующего?

Так устроены шесть вычитаемых пар. В IV , IX , XL , XC , CD и CM меньший символ стоит перед большим, и пара означает разность большего и меньшего. Вычитание первого символа и добавление второго дают именно это значение, и ни в каком другом месте правильной записи числа меньший символ не стоит перед большим.

ЛегкоМатематика и моделирование Хеширование

+10

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

Вам дана корректная римская цифра s. Верните целое число, которое она обозначает.

Функция

romanToInt(s: string) → integer

sstring: корректная римская цифра, написанная заглавными буквами
Возвращаетinteger: значение числа от 1 до 3999

Ограничения

1 ≤ s.length ≤ 15
s содержит только символы I, V, X, L, C, D и M.
s — допустимая римская цифра для значения от 1 до 3999.

Примеры

Ввод: s = "XXVII"
Вывод: 27
Пояснение: XX — это 10 + 10, V — это 5, а II — это 1 + 1, поэтому сумма равна 27. Ни за одним символом не следует символ большего значения, поэтому все символы складываются.

Ввод: s = "CDXLIV"
Вывод: 444
Пояснение: Число состоит из трёх вычитаемых пар подряд: CD — это 400, XL — 40, а IV — 4, что в сумме даёт 444.

Ввод: s = "MCDXCII"
Вывод: 1492
Пояснение: M — это 1000, CD — это 400, XC — это 90, а II — это 2, поэтому число равно 1492. Пары и отдельные символы свободно сочетаются.

+22 скрытых тестов при отправке

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

Можешь написать обратную функцию, преобразующую целое число от 1 до 3999 в римское число?

Подсказки

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

Открыто 0 из 3

Решение

Большая часть римского числа — это обычная сумма, поэтому вся задача сводится к тому, чтобы распознать шесть вычитаемых пар. Их можно искать по двухбуквенным сочетаниям или воспользоваться одним правилом, которое охватывает все шесть случаев: символ, значение которого меньше значения следующего за ним символа, вычитается. В любом случае одного прохода по строке длиной не более 15 символов достаточно, чтобы получить ответ.

Читайте вычитаемые пары как токены

Идея

Представь римское число как ряд токенов. Большинство токенов состоит из одного символа, а шесть — из двух символов: IV, IX, XL, XC, CD и CM. Разбей строку на такие токены, сложи их значения — и получишь число.

На каждой позиции сначала посмотри на следующие два символа. Если они образуют одну из шести пар, прибавь значение пары и перейди через оба символа. Иначе прибавь значение одного символа и перейди через него. MCDXCII разбивается на M, CD, XC, I, I: 1000 + 400 + 90 + 1 + 1 = 1492.

Проверку пары нужно выполнять первой. Если прочитать X из XC отдельно, ты прибавишь 10, а затем 100 и получишь 110 вместо 90. Эта проверка также безопасна: в корректной римской записи символ меньшего значения стоит непосредственно перед символом большего значения только в одной из этих шести пар, поэтому любая найденная тобой пара настоящая.

На каждом шаге обрабатывается один или два символа, поэтому цикл выполняется не более 15 раз. Обе таблицы имеют фиксированный размер, поэтому дополнительное пространство постоянно.

Алгоритм

Создай одну таблицу для шести пар и одну для семи одиночных символов.
Начни с индекса 0 и общей суммы 0.
Если два символа по этому индексу образуют пару, добавь значение пары и увеличь индекс на 2.
В противном случае добавь значение одиночного символа и увеличь индекс на 1.
Когда индекс выйдет за конец, верни общую сумму.

def romanToInt(s):
    pairs = {"IV": 4, "IX": 9, "XL": 40, "XC": 90, "CD": 400, "CM": 900}
    singles = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    i = 0
    while i < len(s):
        two = s[i:i + 2]
        if two in pairs:
            total += pairs[two]
            i += 2
        else:
            total += singles[s[i]]
            i += 1
    return total

Сравните каждый символ со следующим

Идея

Посмотрите на шесть пар ещё раз. В каждой из них значение первого символа меньше значения второго, а значение пары равно значению второго за вычетом первого. Поэтому таблицу пар можно пропустить и использовать одно правило: если значение символа меньше значения символа справа от него, вычтите его; в противном случае прибавьте его. CM превращается в -100 + 1000 = 900 — в то же значение, которое получается при чтении токенов.

Разберём MCDXCII. За M следует меньшая C, поэтому прибавляем 1000. За C следует большая D, поэтому вычитаем 100: сумма равна 900. Прибавляем D и получаем 1400. За X следует большая C, поэтому вычитаем 10: получаем 1390. Прибавляем C: 1490. За первой I следует равная ей I, поэтому прибавляем её: 1491. У последней I нет соседа, поэтому прибавляем и её: 1492.

Сравнение должно быть строгим: меньше. Равные соседние символы всегда складываются — именно поэтому II равно 2, а XX — 20. Это правило верно по той же причине, что и чтение токенов: в правильной записи меньший символ стоит непосредственно перед большим только как первая половина вычитаемой пары.

Вы просматриваете каждый символ один раз и поддерживаете текущую сумму, поэтому временная сложность составляет O(n), а дополнительная память — O(1). Для этой версии нужны только значения семи символов и одно сравнение для каждого символа.

Алгоритм

Сохрани значение каждого из семи символов.
Перебирай индексы s, поддерживая текущую сумму, которая начинается с 0.
Если следующий символ существует и его значение больше значения текущего, вычти текущее значение.
Иначе прибавь текущее значение.
После цикла верни сумму.

def romanToInt(s):
    values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    for i in range(len(s)):
        value = values[s[i]]
        # A symbol worth less than the one after it is subtracted, like the I in IV.
        if i + 1 < len(s) and value < values[s[i + 1]]:
            total -= value
        else:
            total += value
    return total

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

Правило короткое, поэтому ошибки связаны с его пограничными случаями.

Использование «меньше или равно» вместо строгого «меньше». Тогда II превращается в 0, и XX — в 0, потому что каждый первый символ вычитается.
Чтение следующего символа для последнего символа. Там s[i+1] не существует; сначала проверьте i+1 относительно длины и всегда прибавляйте последний символ.
В версии с токенами попытка проверить одиночные символы до пар. Тогда XC читается как 10 + 100 = 110.
Распознавание пары только по её второму символу. Если вы уже прибавили I из IV, вам придётся вычесть его дважды: 1 + 5 - 2 × 1 = 4. Сравнение со следующим символом позволяет избежать этой корректировки.
Забывание о том, что строки в Lua и R начинаются с индекса 1, поэтому последний символ находится в #s или nchar(s).

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

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

Оба подхода считывают каждый символ один раз, поэтому временная сложность составляет O(n) для числа из n символов. Дополнительная память — O(1), поскольку таблицы поиска имеют фиксированный размер. Число от 1 до 3999 содержит не более 15 символов, поэтому на практике объём работы очень мал.

Почему вы вычитаете символ, который меньше следующего?

Так устроены шесть вычитаемых пар. В IV, IX, XL, XC, CD и CM меньший символ стоит перед большим, и пара означает разность большего и меньшего. Вычитание первого символа и добавление второго дают именно это значение, и ни в каком другом месте правильной записи числа меньший символ не стоит перед большим.

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

Да. Идите от последнего символа к первому и запоминайте значение символа, который вы прочитали раньше, — того, что находится справа. Если значение текущего символа меньше значения того символа, вычитайте его; иначе прибавляйте. Это то же правило, что и при чтении слева направо, только рассмотренное с другой стороны.

Проверяет ли это решение, что числительное допустимо?

Нет. В условии гарантируется корректная запись числа, поэтому код только складывает и вычитает. Для некорректной строки, например IIII или VV, он всё равно возвращает число: 4 и 10. Чтобы проверить корректность, преобразуй результат обратно в запись числа и сравни его с исходной строкой.

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

s = "XXVII"

Ожидается