Проблема

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), потому что, хотя мы должны хранить значения в хэше, он постоянен независимо от длины строки.