12. 整数转罗马数字 - 《leetcode》

">
解题思路：
PHP代码实现：
GO代码实现：

解题思路：

罗马数字计数方法：
    1. 相同的数字连写，所表示的数等于这些数字相加得到的数，如：III=3；
    2. 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，如：VIII=8, XII=12；
    3. 小的数字在大的数字的左边（限于 IV、IX、XL、XC、CD和CM），所表示的数等于大数减小数得到的数，如：IV=4, IX=9；
    4. 正常使用时，连写的数字重复不得超过三次；

我们可以将所有减法操作看做一个整体，当成一种新的单位。从大到小整理所有单位得到

M	CM	D	CD	C	XC	L	XL	X	IX	V	IV	I
1000	900	500	400	100	90	50	40	10	9	5	4	1

我们可以将目标整数看成这些单位值的加和，且同一种单位不能使用超过3次,所以我们尽可能优先使用值较大的单位即可。

PHP代码实现：

class Solution {
    /**
     * @param Integer $num
     * @return String
     */
    function intToRoman($num) {
        $value = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
        $str = ['M', 'CM', 'D', 'CD', 'C',
                'XC', 'L', 'XL', 'X',
                'IX', 'V', 'IV', 'I'];
        $roman = '';
        for ($i = 0; $i < count($value); $i ++) {
            while ($num >= $value[$i]) {
                $num -= $value[$i];
                $roman .= $str[$i];
            }
        }
        return $roman;
    }
}

GO代码实现：

func intToRoman(num int) (roman string) {
    values := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
    str := []string{"M", "CM", "D", "CD", "C",
        "XC", "L", "XL", "X", "IX",
        "V", "IV", "I"}
    for i:= 0; i < len(values); i++ {
        for num >= values[i] {
            num -= values[i];
            roman += str[i]
        }
    }
    return
}