Римские цифры представлены семью различными символами: I, V, X, L, C, D и M.
Цифра 2 в римской нумерации записывается как II - просто две единицы, сложенные вместе. Число 12 записывается как XII, то есть просто X + II. Число 27 записывается как XXVII, то есть XX + V + II. Римские цифры обычно пишутся слева направо от наибольшей к наименьшей. Однако цифра, обозначающая четыре не равняется IIII. Вместо этого число четыре записывается как IV. Поскольку единица находится перед пятеркой, мы вычитаем ее, получая четыре. Тот же принцип применим и к числу девять, которое записывается как IX. Итого, в шести случаях мы используем принцип вычитания:
I можно поставить перед V (5) и X (10), чтобы получить 4 и 9.
X можно поставить перед L (50) и C (100), чтобы получить 40 и 90.
C можно поставить перед D (500) и M (1000), чтобы получить 400 и 900.
Дано: Преобразуйте римские цифры (s) в целое число.
Пример:
Дано: s = "III"
Ответ: 3
Объяснение: III = 3.
Ограничения:
- 1 <= s.length (длина римских цифр) <= 15
- s содержит только символы ('I', 'V', 'X', 'L', 'C', 'D', 'M').
- s является допустимым римским числом в диапазоне [1, 3999].
Решение(Python):
Сложность при счете римскими цифрами заключается в том, что некоторые комбинации цифр, как было написано ранее, используются для вычитания. Например, в числе "IV" значение "I" - 1, вычитается из значения "V" - 5. В противном случае вы просто складываете значения всех числительных. Итерацию римских цифр удобнее выполнять справа налево, чтобы облегчить процесс идентификации. Таким образом, проще всего будет просмотреть s в обратном порядке, найти значение каждой буквы и добавить его к нашему ответу. Если встречается значение буквы, меньшее, чем наибольшее из встречавшихся до сих пор, то его следует не прибавлять, а вычитать.
1а) Наивный вариант, складываем числа и проверяем на исключения
def romanToInt(s: str) -> int:
roman_to_integer= {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000
}
result = 0
i = len(s) - 1
while i > -1:
char = s[i]
if (char == 'V' and i != 0 and s[i - 1] == 'I'):
result += 4
i -= 2
elif (char == 'X' and i != 0 and s[i - 1] == 'I'):
result += 9
i -= 2
elif (char == 'L' and i != 0 and s[i - 1] == 'X'):
result += 40
i -= 2
elif (char == 'C' and i != 0 and s[i - 1] == 'X'):
result += 90
i -= 2
elif (char == 'D' and i != 0 and s[i - 1] == 'C'):
result += 400
i -= 2
elif (char == 'M' and i != 0 and s[i - 1] == 'C'):
result += 900
i -= 2
else:
result += roman_to_integer[char]
i -= 1
return result
Создаём ассоциативный массив (карту, хэш-таблицу) для организации сопоставления римских и арабских цифр roman_to_integer. Создаём целочисленную переменную, которая будет преобразовываться и в результате станет нашим ответом result. И переменную с длинной строки римских цифр, с которой будем организовывать цикл - i. Пока не закончится строка с цифрами проходимся по каждому символу строки while i > -1: справа - налево и прибавляем число к нашему ответу result в соответствие с таблицей сравнения roman_to_integer. Если же выпадает один из 6 вариантов исключений, описанных в начале статьи, то мы вычитаем это число. Например:
char == 'M' and i != 0 and s[i - 1] == 'C',
если наш символ s[i] равен M, а предыдущий символ s[i-1] это С, и M - это не первый элемент строки, то сработает исключение CM, которое равно не сумме значений, а их разности.
1б) Более лаконичный вариант, где мы заранее обрабатываем все исключения заменяя их на значения, которые не потребуется вычитать, с использованием replace c обычным обходом слева направо.
def romanToInt(s: str) -> int:
roman_to_integer= {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000
}
result= 0
s = s.replace("IV", "IIII").replace("IX", "VIIII")
s = s.replace("XL", "XXXX").replace("XC", "LXXXX")
s = s.replace("CD", "CCCC").replace("CM", "DCCCC")
for char in s:
result+= roman_to_integer[char]
return result
И такой же вариант, где бы заменяем цикл for функцией map.
def romanToInt(s: str) -> int:
roman_to_integer = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
s = s.replace("IV", "IIII").replace("IX", "VIIII").replace("XL", "XXXX").replace("XC", "LXXXX").replace("CD", "CCCC").replace("CM", "DCCCC")
return sum(map(lambda x: roman_to_integer[x], s))
1в) И вариант с обычным циклом, самый фундаменталичный.
def romanToInt(s: str) -> int:
roman_to_integer= {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
result= 0
for i in range(len(s)):
if i < len(s) - 1 and roman_to_integer[s[i]] < roman_to_integer[s[i + 1]]:
ans -= roman_to_integer[s[i]]
else:
result+= roman_to_integer[s[i]]
return result
также проходим цикл, если символ не последний в строке и следующий символ больше по таблице соответствия текущего вычитаем из переменной result
Все варианты c одинаковой O-нотацией:
Временная сложность: цикла даёт сложность O(n)
Пространственная сложность: используем числовую переменную result, дающую O(1)