2020-04-24 b4396e699cb01d51e0b991ae2a299015 99+ 3 分钟 0.5 k 0次访问

leetcode-整数转罗马数字及罗马数字转整数

罗马数字是欧洲在阿拉伯数字（实际上是印度数字）传入之前使用的一种数码，是古罗马使用的记数系统。它的产生晚于中国甲骨文中的数码，更晚于埃及人的十进制数字。但是，它的产生标志着一种古代文明的进步。

整数转罗马数字

一、题目

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

罗马数字与阿拉伯数字对应表

罗马数字	阿拉伯数字
M	1000
CM	900
D	500
CD	400
C	100
XC	90
L	50
XL	40
X	10
IX	9
V	5
IV	4
I	1

例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例 1:

输入: 3
输出: “III”
示例 2:

输入: 4
输出: “IV”
示例 3:

输入: 9
输出: “IX”
示例 4:

输入: 58
输出: “LVIII”
解释: L = 50, V = 5, III = 3.
示例 5:

输入: 1994
输出: “MCMXCIV”
解释: M = 1000, CM = 900, XC = 90, IV = 4.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-to-roman

二、思路一

暴力匹配

题目限制输入的数字在1 ~ 3999之间，所以数字最多有四位，分别是千、百、十、个位。转换时，从左到右依次转换。

三、代码实现

// 解法一 暴力匹配
func intToRoman(num int) string {
	// 将每个数位枚举出
	M := []string{"", "M", "MM", "MMM"}                                       // 1000, 2000, 3000 对应的是阿拉伯数字千分位
	C := []string{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"} // 100 ~ 900
	X := []string{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"} // 10 ~ 90
	I := []string{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"} // 1 ~ 9
	return M[num/1000] + C[(num/100)%10] + X[(num/10)%10] + I[(num%10)]
}

四、思路二

贪心法

可以构造一个字典，将阿拉伯数字和罗马数字对应起来。每次都从罗马数字中，选取一个最大的罗马数字，去分解这个整数，目的就是让分解的整数的个数尽可能的少。

五、代码实现

// 解法二 贪心法
func intToRoman1(num int) string {
	digits := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
	romans := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
	res := ""
	for i := 0; i < len(digits); i++ {
		for num >= digits[i] {
			num -= digits[i]
			res += romans[i]
		}
	}
	return res
}

参考

罗马数字转整数

一、思路

转换时是从最低位开始，从左到右转换，把一个小值放在大值的左边，就是做减法，否则做加法。

罗马数字由 I、V、X、L、C、D、M 构成；
当小值在大值的左边，则减小值，如 IV=5-1=4
当小值在大值的右边，则加小值，如 VI=5+1=6

二、代码实现

func romanToInt(s string) int {
	// 一个hashmap或者map存储罗马数字与对应阿拉伯数字的对应关系
	res := 0

	hashmap := map[byte]int{
		'I': 1,
		'V': 5,
		'X': 10,
		'L': 50,
		'C': 100,
		'D': 500,
		'M': 1000,
	}

	// 从右往左遍历字符转换
	pre := 0
	for i := len(s) - 1; i >= 0; i-- {
		cur := hashmap[s[i]]
		sign := 1
		// 如果小数在大数的旁边，需减去小数，如IV
		if cur < pre {
			sign = -1
		}
		res += sign * cur
		pre = cur
	}

	return res
}