Ссылка: → https://leetcode.com/problems/roman-to-integer/
Проблема: →
Римские цифры представлены семью различными символами: I
, V
, X
, L
, C
, D
и M
.
Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000
Например, 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.
Дана римская цифра, преобразовать ее в целое число.
Пример 1:
Input: s = "III" Output: 3 Explanation: III = 3.
Пример 2:
Input: s = "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3.
Пример 3:
Input: s = "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Ограничения:
1 <= s.length <= 15
s
содержит только символы('I', 'V', 'X', 'L', 'C', 'D', 'M')
.- Гарантируется, что
s
является допустимой римской цифрой в диапазоне[1, 3999]
.
Решение: →
Здесь, проверив примеры и изображения, вы можете получить некоторое представление:
- Нам нужно начать чтение справа налево. Например IV → V, а затем I
- Здесь мы видим, что у нас есть значения ниже
I 1 V 5 X 10 L 50 C 100 D 500 M 1000
IV = 4, но VI = 6
Итак, мы можем думать, как показано ниже
Первый пример:
IV
мы читаем справа налево V и I
V = 5, I = 1
Здесь V идет первым, а затем я, чтобы мы могли проверить
если V › мне нравится 5 › 1
Сделайте вычитание, я имею в виду 5-1 = 4,
Второй пример:
VI
Читаем справа налево I и V.
V = 5, I = 1
Здесь я на первом месте, а затем В, чтобы мы могли проверить
если мне > V нравится 1 > 5, это условие становится False
Сделайте сложение, я имею в виду 5 + 1 = 6.
Если условие истинно, то вычитание, если условие ложно, то сложение.
Давайте посмотрим код:
Код (Java):
Временная сложность:
Максимальная длина строки может быть 15, как видно из ограничений 1 <= s.length <= 15
, поэтому временная сложность в худшем случае может быть O(15) или O(1).
Пространственная сложность:
Мы используем карту/словарь для хранения римских символов и соответствующих им целочисленных значений, но имеется только 7 символов, поэтому сложность пространства в худшем случае может быть O{7}, что эквивалентно O( 1).
Спасибо, что прочитали эту статью ❤
Если я что-то не так? Позвольте мне в комментариях. Я хотел бы улучшить.
Хлопайте 👏 Если вам поможет эта статья.