Roman to Integer && Integer to Roman 解答

Roman Numeral Chart

V:5  X:10  L:50  C:100  D:500  M:1000

规则:

1. 重复次数表示该数的倍数
2. 右加左减:
较大的罗马数字右边记上较小的罗马数字,表示大数字加小数字
较小的罗马数字右边记上较大的罗马数字,表示大数字减小数字
左减的数字有限制,仅限于I, X, C
左减时不可跨越一个位数。如,99不可以用IC(100 - 1)表示,而是XCIX(100 - 10 + 10 - 1)
左减数字必需为一位
右加数字不可连续超过三位

Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

基本思路是每次比较当前字母和它下一个字母,如果是increasing order,说明当前字母的符号是减号,如果是decreasing order,说明当前字母的符号是加号。

 1 class Solution(object):
 2     def romanToInt(self, s):
 3         """
 4         :type s: str
 5         :rtype: int
 6         """
 7         result = 0
 8         my_map = {'I':1, 'V':5, 'X':10,'L':50, 'C':100, 'D':500, 'M':1000}
 9         for i in range(len(s) - 1):
10             if (my_map[s[i]] - my_map[s[i + 1]]) >= 0:
11                 result += my_map[s[i]]
12             else:
13                 result -= my_map[s[i]]
14         result += my_map[s[len(s) - 1]]
15         return result

Integer to Roman

根据规则,可以用递归和非递归的方法解答。

注意到规则,跨越的位数不可超过一位。

 1 public class Solution {
 2     public String intToRoman(int num) {
 3         if (num >= 1000) { return "M" + intToRoman(num - 1000); }
 4         if (num >= 900) { return "CM" + intToRoman(num - 900); }
 5         if (num >= 500) { return "D" + intToRoman(num - 500); }
 6         if (num >= 400) { return "CD" + intToRoman(num - 400); }
 7         if (num >= 100) { return "C" + intToRoman(num - 100); }
 8         if (num >= 90) { return "XC" + intToRoman(num - 90); }
 9         if (num >= 50) { return "L" + intToRoman(num - 50); }
10         if (num >= 40) { return "XL" + intToRoman(num - 40); }
11         if (num >= 10) { return "X" + intToRoman(num - 10); }
12         if (num >= 9) { return "IX" + intToRoman(num - 9); }
13         if (num >= 5) { return "V" + intToRoman(num - 5); }
14         if (num >= 4) { return "IV" + intToRoman(num - 4); }
15         if (num >= 1) { return "I" + intToRoman(num - 1); }
16         return "";
17     }
18 }

循环改为非递归

 1 public class Solution {
 2     public String intToRoman(int num) {
 3         String result = "";    
 4         String [] symbol = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};    
 5         int [] value = {1000,900,500,400, 100, 90,  50, 40,  10, 9,   5,  4,   1};   
 6         for(int i=0;num!=0;i++){  
 7             while(num >= value[i]){  
 8                 num -= value[i];  
 9                 result += symbol[i];  
10             }  
11         }  
12         return result; 
13     }
14 }
原文地址:https://www.cnblogs.com/ireneyanglan/p/4935322.html