| leetcode

LeetCode笔记-Roman<-->Integer

罗马字符串转整数

规则：

  • 输入： string s，由罗马字母组成的字符串。
  • 映射关系：I-1， V-5, X-10, L-50, C-100, D-500, M-1000;
  • 计算规则：
    1、如如果几个（不超过3个）相同的数字并列，就表示这个数的值是数码的几倍。
    例如罗马数字要表示2，就用2个I来表示，写成II；要表示30, 则写成XXX
    2、不相同的几个数码并列时：
    (1)、如果小的数码在右边，就表示数的数值是数码之和。
    6用罗马数字可以表示为VI，800就是DCCC，58就是LVIII
    (2)、如果小的数码（1个，且只能是I、X、C）在左边，就表示数的数值是这几个数码的差;
    4用罗马数字可以表示为IV，
    通常也只有4、9、40、90、400、900分别表示为IV、IX、XL、XC、CD、CM

解法一

  • 想到的第一种解法就是一个一个字符扫描，每次一位c，如果c是比后面那位(c_next)小的，那c以及c_next的值就是c_next-c;
  • 每次只看c的符号，因为当c>=c_next时，value=+c+c_next, c<c_next时，value=-c+c_next;不同的就是c的符号。c_next留到下一轮考虑。
  • 这里给字符串加了”I”，使得原来s的最后一位比较好处理，因为不管最后一位是啥都不会比”I”小。不会影响计算结果。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
    public:
        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 r = 0;
            s += "I";
            for(int i = 0, len = s.length(); i < len - 1; i++) {
                char c1 = s[i];
                char c2 = s[i+1];
                if(map[c1-'A'] < map[c2-'A']) {
                    r -= map[c1-'A'];
                } else {
                    r += map[c1-'A'];
                }
            }
            return r;
        }
    };

解法二

  • 翻discuss翻出来的，先上代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    public int romanToInt(String s) {
        int sum=0;
        if(s.indexOf("IV")!=-1){sum-=2;}
        if(s.indexOf("IX")!=-1){sum-=2;}
        if(s.indexOf("XL")!=-1){sum-=20;}
        if(s.indexOf("XC")!=-1){sum-=20;}
        if(s.indexOf("CD")!=-1){sum-=200;}
        if(s.indexOf("CM")!=-1){sum-=200;}
        char c[]=s.toCharArray();
        int count=0;
        for(;count<=s.length()-1;count++){
            if(c[count]=='M') sum+=1000;
            if(c[count]=='D') sum+=500;
            if(c[count]=='C') sum+=100;
            if(c[count]=='L') sum+=50;
            if(c[count]=='X') sum+=10;
            if(c[count]=='V') sum+=5;
            if(c[count]=='I') sum+=1;
        }
        return sum;
    }

  • 这段代码其实是错的，它假定了一个串各种需要减的场合最多出现一次，例如输入为”IXIXIX”时，结果应该是27，但是程序的输出却是31。
    改进代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    class Solution {
    public:
        int romanToInt(string s) {
            int sum = 0;
            cout << s.length();
            
            for(int i = 0, ilen = s.length();i < ilen; i++){
                if(s[i]=='M') sum += 1000;
                if(s[i]=='D') sum += 500;
                if(s[i]=='C') sum += 100;
                if(s[i]=='L') sum += 50;
                if(s[i]=='X') sum += 10;
                if(s[i]=='V') sum += 5;
                if(s[i]=='I') sum += 1;
                if(i == ilen - 1) {
                    break;
                }
                if((s.substr(i, 2) == "IV")) {
                    sum -= 2;
                    continue;
                }
                if((s.substr(i, 2) == "IX")) {
                    sum -= 2;
                    continue;
                }
                if((s.substr(i, 2) == "XL")) {
                    sum -= 20;
                    continue;
                }
                if((s.substr(i, 2) == "XC")) {
                    sum -= 20;
                    continue;
                }
                if((s.substr(i, 2) == "CD")) {
                    sum -= 200;
                    continue;
                }
                if((s.substr(i, 2) == "CM")) {
                    sum -= 200;
                    continue;
                }
            }
            return sum;
        }
    };

整数转罗马字符串

解法一

  • 题目限定的输入是1-3999，所以最简单粗暴的方法就是枚举，把数字的个十百千位分别表示成罗马数字，然后拼接

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution {
    public:
        string intToRoman(int num) {
            string ret = "";
            string ge[10] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
            string shi[10] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
            string bai[10] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
            string qian[4] = {"", "M", "MM", "MMM"};
            return qian[num / 1000] + bai[(num % 1000) / 100] + shi[(num % 100) / 10] + ge[(num % 10)];
        }
    };

  • 这种解法的弊端在于需要的空间有点大

解法二

  • 与第一种一样都采用枚举的方式，而且都有表示范围的限制，但是看起来没那么粗暴，运行时间仿佛也稍快一点
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        string intToRoman(int num) {
            string ret = "";
            int v[13] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
            string str[13] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
            for(int i = 0; num > 0;) {
                if(num >= v[i]) {
                    ret += str[i];
                    num -= v[i];
                } else {
                    i++;
                }
            }
            return ret;
        }
    };