12.md

✏️Leetcode之PHP版题目解析（12. Integer to Roman)

2019-02-09 吴亲库里 库里的深夜食堂

---

✏️描述

罗马数字由七个不同的符号来表示:I, V, X, L, C, D 和 M。上图给出了符号对应的值。

---

✏️题目实例

​ ****

✏️题目分析

题目的要求是给定一个数字，用对应的字符来表示。题目中给了对应的 demo ，比如2 可以用 II 来表示。12 的话可以用 XII 来表示。可以看到核心思想是尽可能用最大的数来表示(贪心的思想)。然后多出来的再往小的数去补。但是有例外，比如像 4 这个数字，按照上面的说法，应该是 IIII 表示，但是实际上表示的符号应该是 IV 。所以我们可以利用哈希把对应的转换规则存起来，根据这个哈希表，利用贪心思想把给定数匹配最大的数，然后更新给定数，每次拼接匹配到的字符即可

---

✏️暴力超时

 /**
     * @param Integer $num
     * @return String
     */
    function intToRoman($num) {
        $result = '';
        $roman = array(
            '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,
        );
        foreach($roman as $k => $v){
            while(!($num - $v < 0)){
                $num = $num - $v;
                $result .= $k;
            }
        }
        return $result;

    }

---

联系

​