[C++]LeetCode: 85 Integer to Roman

タイトル:
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
Roman to Integerと対応しています.
Answer 1:ルックアップ
考え方:ローマ数字の左減はクロスビット表現を許さないため、ローマ数字は10進数の桁数で分けて表されていることを示している.
例:99はIC()で表すのではなく、XCIX()で表す.(アラビア数字の1桁あたりの数字に等しい.)ローマ数字という性質を利用して、ルックアップテーブルを構築することができ、タイトルに数字が3999を超えない(横線を加える必要がない)と規定されている場合、4つの配列を構築し、それぞれ千位(0~1000~3000)、百位を表す(0~100~900)、10位(0~10~90)、個位(0~1~9).
Attention:
1.各ビットの確定に注意して、千ビットはnum/1000で、百ビットは(num%1000)/100で、まず千ビットを除いた数字を求めて、それから百ビット数を求めます.このようにします.

 ret = Mtable[num/1000] + Ctable[(num%1000)/100] + Xtable[(num%100)/10] + Itable[num%10];

複雑度:O(1)、時間複雑度O(1)
AC Code:

class Solution {
public:
    string intToRoman(int num) {
        //                        ，         
        
        //0~1000~3000,0~100~900,0~10~90,0~1~9
        vector<string> Mtable{"", "M", "MM", "MMM"};
        vector<string> Ctable{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        vector<string> Xtable{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        vector<string> Itable{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        
        string ret;
        ret = Mtable[num/1000] + Ctable[(num%1000)/100] + Xtable[(num%100)/10] + Itable[num%10];
        return ret;
    }
};

Answer 2:
考え方:ローマ数字のアルファベットは規則的で、いくつかのグループに分けることができて、I(1)、V(5)は1グループで、X(10)、L(50)は1グループで、C(100)、D(500)は1グループで、M(1000)、V(Vは1つの上線をプラスして、5000を表します).そして、後のグループの2つの数は前のグループの10倍です.
10より大きい整数については,整数をビット単位でローマ数字として表す.
個位の数字1~9のそれぞれは、IIIIII IV V VII VIII IX
10桁上の数字1~9は、元のビットのIをX、VをL、XをC、すなわち10桁上の1~9を10~90とする.
このようにして、百位、千位、私たちはローマの表現を得ることができます.
Attention:
1.私たちは千位から百位、十位、個位まで、順番に表します.
2.helper関数をモジュール化するために、具体的に指す文字の位置を判断する必要はありません.移動後の配列ヘッダアドレスを関数に渡します.

//                     
            intToRoman_helper(num/factor, &romanChar[startIdx], ret);

else if( k <= 8)
        {
            ret.push_back(romanChar[1]);
            ret.append(k-5, romanChar[0]);
        }

3.Cの配列で文字を格納します.

char romanChar[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};

4. if...else文は、実行順序に影響があり、順序が実行され、ある文ブロックに入り、完了するとif文が終了します.だから各条件は反発する必要はありません.

        if(k <= 0)
            return;
        else if( k <= 3)
        { }
        else if( k == 4)
        { }
        else if( k <= 8)
        { }
        else if( k == 9)
        { }

5. string append関数

string& append (size_t n, char c);

複雑度:O(N)
AC Code:

class Solution {
public:
    string intToRoman(int num) {
        char romanChar[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
        string ret;
        
        int startIdx = 6;
        int factor = 1000;
        while(num != 0)
        {
            //                     
            intToRoman_helper(num/factor, &romanChar[startIdx], ret);
            num %= factor;
            startIdx -= 2;
            factor /= 10;
        }
        
        return ret;
    }

private:
    void intToRoman_helper(int k, char romanChar[], string& ret)
    {
        if(k <= 0)
            return;
        else if( k <= 3)
        {
            ret.append(k, romanChar[0]);
        }
        else if( k == 4)
        {
            ret.push_back(romanChar[0]);
            ret.push_back(romanChar[1]);
        }
        else if( k <= 8)
        {
            ret.push_back(romanChar[1]);
            ret.append(k-5, romanChar[0]);
        }
        else if( k == 9)
        {
            ret.push_back(romanChar[0]);
            ret.push_back(romanChar[2]);
        }

        return;        
    }
};