12.整型to罗马数字

题目

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value

I 1

V 5

X 10

L 50

C 100

D 500

M 1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

1
2
Input: 3
Output: "III"

Example 2:

1
2
Input: 4
Output: "IV"

Example 3:

1
2
Input: 9
Output: "IX"

Example 4:

1
2
3
Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 5:

1
2
3
Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

分析

我们将每一个罗马字母与相对象的数字存放在两个数组中，因为限制了输入本身的整型数字大小，所以我们直接依次除以每一位代表的整数，注意4和9这两个数有特殊的逻辑编写方式。综合考虑，逻辑是

  • 从高位开始除以罗马数字M->I，（设当前罗马位为$\alpha$）得到结果x
  • 如果x小于4，说明可以用该位的罗马数字重复表示（$\alpha*n$）（例如，3000就是MMM）
  • 如果x等于4，那就是$\alpha-1,\alpha$（例如IV）
  • 如果x大于4小于九，那就是$\alpha，\alpha*n$（例如VIII）
  • 如果x等于9，便是$\alpha-2，\alpha$（例如IX）
  • 取余，继续迭代

其实，这个动手稍微算一下，总结一下规律，还是比较好明白这里面的逻辑规律的，只是用眼看反而不容易看出来。

但是我们还有一种算法，简化代码，首先，不觉得把4和9单独拿出来判断过于繁琐了么，干脆就把所有的4和9的情况也写进数组，这样就完全依靠数组来来判断，而不需要再写那么多else if，看起来很麻烦。这里其实是一个很简单的贪婪算法，既然这里谈到了贪心算法，我们不如就来了解一下

贪心算法

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止

其实可以发现，贪心算法的优点在于代码简洁，比较傻瓜，但是不一定是最优解。但是此题我们不需要考虑最优解这个问题，在这道题的应用，即我们只考虑当前最高位，检测当前最高位是否大于我们数组中预设的最高位，如果是，则减去最高位，并且字符串添加一次最高位，因为数组中设置了4和9，我们也不用担心4被忽略

代码

一般解法

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:
    string intToRoman(int num) {
        string res = "";
        char roman[] = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};
        int value[] = {1000, 500, 100, 50, 10, 5, 1};
        for (int n = 0; n < 7; n += 2) {
            int x = num / value[n];
            if (x < 4) {
                for (int i = 1; i <= x; ++i) 
                    res += roman[n];
            } 
            else if (x == 4) 
                res = res + roman[n] + roman[n - 1];
            else if (x > 4 && x < 9) {
                res += roman[n - 1];
                for (int i = 6; i <= x; ++i) 
                    res += roman[n];
            }
            else if (x == 9) 
                res = res + roman[n] + roman[n - 2];
            num %= value[n];            
        }
        return res;
    }
};

贪婪算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string intToRoman(int num) {
        string res = "";
        vector<int> val{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        vector<string> str{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        for (int i = 0; i < val.size(); ++i) {
            while (num >= val[i]) {
                num -= val[i];
                res += str[i];
            }
        }
        return res;
    }
};

13.罗马数字to整型

示例 1:

1
2
输入: "III"
输出: 3

示例 2:

1
2
输入: "IV"
输出: 4

示例 3:

1
2
输入: "IX"
输出: 9

示例 4:

1
2
3
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

1
2
3
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

Follow up:
Coud you solve it without converting the integer to a string?

分析

提示：

  1. 相同的数字连写，所表示的数等于这些数字相加得到的数，如：Ⅲ = 3；
  2. 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数， 如：Ⅷ = 8；Ⅻ = 12；
  3. 小的数字，（限于Ⅰ、X 和C）在大的数字的左边，所表示的数等于大数减小数得到的数，如：Ⅳ= 4；Ⅸ= 9；
  4. 正常使用时，连写的数字重复不得超过三次。（表盘上的四点钟“IIII”例外）
  5. 在一个数的上面画一条横线，表示这个数扩大1000倍。

有几条须注意掌握：

  1. 基本数字Ⅰ、X 、C 中的任何一个，自身连用构成数目，或者放在大数的右边连用构成数目，都不能超过三个；放在大数的左边只能用一个。
  2. 不能把基本数字V 、L 、D 中的任何一个作为小数放在大数的左边采用相减的方法构成数目；放在大数的右边采用相加的方式构成数目，只能使用一个。
  3. V 和X 左边的小数字只能用Ⅰ。
  4. L 和C 左边的小数字只能用X。
  5. D 和M 左边的小数字只能用C。

而这道题好就好在没有让我们来验证输入字符串是不是罗马数字，这样省掉不少功夫。我们需要用到map数据结构，来将罗马数字的字母转化为对应的整数值，因为输入的一定是罗马数字，那么我们只要考虑两种情况即可：

第一，如果当前数字是最后一个数字，或者之后的数字比它小的话，则加上当前数字

第二，其他情况则减去这个数字

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int romanToInt(string s) {
        int res = 0;
        unordered_map<char, int> m{{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
        for (int i = 0; i < s.size(); ++i) {
            int val = m[s[i]];
            if (i == s.size() - 1 || m[s[i+1]] <= m[s[i]]) res += val;
            else res -= val;
        }
        return res;
    }
};

个人总结

这两道题虽然题目很一样，但是所采用的逻辑结构是完全不一样的。整型转化成罗马数字所采用的是数字拆分，我们可以选择像7&9一样的除法提取每一位，但是由于罗马数字的特殊逻辑，需要再判断中添加循环，来重复打印；而像方法2选择减法拆分直接将循环充分利用，很是巧妙。

第二道题则利用了map的对应关系，当然这个也可以将4和9考虑进来，只不过对程序的化简起不到太大作用，（采用4和9仍要判断是否要判断下一位）。