1.算法12 整数转罗马数字

我自己的解法：

要做这一题首先得理解罗马数字的排列规则，看字符-数值的对照表其实很容易明白，总结起来就一句话“不够就向下取一个”。比如1934这个数字。 >=1000,那么取一个M，1934-1000 = 934 > 500 且 < 1000，不够一个M，那么取一个D，934-500 = 434.....最后我们得到MDCCCCXXXIIII，显然太长了不方便书写，我们把像DDDD,IIII这种四个并列的进行整合，但是这只是处理的数字4的情况，对于数字9，我们同样能发现规律：它们像“汉堡包”。

于是步骤就很明显了
1.我们需要先把1934转成MDCCCCXXXIIII，依赖字符-数值的对照表即可（可能需要用Map保存这张表。）
2.第一遍检查：把像DDDD,IIII这种四个并列的进行整合。
3.第二遍检查：把像DCD这种“汉堡包”进行整合。（这其实是在处理数字9的情况）

代码是可以实现的，但是这等于把一道题分成了三道题来解，代码太长，没脸展示。首先理解罗马数字的排列规律即可。

官方解法

接下来是官方解法，我尽量简单解释思路：
1.贪心：
回到题目，首先我们发现，罗马数字的规则：
规则一：是字符-数值表，如果只有这个那么问题十分简单。
规则二：但是还有4和9数字的特殊处理，因此显得比较头疼。
但是，二者结合发现一个关键点：可能性是有限、且数量不算特别多的。
将规则二结合到规则一，我们能得到一张更确切的表：

注意，还是那句话：“不够就向下取一个”，我们肯定是从1000,900,500....这样的顺序，从大到小分解我们的数字，那么第一层for循环肯定是遍历1000,900,500....，不够时就取下一个更小的数。这样，任何普通数字都能转化成罗马数字。

int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};    
String[] symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

public String intToRoman(int num) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < values.length && num >= 0; i++) {
        while (values[i] <= num) {
            num -= values[i];
            sb.append(symbols[i]);
        }
    }
    return sb.toString();
}

能学到什么？

我并不关心罗马数字到底是怎样。刷leecode并不是为了做各种脑筋急转弯，而是希望初步认识一些算法，锻炼我用计算机的思维方式想问题，并且写出更高效、更好的代码。

1.关于贪心算法：贪心是指一旦找到合适的解，就立刻输出，不追求找到最优解，或者说，明确知道找到的第一个解肯定是最优解/唯一解，那么这就符合“贪心”的场景。