012. Integer to Roman.md

###12. Integer to Roman

题目: https://leetcode.com/problems/integer-to-roman/

难度: Medium

思路：

首先我学习了一下罗马字母是如何表示的。然后感慨，这个阿拉伯数字是多么好的发明

上图

基于的是这些个Symbol：

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

组合是这种方式

1		2		3		4		5		6		7		8		9
I   	II		III		IV		V		VI		VII		VIII	IX
10		20		30		40		50		60		70		80		90
X		XX		XXX		XL		L		LX		LXX		LXXX	XC
100		200		300		400		500		600		700		800		900
C		CC		CCC		CD		D		DC		DCC		DCCC	CM

可以看出来，这个进位或者组合是4和9的地方进位的，比如4是加上了I然后到V，9是加上了I到X。所以题目要限制数字在1-3999之间。

然后就去谷歌罗马数字最大能表示多少，看到了一个更好的总结，不过是可以更大的，数字上面加bar.

via http://www.cnblogs.com/cacique/archive/2012/02/23/2364377.html

下面是几个通常的规则来构成罗马数字：

• 大部分时候用字符相叠加来表示数字。I是1， II是2， III是3。VI是6（挨个看来，是“5 和 1”的组合），VII是7，VIII是8。
• 含有10的字符（I，X，C和M）最多可以重复出现三个。为了表示4，必须用同一位数的下一个更大的数字5来减去一。不能用IIII来表示4，而应该是IV（意思是比5小1）。40写做XL（比50小10），41写做XLI，42写做XLII，43写做XLIII，44写做XLIV（比50小10并且比5小1）。
• 有些时候表示方法恰恰相反。为了表示一个中间的数字，需要从一个最终的值来减。比如：9需要从10来减：8是VIII，但9确是IX（比10小1），并不是VIII（I字符不能重复4次）。90是XC，900是CM。
• 表示5的字符不能在一个数字中重复出现。10只能用X表示，不能用VV表示。100只能用C表示，而不是LL。
• 罗马数字是从左到右来计算，因此字符的顺序非常重要。DC表示600，而CD完全是另一个数字400（比500小100）。CI是101，IC不是一个罗马数字（因为你不能从100减1，你只能写成XCIX，表示比100小10，且比10小1）。

规则总结：  左减右加    加减时位数和被加减数相差位数最大为一（两位数可加减一位数 三位数只能加减两位数）  从左向右计数

所以想着4，9这块需要特殊处理一下，但是看到了一个很棒的算法

AC代码

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        lookup = {'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}
        romanSt = ''

        for symbol, val in sorted(lookup.items(), key = lambda t: t[1], reverse = True):
        	while num >= val:
        		romanSt += symbol
        		num -= val
        return romanSt

因为dict本身是无序的，这里做了一个逆向排序的操作(否则可能会出现IIII这种状况)，每次找到余下的最大的值，然后慢慢来生成我们的romanStr。