スナップ13.ローマ数字回転整数(mapハッシュ)
2494 ワード
スナップ13.ローマ数字回転整数
https://leetcode-cn.com/problems/roman-to-integer/
ローマ数字には、I、V、X、L、C、D、Mの7文字が含まれています.
文字値I 1 V 5 X 10 L 50 C 100 D 500 M 1000は、例えば、ローマ数字2をIIと書くと、2つの並列の1となる.12はXIIと書きます.つまりX+IIです.27 XXVIIと書くと、XX+V+IIとなります.
通常、ローマ数字の中で小さい数字は大きな数字の右側にあります.しかし、例えば4はIIIではなくIVと書くという特例もある.数字1は数字5の左側にあり、表す数は大数5から小数1を減らした数値4に等しい.同様に、数字9はIXとして表される.この特殊なルールは、次の6つの場合にのみ適用されます.
IはV(5)とX(10)の左側に置いて4と9を表すことができる.XはL(50)とC(100)の左側に置いて40と90を表すことができる.CはD(500)とM(1000)の左側に置いて400と900を表すことができる.ローマ数字を指定し、整数に変換します.入力は1~3999の範囲であることを確認します.
例1:
入力:III出力:3例2:
入力:IV出力:4例3:
入力:IX出力:9例4:
入力:「LVIII」出力:58解釈:L=50,V=5,III=3.例5:
入力:「MCMXCIV」出力:1994解釈:M=1000,CM=900,XC=90,IV=4.
考え方:
//法則を探す:現在の値が次の値より小さい場合は、減算します.そうでなければ、加算//コード実装では、複数のビットを後ろに見て、現在のビットと後のビットのサイズ関係を比較して、現在のビットが加算されるか減算されるかを決定することができます.次の人がいない場合は、加算をすればいいです.//複雑度分析:時間複雑度:O(N)、文字列を1回遍歴した;空間複雑度:O(1)
法二:mapハッシュで実現
map挿入:
map使用:
https://leetcode-cn.com/problems/roman-to-integer/
ローマ数字には、I、V、X、L、C、D、Mの7文字が含まれています.
文字値I 1 V 5 X 10 L 50 C 100 D 500 M 1000は、例えば、ローマ数字2をIIと書くと、2つの並列の1となる.12はXIIと書きます.つまりX+IIです.27 XXVIIと書くと、XX+V+IIとなります.
通常、ローマ数字の中で小さい数字は大きな数字の右側にあります.しかし、例えば4はIIIではなくIVと書くという特例もある.数字1は数字5の左側にあり、表す数は大数5から小数1を減らした数値4に等しい.同様に、数字9はIXとして表される.この特殊なルールは、次の6つの場合にのみ適用されます.
IはV(5)とX(10)の左側に置いて4と9を表すことができる.XはL(50)とC(100)の左側に置いて40と90を表すことができる.CはD(500)とM(1000)の左側に置いて400と900を表すことができる.ローマ数字を指定し、整数に変換します.入力は1~3999の範囲であることを確認します.
例1:
入力:III出力:3例2:
入力:IV出力:4例3:
入力:IX出力:9例4:
入力:「LVIII」出力:58解釈:L=50,V=5,III=3.例5:
入力:「MCMXCIV」出力:1994解釈:M=1000,CM=900,XC=90,IV=4.
考え方:
//法則を探す:現在の値が次の値より小さい場合は、減算します.そうでなければ、加算//コード実装では、複数のビットを後ろに見て、現在のビットと後のビットのサイズ関係を比較して、現在のビットが加算されるか減算されるかを決定することができます.次の人がいない場合は、加算をすればいいです.//複雑度分析:時間複雑度:O(N)、文字列を1回遍歴した;空間複雑度:O(1)
// : , ;
// , , , 。 , 。
// : :O(N), ; :O(1)
//
#include "stdafx.h"
#include
using namespace std;
class Solution {
public:
int romanToInt(string s)
{
// ,
int sum = 0;
int cur = 0;
while (cur
法二:mapハッシュで実現
class Solution {
public:
int romanToInt(string s) {
int result=0;
map luomab;//
luomab.insert(map::value_type('I',1));
luomab.insert(map::value_type('V',5));
luomab.insert(map::value_type('X',10));
luomab.insert(map::value_type('L',50));
luomab.insert(map::value_type('C',100));
luomab.insert(map::value_type('D',500));
luomab.insert(map::value_type('M',1000));
for(int i=0;i
map挿入:
map luomab = {
{"I", 1}, {"V", 5}, {"X", 10}, {"L", 50},
{"C", 100}, {"D", 500}, {"M", 1000}
};
map使用:
luomab[s[i]];