Letcodeロマンから整数へ
19585 ワード
問題声明
ローマ数字は、7つの異なるシンボルで表されます:I、V.
X、L、C、D、M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
12はXIIとして書かれています.
27はXXVII、XX＋V＋IIである.
ローマ数字は、通常、左から右に最小に最大に書き込まれます.
ただし、4の数字はIIIIではない.
代わりに、番号4をIVと書く.
つは5つ前に私たちはそれを4つを減算します.数9についても同様である.
減算が使用される6つのインスタンスがあります.
私は、V(5)とX(10)の前に置かれて、4と9を作ることができます.
Xは、L(50)とC(100)の前に配置することができ、40と90を作ることができる.
D(500)及びM(1000)の前にCを配置して400と900とする.
からの問題文 https://leetcode.com/problems/roman-to-integer
例1 :
Input: s = "III"
Output: 3
Input: s = "IV"
Output: 4
Input: s = "IX"
Output: 9
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
- 1 <= s.length <= 15
- s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
- It is guaranteed that s is a valid roman numeral in the range [1, 3999].
解説
この問題の解決は簡単です.
我々はローマの文字の順序に注意を払う必要があります
を返します.
IVの代わりに4から4を表す.
これは文字の現在の値を減算する必要がある場合にヒントを与えます
または合計金額に追加します.
アルゴリズム
- initialize an hash map characterMap with keys as 'I', 'V', 'X', 'L', 'C', 'D', 'M'
and value as 1, 5, 10, 50, 100, 500, 1000.
- return 0 if s.length() == 0.
- if s.length == 1, return characterMap[s[0]]
- set sum = characterMap[s[s.length() - 1]].
- characterMap[s[s.length() - 1]] is the value of the last character in the string s.
- Loop for i = s.length() - 2; i >= 0; i--
// if value of the current character is less than next character we subtract current value from sum
- if characterMap[s[i]] < characterMap[s[i+1]]
- subtract sum = sum - characterMap[s[i]]
- else
- add sum = sum + characterMap[s[i]]
- return sum
C++ソリューション
class Solution {
public:
int romanToInt(string s) {
map<char, int> characterMap = {
{'I', 1},
{'V', 5},
{'X', 10},
{'L', 50},
{'C', 100},
{'D', 500},
{'M', 1000}
};
int length = s.length();
if(length == 0) {
return 0;
}
if(length == 1){
return characterMap[s[0]];
}
int sum = characterMap[s[length - 1]];
for(int i = length - 2; i >= 0; i--){
if(characterMap[s[i]] < characterMap[s[i+1]]){
sum -= characterMap[s[i]];
} else {
sum += characterMap[s[i]];
}
}
return sum;
}
};
ゴランソリューション
func romanToInt(s string) int {
characterMap := map[byte]int{
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
length := len(s)
if length == 0 {
return 0
}
if length == 1 {
return characterMap[s[0]]
}
sum := characterMap[s[length - 1]]
for i := length - 2; i >= 0; i-- {
if characterMap[s[i]] < characterMap[s[i+1]] {
sum -= characterMap[s[i]]
} else {
sum += characterMap[s[i]]
}
}
return sum
}
ジャバスクリプト
var romanToInt = function(s) {
const characterMap = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
};
const length = s.length;
if( length == 0 ) {
return 0;
}
if( length == 1 ){
return characterMap[s[0]];
}
var sum = characterMap[s[length - 1]];
for( var i = length - 2; i >= 0; i-- ) {
if( characterMap[s[i]] < characterMap[s[i + 1]] ) {
sum -= characterMap[s[i]];
} else {
sum += characterMap[s[i]];
}
}
return sum;
};
s = "MCMXCIV"
map<char, int> characterMap = {
{'I', 1},
{'V', 5},
{'X', 10},
{'L', 50},
{'C', 100},
{'D', 500},
{'M', 1000}
};
length = s.length()
= 7
Step 1: length == 0
7 == 0
false
Step 2: length == 1
7 == 1
false
Step 3: sum = characterMap[s[length - 1]]
= characterMap[s[7 - 1]]
= characterMap[s[6]]
= characterMap['V']
= 5
Step 4: for i = length - 2; i >= 0; i--
i = 5
5 >= 0
characterMap[s[i]] < characterMap[s[i + 1]]
characterMap[s[5]] < characterMap[s[6]]
characterMap['I'] < characterMap['V']
1 < 5
true
sum -= characterMap[s[i]]
= characterMap[s[5]]
= characterMap['I']
= 1
sum = 5 - 1
= 4
i--
i = 4
Step 5: i >= 0
i = 4
4 >= 0
characterMap[s[i]] < characterMap[s[i + 1]]
characterMap[s[4]] < characterMap[s[5]]
characterMap['C'] < characterMap['I']
100 < 1
false
sum += characterMap[s[i]]
= characterMap[s[4]]
= characterMap['C']
= 100
sum = 4 + 100
= 104
i--
i = 3
Step 6: i >= 0
i = 3
3 >= 0
characterMap[s[i]] < characterMap[s[i + 1]]
characterMap[s[3]] < characterMap[s[4]]
characterMap['X'] < characterMap['C']
10 < 100
true
sum -= characterMap[s[i]]
= characterMap[s[3]]
= characterMap['X']
= 10
sum = 104 - 10
= 94
i--
i = 2
Step 7: i >= 0
i = 2
2 >= 0
characterMap[s[i]] < characterMap[s[i + 1]]
characterMap[s[2]] < characterMap[s[3]]
characterMap['M'] < characterMap['X']
1000 < 10
false
sum += characterMap[s[i]]
= characterMap[s[2]]
= characterMap['M']
= 1000
sum = 94 + 1000
= 1094
i--
i = 1
Step 8: i >= 0
i = 1
1 >= 0
characterMap[s[i]] < characterMap[s[i + 1]]
characterMap[s[1]] < characterMap[s[2]]
characterMap['C'] < characterMap['M']
100 < 1000
true
sum -= characterMap[s[i]]
= characterMap[s[1]]
= characterMap['C']
= 100
sum = 1094 - 100
= 994
i--
i = 0
Step 9: i >= 0
i = 0
0 >= 0
characterMap[s[i]] < characterMap[s[i + 1]]
characterMap[s[0]] < characterMap[s[1]]
characterMap['M'] < characterMap['C']
1000 < 100
false
sum += characterMap[s[i]]
= characterMap[s[0]]
= characterMap['M']
= 100
sum = 994 + 1000
= 1994
i--
i = -1
Step 10: i >= 0
i = -1
-1 >= 0
return sum as 1994
Reference
この問題について(Letcodeロマンから整数へ), 我々は、より多くの情報をここで見つけました https://dev.to/_alkesh26/leetcode-roman-to-integer-46opテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol