- 题目描述
- 题目理解
- 我的代码
- 总结
题目描述
题目的描述如下图所示，其链接见：罗马数字转整数。
我是按照从左往右读罗马数字的，发现一般的罗马数字，一个就代表一位，但是有特殊的六种两个字母组合，必须组合起来读。这些内容就是我第一次分析出来的模式（有点pattern recognition的感觉在里面）。
所以第一次写的算法就是从左往右读，读了1位就踢掉这1位，读了2位就踢掉2位，把相应的数值加起来，判断剩下的字符串是否为空，如果为空就结束，不空就继续。
class Solution:
def romanToInt(self, s: str) -> int:
n = 0
while(s!=''):
if len(s) == 1:
if s == 'I':
n += 1
elif s == 'V':
n += 5
elif s == 'X':
n += 10
elif s == 'L':
n += 50
elif s == 'C':
n += 100
elif s == 'D':
n += 500
else:
n += 1000
s = s[1:]
else:
if s[0:2] == 'IV':
n += 4
s = s[2:]
elif s[0:2] == 'IX':
n += 9
s = s[2:]
elif s[0:2] == 'XL':
n += 40
s = s[2:]
elif s[0:2] == 'XC':
n += 90
s = s[2:]
elif s[0:2] == 'CD':
n += 400
s = s[2:]
elif s[0:2] == 'CM':
n += 900
s = s[2:]
else:
if s[0] == 'I':
n += 1
elif s[0] == 'V':
n += 5
elif s[0] == 'X':
n += 10
elif s[0] == 'L':
n += 50
elif s[0] == 'C':
n += 100
elif s[0] == 'D':
n += 500
elif s[0] == 'M':
n += 1000
s = s[1:]
return n
可以看到整个代码非常的冗长，大眼一扫，就知道肯定不怎么滴，所以也就不怎么细说了。
所以，我又接着想了第二种实现过程，如果利用字典，把这些罗马字母对应的数值以键值对的方式存储在字典里，这样每次调用就很方便了。所以我的这个第二个代码就很简洁明了：判断当前字符串是否为空，不为空时，直接判断它的前两位，即s[0:2]是否在字典中，这里有一个小技巧，就是不用再判断它的长度是否有两位以上，如果长度不足两位，它自然就被分到else里了。然后就是利用字符串的切片操作，踢掉已经考虑过的字母，接着进入下一次循环中。
class Solution:
def romanToInt(self, s: str) -> int:
n = 0
re = dict()
re['I'] = 1
re['V'] = 5
re['X'] = 10
re['L'] = 50
re['C'] = 100
re['D'] = 500
re['M'] = 1000
re['IV'] = 4
re['IX'] = 9
re['XL'] = 40
re['XC'] = 90
re['CD'] = 400
re['CM'] = 900
# re = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000, 'IV':4,
# 'IX':9, 'XL':40, 'XC':90, 'CD':400, 'CM':900}
while(s!=''):
if s[0:2] in re:
n += re[s[0:2]]
s = s[2:]
else:
n += re[s[0]]
s = s[1:]
return n
这一次代码的运行结果就很好，结果如下图：
啊哈哈哈哈~~~，这个结果比它的官方代码的结果还要好，所以在这里就不说它的做法了。
另外，我在讨论区，看到了一种解法，我觉得特别好，是我所没有想到的，所以在这里也说一下。就是，罗马数字字母排列的模式里，特别的六种组合，都是小数字排在了大数字的左边，但是正常情况下，都是左边的字母所代表的数字更大。这是一个非常特殊的模式，正好可以利用这个模式来进行判断，如果当前位比右边一位更大，那么当前位直接读就好了；如果当前位比右边位要小，那么说明他俩是一个组合，对于这个组合，当前位的读取是要做减法；然后循环至下一位。
以上算法可由LeetCode用户pony Ma的代码实现如下：
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
dct = {'M':1000,'D':500,'C':100,'L':50,'X':10,'V':5,'I':1}
i,res = 0,0
while i < len(s)-1:
if dct[s[i]] < dct[s[i+1]]:
res -= dct[s[i]]
else:
res += dct[s[i]]
i += 1
return res+dct[s[-1]]
总结
尽可能多的挖掘出计算流程，数据本身所具有的某种模式和特点，挖掘的越多，并把这些模式和特点利用起来，当然，再结合一些特定的数据结构，就会编写出越来越棒的算法程序了！
