Проблема
https://leetcode.com/problems/roman-to-integer/
Римские цифры представлены семью различными символами: 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.
Дана римская цифра, преобразовать ее в целое число.
Первый инстинкт
Моим первым побуждением было создать хэш-словарь для хранения каждой из оригинальных и отдельных римских цифр с их значениями, подобными этому.
const dict = { I:1, V:5, X:10, L:50, C:100, D:500, M:1000 }
Мне нравится разбивать алгоритм на удобоваримые части, поэтому я проигнорировал крайние случаи IX, IV и т. д. и просто сосредоточился на способе сложения символов в строке.
До меня довольно быстро дошло: используйте цикл, чтобы найти значение каждого символа в строке и добавить к итогу, а затем вернуть итог. Моя выглядела так…
function romanToInt(str){ let total = 0; for(let i = 0; i<str.length; i++){ let char = str[i]; total += dict[char]; } return total }
Теперь я хотел рассмотреть крайние случаи. Сначала я думал, что мне придется создать массу операторов if else и использовать несколько указателей, чтобы найти следующее значение для сравнения. Однако я знал, что должен быть более простой и эффективный способ сделать это, потому что всякий раз, когда код кажется слишком утомительным, обычно так оно и есть. Я вернулся к подсказке и внимательно прочитал ее. Мне запомнилась информация: «Римские цифры обычно пишутся слева направо от большего к меньшему». Хммм, так что, когда это не так, у нас есть значение, которое меньше, чем две цифры. Для IV с нашим кодом выше он будет читаться как 6, но с пограничным случаем будет 4, или V -I. И это работает для остальных тоже! Попробуйте кое-что, я это делал, когда изначально псевдокодировал, и все пограничные случаи работают!
Решение
Итак, как мы реализуем это в коде? Ну, сначала мы должны сохранить следующий символ после начального в значении. Нам нужен оператор if, который говорит, что если значение char меньше следующего значения, мы вычитаем текущее значение char, на котором мы находимся, и двигаемся дальше. В противном случае мы добавляем текущее значение char. Таким образом, с чем-то вроде IV мы бы вычли 1 из суммы для I, перешли бы к V, увидели, что после V ничего нет, а затем добавили бы 5 к сумме, в результате чего сумма = 4.
function romanToInt(str){ let total = 0; for(let i = 0; i<str.length; i++){ let char = str[i]; let next = str[i+1]; if(dict[char]<dict[next]){ total -= dict[char] }else{ total += dict[char]; } } return total }
Большой О
Временная сложность, если O (n), потому что нам нужно перебрать всю строку.
Сложность пространства составляет O(1), потому что, хотя мы должны хранить значения в хэше, он постоянен независимо от длины строки.