LeetCode

LeetCode-12&13-整数与罗马数字相互转化

Posted by 刘知安 on 2018-11-15
文章目录
  1. 说明
    1. 字典是存放顺序与你输入的顺序是不一样的！！！迭代读取的时候一定要小心！！！！！
      1. 描述
      2. 示例1：
      3. 示例2：
      4. 示例3：
      5. 示例4：
      6. 示例5：
    2. 思路
  2. Code
  3. 疑问
    1. 修改
    2. 另：罗马数字转整数，思路几乎一样，就是预定义字典的顺序改变一下。

说明

如果你在写这个程序的时候，发现你在IDE上运行结果完全正确，而在网站上总是Wrong Answer，恭喜你，这将让你倍涨经验（起码我找了很久才发现这个问题）

字典是存放顺序与你输入的顺序是不一样的！！！迭代读取的时候一定要小心！！！！！

下面讲下经过。。。

描述

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

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 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：

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

示例2：

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

示例3：

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

示例4：

1
2
3
输入: 58
输出: "LVIII"
解释: C = 100, L = 50, XXX = 30, III = 3.

示例5：

1
2
3
输入: 58
输出: "LVIII"
解释: C = 100, L = 50, XXX = 30, III = 3.

思路

乍一看，什么放左边放右边，有点凌乱的感jio，我们不妨把所有罗马数字的“基数”都给它罗列出来（当然是用字典了），一共有以下这些“基数”。
这里的字典一定要按照基数值从大到小的顺序排列 ,就好比我们从高位到低位写一个数字，总是从高位写到低位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
dict_roma = {
	3000: 'MMM',
	2000: 'MM',
	1000: 'M',
	900: 'CM',
	500: 'D',
	400: 'CD',
	300: 'CCC',
	200: 'CC',
	100: 'C',
	90: 'XC',
	50: 'L',
	40: 'IL',
	30: 'XXX',
	20: 'XX',
	10: 'X',
	9: 'IX',
	5: 'V',
	4: 'IV',
	3: 'III',
	2: 'II',
	1: 'I',
}

然后再逐个去除基数，看有没有商（够不够除），一旦够除，商肯定也只能是1，这里用到了defaultdict(int)这个标准库中的字典，方便统计数量。

最后再根据统计的情况生成最终结果字符串即可。

Code

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
46
47
48
49
50
51
from collections import defaultdict


class Solution:
	def intToRoman(self, num):
		"""
		:type num: int
		:rtype: str
		"""
		# 这里的预定义字典一定要从数值大道数值小排列
		dict_roma = {
			3000: 'MMM',
			2000: 'MM',
			1000: 'M',
			900: 'CM',
			500: 'D',
			400: 'CD',
			300: 'CCC',
			200: 'CC',
			100: 'C',
			90: 'XC',
			50: 'L',
			40: 'IL',
			30: 'XXX',
			20: 'XX',
			10: 'X',
			9: 'IX',
			5: 'V',
			4: 'IV',
			3: 'III',
			2: 'II',
			1: 'I',
		}

		num_dict = defaultdict(int)
		for key in dict_roma.keys():
			if int(num / key) != 0:
				num_dict[key] += 1
				num -= key
			# 查找完了，提前退出，后面的key无需再试探
			if num == 0:
				break
		result = ""
		for key, value in num_dict.items():
			if value != 0:
				result += dict_roma[key]

		return result

s = Solution()
print(s.intToRoman(4))

疑问

我在pycharm中运行程序，完全没问题，输入4时，输出为IV
这里写图片描述

可是在LeetCode跑起来，就是说我输入4的时候输出错误
这里写图片描述

我也是醉了，不知道是哪里的问题，真的想了很久很久。于是乎，我又遇到了
罗马数字转整数这个题，也出现了类似的错误，百度了一下，并没有找到什么相关答案。我灵机一动，是不是和字典的“无序性”有关？呵呵。。果然是这样

修改

上面说道，我用了defaultdict这个工具，实验证明，它也是无序的。于是我干脆自己统计好了（省去defaultdict提供的便利），用了两个OrderedDict(),关于OrderedDict()大家自行百度，我这里说明一下它的一个特别之处。

一般字典取value，我们肯定是dictionary[key]这样，但是在OrderedDict()中，dictionary[key]返回的是一个元组，所以取出具体值需要这样操作——
dictionary[key][0],ok，代码如下：

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
46
47
48
49
50
51
52
from collections import defaultdict
from collections import OrderedDict


class Solution:
	def intToRoman(self, num):
		"""
		:type num: int
		:rtype: str
		"""
		# 这里的预定义字典一定要从数值大道数值小排列
		dict_roma = OrderedDict()
		dict_roma['3000'] = 'MMM',
		dict_roma['2000'] = 'MM',
		dict_roma['1000'] = 'M',
		dict_roma['900'] = 'CM',
		dict_roma['500'] = 'D',
		dict_roma['400'] = 'CD',
		dict_roma['300'] = 'CCC',
		dict_roma['200'] = 'CC',
		dict_roma['100'] = 'C',
		dict_roma['90'] = 'XC',
		dict_roma['50'] = 'L',
		dict_roma['40'] = 'XL',
		dict_roma['30'] = 'XXX',
		dict_roma['20'] = 'XX',
		dict_roma['10'] = 'X',
		dict_roma['9'] = 'IX',
		dict_roma['5'] = 'V',
		dict_roma['4'] = 'IV',
		dict_roma['3'] = 'III',
		dict_roma['2'] = 'II',
		dict_roma['1'] = 'I'

		num_dict = OrderedDict()
		for key in dict_roma.keys():
			if int(num / int(key)) != 0:
				# 如果计数字典中存在这个键
				if key in num_dict:
					num_dict[key] += 1
				else:
					num_dict[key] = 1
				num -= int(key)
			# 查找完了，提前退出，a后面的key无需再试探
			if num == 0:
				break
		result = ""
		for key, value in num_dict.items():
			if value != 0:
				result += dict_roma[key][0]

		return result

另：罗马数字转整数，思路几乎一样，就是预定义字典的顺序改变一下。

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
46
47
48
49
from collections import OrderedDict


class Solution:
	def romanToInt(self, s):
		"""
		:type s: str
		:rtype: int
		"""
		# 这里的预定义字典一定要从数值大道数值小排列
		dict_roma = OrderedDict()
		dict_roma['CM'] = 900,
		dict_roma['CD'] = 400,
		dict_roma['XC'] = 90,
		dict_roma['XL'] = 40,
		dict_roma['IX'] = 9,
		dict_roma['IV'] = 4,
		dict_roma['MMM'] = 3000,
		dict_roma['MM'] = 2000,
		dict_roma['M'] = 1000,
		dict_roma['D'] = 500,
		dict_roma['CCC'] = 300,
		dict_roma['CC'] = 200,
		dict_roma['C'] = 100,
		dict_roma['L'] = 50,
		dict_roma['XXX'] = 30,
		dict_roma['XX'] = 20,
		dict_roma['X'] = 10,
		dict_roma['V'] = 5,
		dict_roma['III'] = 3,
		dict_roma['II'] = 2,
		dict_roma['I'] = 1,

		base_list = list(dict_roma.keys())
		result = 0
		for item in base_list:
			try:
				base_index = s.index(item)
				num = dict_roma[item][0]
				result += num
				# 如果从头匹配到
				if base_index == 0:
					s = s[len(item) + base_index:]
				# 如果在中间匹配到
				else:
					s = s[:base_index] + s[len(item) + base_index:]
			except ValueError as e:
				continue
		return result
FEATURED TAGS
LeetCode
FRIENDS