Ссылка: → 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).

Спасибо, что прочитали эту статью ❤

Если я что-то не так? Позвольте мне в комментариях. Я хотел бы улучшить.

Хлопайте 👏 Если вам поможет эта статья.