Leetcode. 13. 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.

Получив римскую цифру, преобразуйте ее в целое число.

Example 1:
Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Решение на Java

class Solution {
    public int romanToInt(String s) {
        var romanToInt = new HashMap<Character, Integer>();

        romanToInt.put('I', 1);
        romanToInt.put('V', 5);
        romanToInt.put('X', 10);
        romanToInt.put('L', 50);
        romanToInt.put('C', 100);
        romanToInt.put('D', 500);
        romanToInt.put('M', 1000);

        int sum = 0;
        int length = s.length();

        for(var i = 0; i < length; i++) {
            int cur = romanToInt.get(s.charAt(i));

            if(i < length - 1 && cur < romanToInt.get(s.charAt(i+1))) {
                sum -= cur;
            } else {
                sum += cur;
            }
        }

        return sum;
    }
}

Объяснение

1. Создаем словарь для римских цифр:

var romanToInt = new HashMap<Character, Integer>();

romanToInt.put('I', 1);
romanToInt.put('V', 5);
romanToInt.put('X', 10);
romanToInt.put('L', 50);
romanToInt.put('C', 100);
romanToInt.put('D', 500);
romanToInt.put('M', 1000);

В этом словаре мы храним соответствие римских цифр и их значений. Например, 'I' соответствует 1, 'V' - 5, и так далее.

2. Создаем переменные для хранения результата и длины строки:

int sum = 0;
int length = s.length();

sum будет хранить итоговое значение, а length - длину строки s.

3. Проходим по каждому символу строки:

for(var i = 0; i < length; i++) {
    int cur = romanToInt.get(s.charAt(i));

В цикле мы идем по каждому символу строки и находим его значение в словаре romanToInt.

4. Проверяем следующий символ и выполняет соответствующее действие:

if(i < length - 1 && cur < romanToInt.get(s.charAt(i+1))) {
    sum -= cur;
} else {
    sum += cur;
}

Если текущий символ меньше следующего, мы вычитаем его значение из sum. Это нужно для случаев, когда меньшая цифра стоит перед большей, например, в "IV" (4) или "IX" (9).
В остальных случаях мы просто добавляем значение текущего символа к sum.

5. Возвращает итоговое значение:

return sum;

Пример:

Рассмотрим строку "IX":

Длина строки length = 2.
Первая итерация (i = 0):
- cur = romanToInt.get('I') = 1.
- Следующий символ 'X', его значение 10, больше текущего.
- Значит, вычитаем cur из sum: sum = 0 - 1 = -1.
Вторая итерация (i = 1):
- cur = romanToInt.get('X') = 10.
- Нет следующего символа, просто добавляем cur к sum: sum = -1 + 10 = 9.
Возвращаем sum, то есть 9.

Решение на Ruby

# @param {String} s
# @return {Integer}
def roman_to_int(s)
    roman_to_int = {
        'I' => 1,
        'V' => 5,
        'X' => 10,
        'L' => 50,
        'C' => 100,
        'D' => 500,
        'M' => 1000
    }

    sum = 0

    s.each_char.with_index do |c, i|
        cur = roman_to_int[c]

        if i < s.size-1 && cur < roman_to_int[s[i+1]]
            sum -= cur
        else
            sum += cur
        end
    end

    sum
end

Решение на Golang

func romanToInt(s string) int {
    romanToInt := map[rune]int {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }

    sum := 0
    length := len(s)

    for i, c := range s {
        if i < length-1 && romanToInt[c] < romanToInt[rune(s[i+1])] {
            sum -= romanToInt[c]
        } else {
            sum += romanToInt[c]
        }
    }

    return sum
}

Решение на Javascript / Typescript

function romanToInt(s: string): number {
    const romanToInt: Map<string, number> = new Map([
        ['I', 1],
        ['V', 5],
        ['X', 10],
        ['L', 50],
        ['C', 100],
        ['D', 500],
        ['M', 1000]
    ]);

    let sum = 0;
    const length = s.length;

    for (let i = 0; i < length; i++) {
        const cur = romanToInt.get(s.charAt(i))!;

        if (i < length - 1 && cur < romanToInt.get(s.charAt(i + 1))!) {
            sum -= cur;
        } else {
            sum += cur;
        }
    }

    return sum;
};

Решение на Python

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_to_int = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }

        sum = 0
        length = len(s)

        for i in range(length):
            cur = roman_to_int[s[i]]

            if i < length - 1 and cur < roman_to_int[s[i+1]]:
                sum -= cur
            else:
                sum += cur

        return sum

Решение на PHP

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function romanToInt($s) {
        $romanToInt = array(
            'I' => 1,
            'V' => 5,
            'X' => 10,
            'L' => 50,
            'C' => 100,
            'D' => 500,
            'M' => 1000
        );

        $sum = 0;
        $length = strlen($s);

        for ($i = 0; $i < $length; $i++) {
            $cur = $romanToInt[$s[$i]];

            if ($i < $length - 1 && $cur < $romanToInt[$s[$i+1]]) {
                $sum -= $cur;
            } else {
                $sum += $cur;
            }
        }

        return $sum;
    }
}

Решение на Csharp

public class Solution {
    public int RomanToInt(string s) {
        var romanToInt = new Dictionary<char, int>();

        romanToInt['I'] = 1;
        romanToInt['V'] = 5;
        romanToInt['X'] = 10;
        romanToInt['L'] = 50;
        romanToInt['C'] = 100;
        romanToInt['D'] = 500;
        romanToInt['M'] = 1000;

        int sum = 0;
        int length = s.Length;

        for (int i = 0; i < length; i++) {
            int cur = romanToInt[s[i]];

            if (i < length - 1 && cur < romanToInt[s[i+1]]) {
                sum -= cur;
            } else {
                sum += cur;
            }
        }

        return sum;
    }
}

Решение на Java#

Объяснение#

1. Создаем словарь для римских цифр:#

2. Создаем переменные для хранения результата и длины строки:#

3. Проходим по каждому символу строки:#

4. Проверяем следующий символ и выполняет соответствующее действие:#

5. Возвращает итоговое значение:#

Пример:#

Решение на Ruby#

Решение на Golang#

Решение на Javascript / Typescript#

Решение на Python#

Решение на PHP#

Решение на Csharp#