1. Introduction
The "Roman to Integer" problem involves converting a string representing a Roman numeral into its equivalent integer value. Roman numerals follow specific rules, with seven symbols representing different values, and some cases where subtraction is used instead of addition.
2. Problem
Given a Roman numeral, convert it to an integer. Roman numerals are represented by the symbols I, V, X, L, C, D, and M, with specific rules for their combination and subtraction in certain cases.
3. Solution in C++
int romanToInt(string s) {
unordered_map<char, int> values = {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
int total = 0;
for (int i = 0; i < s.length(); i++) {
if (i < s.length() - 1 && values[s[i]] < values[s[i + 1]]) {
total -= values[s[i]];
} else {
total += values[s[i]];
}
}
return total;
}
Explanation:
1. Create a hash map to store the values of Roman numerals.
2. Traverse the string s and for each character, add its value to total.
3. If a numeral is followed by a larger numeral, subtract its value instead of adding.
4. The final value of total is the integer representation of the Roman numeral.
4. Solution in Java
public int romanToInt(String s) {
Map<Character, Integer> values = Map.of('I', 1, 'V', 5, 'X', 10, 'L', 50, 'C', 100, 'D', 500, 'M', 1000);
int total = 0;
for (int i = 0; i < s.length(); i++) {
if (i < s.length() - 1 && values.get(s.charAt(i)) < values.get(s.charAt(i + 1))) {
total -= values.get(s.charAt(i));
} else {
total += values.get(s.charAt(i));
}
}
return total;
}
Explanation:
1. Initialize a map with Roman numerals and their values.
2. Iterate over the string, adding the value of each numeral to total.
3. When a numeral is smaller than the one after it, subtract its value.
4. The accumulated value in total is the integer equivalent of the Roman numeral.
5. Solution in Python
def romanToInt(s):
values = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
total = 0
for i in range(len(s)):
if i < len(s) - 1 and values[s[i]] < values[s[i + 1]]:
total -= values[s[i]]
else:
total += values[s[i]]
return total
Explanation:
1. Define a dictionary mapping Roman numerals to their values.
2. Loop through the string s, adding the value of each character to total.
3. If a numeral is smaller than its successor, subtract its value from total.
4. The final total gives the integer value of the Roman numeral.
Comments
Post a Comment