[leetcode]Integer to Romanの詳細

Integer to Roman
RomanとIntegerの変換ルール?
From Wikipediaが現在使用しているローマ数字は7文字で、以下の表に示されています.
文字
値
I
1
V
5
X
10
L
50
C
100
D
500
M
1,000
ローマ数字の値は、次のように加算(または減算)されます.
ローマ数字の組み合わせ
結果
コンビネーションモード
CCVII
100 + 100 + 5 + 1 + 1 = 207
プラス
MLXVI
1,000 + 50 + 10 + 5 + 1 = 1066
プラス
IV
-1 + 5 = 4
減らす
MCMLIV
1,000 + (-100 + 1,000) + 50 + (-1 + 5) = 1954
こんごう
足し算は分かりやすいので、左から右へ、あるいは逆から直接付ければいいです.中混合の減算は『左損右盈』:小さい数字は比較的大きい数字 (例えばIV)で (例えばIVで比V差I)である.
比較的良い計算方法は、右から左へ読むことです.

現在のポインタの次の数字が現在の数字以上である場合、現在の数字を前の結果に加算し、ポインタを左に1桁移動する.そうでなければ、次の数字は現在の数字より小さく、2

を行います.

現在の数字から次の数字を減算前の結果に加算.だからこの問題の構想は1組の最大の単位の組み合わせを探し出すべきです.

ぶんせき
一部のブログでは接頭辞セットが与えられていますが、説明はされていません.のJustDoITのブログの分析はとても良くて、実現したのは直観的ではありません.変換する前にローマ数字の組み合わせを見てみましょう.
数値範囲
ローマ数字
1 ~ 9
I II III IV V VI VII VIII IX
10 ~ 19
X XI XII XIII XIV XV XVI XVII XVIII XIX
20 ~ 29
XX XXI XXII XXIII XXIV XXV XXVI XXVII XXVIII XXIX
...
...
これらの文字の組み合わせの「単位要素」を見つけるには、あまり考えられず、接頭辞符号化を減らしているような気がします.整数をローマ数字に変換するときは、最大の一意の接頭辞を1つずつ減算する必要があります.では、どの接頭辞があるかを見てみましょう(接頭辞セットの要素で表現できない組み合わせにスキャンすると、接頭辞セットが追加されます).
接頭辞セット
スキャンコンビネーション
ø
I
I
II
I
III
I
IV
IV I
V
V IV I
VI
V IV I
VII
V IV I
VIII
V IV I
IX
IX V IV I
X
X IX V IV I
XI
…
…
X IX V IV I
XXXIX
ここでは0~9を表す単位要素にIX V IV Iがありますが、10桁がどのように表示されているかを見てみましょう(*でその中の桁数を表します)
接頭辞セット
スキャンコンビネーション
説明
ø
X*
10-19
X
XX*
20-19
X
XXX*
30-39
X
XL*
40-49
XL X
L*
50-59
L XL X
LX*
60-69
L XL X
LXX*
70-79
L XL X
LXXX*
80-89
L XL X
XC*
90-99
XC L XL X
C*
100-109
…
… 10~99の10桁の数字の接頭辞はXC L XL Xだけで、次の接頭辞表を出すことができます.
範囲
接頭辞
個位
IX V IV I
10名
XC L XL X
百位
CM D CD C
…
…
プログラム実装

3999 / 3999 test cases passed.
Status: Accepted
Runtime: 32 ms

/*
*Author: cslzy
*Emaile: [email protected]
*/
class Solution {
public:
    string intToRoman(int num) {
      string prefixes[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX" ,"V","IV" ,"I"};
      int s = sizeof(prefixes) / sizeof(prefixes[0]);

      int values[]      = {1000, 900, 500, 400,   100, 90,   50,  40,   10,   9,   5,  4,    1};

      string result = "";

      int i = 0;
      while(i< s && num < values[i]) i++;

      while(num > 0)
      {
          while(num >= values[i])
          {
              num -= values[i];
              result += prefixes[i];
          }

          i++;
      }

      return result;
    }
};