OJ练习47——T12 Integer to Roman

把整数转换成罗马数字。数字不超过3999.

罗马数字规律：1-I，5-V，10-X，50-L，100-C，500-D，1000M

【对比回顾】

罗马数字到整数：

基本规律，当左边数字大于右边，是和的关系，如VI=5+1=6，XII=10+2=12;

当左边数字小于右边，是差的关系，如IV=5-1=4，IX=10-1=9,XL=50-10=40.

【思路1】

列出字符所有可能的情况成单独一个方法，对string s的每个元素调用方法，得到其代表的值，有三种可能：

1）连续相等，则累加到临时变量sub

2）若当前值比前一个值小，则把sub加到result上，再sub=cur

3）若当前值比前一个值大，则是“含4”情况，就要有sub=cur-lastc

【other code1】

int romanToInt(string s) {
    if(s.length() < 1) return 0;  
    int result=0;
    int sub=getthenumber(s[0]);
    int lastc=sub;
    int cur=0;
    for(int i=1;i<s.length();i++)
    {
        cur=getthenumber(s[i]);
        if(cur==lastc)
            sub+=cur;
        else if(cur>lastc)
            sub=cur-sub;
        else {
            result+=sub;
            sub=cur;
        }
           lastc=cur;
    }
    result+=sub;
    return result;  
    }  
    int getthenumber(char c) {  
        switch(c) {  
            case 'I': return 1;   
            case 'V': return 5;  
            case 'X': return 10;  
            case 'L': return 50;  
            case 'C': return 100;  
            case 'D': return 500;  
            case 'M': return 1000;  
            default: return 0;  
        }  
    }  

【思路2】

用数组保存特殊字母对应的十进制数，相当于上面的getthenumber函数。

int romanToInt(string s) {
        int map[26];
        map['I'-'A'] = 1; map['V'-'A'] = 5; map['X'-'A'] = 10; map['L'-'A'] = 50; 
        map['C'-'A'] = 100; map['D'-'A'] = 500; map['M'-'A'] = 1000;
        int res = 0, n = s.size();
        s.push_back(s[n-1]);
        for(int i = 0; i < n; i++)
        {
            if(map[s[i]-'A'] >= map[s[i+1]-'A'])
                res += map[s[i]-'A'];
            else res -= map[s[i]-'A'];
        }
        return res;
    }

代码明显要简洁很多，注意最后一位的处理，为了满足比较i+1位。否则会发生越界！

【本题思路】

1.因为给出最大值是3999，因此可以从1000开始除，列出每一位所有可能

string intToRoman(int num) {
        char c[10][10][10]={{"0","I","II","III","IV","V","VI","VII","VIII","IX"},{"0","X","XX","XXX","XL","L","LX"
        ,"LXX","LXXX","XC"},{"0","C","CC","CCC","CD","D",
              "DC","DCC","DCCC","CM"},{"0","M","MM","MMM"}};
        int t=1;
        int tmp=num;
        string st;
        if(tmp/1000!=0) st+=c[3][tmp/1000];
        if((tmp%1000)/100!=0) st+=c[2][(tmp%1000)/100];
        if((tmp%100)/10!=0) st+=c[1][(tmp%100)/10];
        if(tmp%10!=0) st+=c[0][tmp%10];
        return st;
    }

2.发现规律：

个位上的数字依次是 I,II,III,IV,V,VI,VII,VIII,IX

十位上的数字把I替换为X，V替换为L，X替换为C，即表示10,20，...,90

百位、千位依次类推。

【other code】

string intToRoman(int num) {
        char romanChar[]={'I','V','X','L','C','D','M'};
        string res;
        int i=6,factor=1000;
        while(num!=0){
            helper(num/factor,&romanChar[i],res);
            num%=factor;
            factor/=10;
            i-=2;
        }
        return res;
    }
    void helper(int k, char *romanChar, string &res){
        if(k<=0);
        else if(k<=3)
            res.append(k,romanChar[0]);
        else if(k==4){
            res.push_back(romanChar[0]);
            res.push_back(romanChar[1]);
        }
        else if(k<=8){
            res.push_back(romanChar[1]);
            res.append(k-5,romanChar[0]);
        }
        else if(k==9){
            res.push_back(romanChar[0]);
            res.push_back(romanChar[2]);
        }
    }

【总结】

有好几个聪明的处理：

1.每一位都按照1-9的思路处理，变的是传入的romanChar表，用&romanChar[i]来取特定的子串。i每次-=2.

2.res.append(int,char)头一次使用，表示在res后接int个相同的char字符，即III类似。