0012. Integer to Roman ====================== 题目信息 -------- :题号: 0012. 整数转罗马数字 :难度: Medium :主题: 字符串、查表、贪心 :原题: `LeetCode 0012 `_ :重点: 先确定每个十进制位的唯一规范模板,再把四组模板展开为降序罗马单位表 题目重述 -------- 给定范围 ``[1, 3999]`` 内的整数 ``num``,返回它的规范罗马数字表示。 七个基本符号为 ``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``。 减法只能发生在同一个十进制位内。例如 ``49`` 由 ``40`` 和 ``9`` 分别转换为 ``XL`` 与 ``IX``,结果是 ``XLIX``,不能跨越十位和个位写成 ``IL``。 自建示例 -------- * 普通加法形式:``num = 58``,分解为 ``50 + 8``,返回 ``"LVIII"``; * 多个减法组合:``num = 2944``,分解为 ``2000 + 900 + 40 + 4``,返回 ``"MMCMXLIV"``; * 每一位都是 9:``num = 999``,返回 ``"CMXCIX"``; * 禁止跨位减法:``num = 49``,返回 ``"XLIX"``; * 最小值:``num = 1``,返回 ``"I"``; * 最大值:``num = 3999``,返回 ``"MMMCMXCIX"``。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: std::string byDecimalPlaces(int num) { static const std::array thousands{"", "M", "MM", "MMM"}; static const std::array hundreds{ "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" }; static const std::array tens{ "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" }; static const std::array ones{ "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" }; return thousands[num / 1000] + hundreds[num / 100 % 10] + tens[num / 10 % 10] + ones[num % 10]; } std::string greedyUnits(int num) { static const std::array values{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}; static const std::array symbols{ "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" }; std::string result; for (int index = 0; index < static_cast(values.size()); ++index) { while (num >= values[index]) { result += symbols[index]; num -= values[index]; } } return result; } public: std::string intToRoman(int num) { return greedyUnits(num); } }; 题解 ---- 单个数位 ~~~~~~~~ 罗马数字的规范规则可以先缩小到一个十进制位。设当前位的 ``1``、``5``、``10`` 单位分别记为 ``one``、``five``、``ten``,数字 ``0`` 到 ``9`` 的结构固定为: .. code-block:: text 0 -> "" 1..3 -> one 重复 1..3 次 4 -> one + five 5..8 -> five + one 重复 0..3 次 9 -> one + ten 个位使用 ``I``、``V``、``X``,十位使用 ``X``、``L``、``C``,百位使用 ``C``、``D``、``M``。 千位在题目范围内只需要重复 ``M`` 零到三次。 因此每个十进制位都有唯一的规范文本,并且各位从高到低直接连接即可。``byDecimalPlaces`` 把这四组局部结果 完整列成表,分别取出千位、百位、十位和个位后完成连接。 减法单位 ~~~~~~~~ 若转换过程只认识七个基本符号,``4`` 会被拆成 ``IIII``,``9`` 会被拆成 ``VIIII``,与上面的规范模板 冲突。``IV`` 和 ``IX`` 不是输出完成后的修补规则,而是个位模板中的完整单位。 同理,``XL``、``XC``、``CD``、``CM`` 也必须与普通符号一起参与选择。加入这六项后,完整单位表为: .. code-block:: text 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 这张表只是把千、百、十、个位的局部模板按数值降序展开,并没有引入新的罗马数字规则。 最大单位 ~~~~~~~~ ``greedyUnits`` 从最大单位开始,只要当前剩余值能够容纳该单位,就追加对应符号并扣除它。 这里的正确性不是来自“任意数值单位都可以使用最大值贪心”,而是来自已经确定的数位模板。对任意一个数位: * 数字为 ``9`` 时,规范前缀必须是该位的 ``9`` 单位; * 数字位于 ``5`` 到 ``8`` 时,必须先使用 ``5`` 单位,再追加若干 ``1`` 单位; * 数字为 ``4`` 时,必须使用 ``4`` 单位; * 数字位于 ``0`` 到 ``3`` 时,只使用对应数量的 ``1`` 单位。 降序表的访问顺序恰好执行这四种情况。一个数位处理完成后,剩余值不足以再次使用该位的更大单位,循环自然 进入下一十进制位,因此不会产生跨位减法或非法重复。 例如 ``2944`` 的选择顺序是: .. code-block:: text 2944 -> M -> 1944 1944 -> M -> 944 944 -> CM -> 44 44 -> XL -> 4 4 -> IV -> 0 连接得到 ``MMCMXLIV``,与按位模板 ``2000 + 900 + 40 + 4`` 完全一致。 代码演进 ~~~~~~~~ ``byDecimalPlaces`` 直接保存每个数位的十种规范结果,转换时只做四次索引。它最清楚地展示了规则来源, 但百位、十位和个位三张表具有相同结构。 ``greedyUnits`` 把这些重复模板压缩成十三个合法单位。四次独立查表被替换为同一个降序循环;每次追加的符号 都是当前数位规范模板的下一个片段。 公开入口采用 ``greedyUnits``。它比按位表更紧凑,同时保留了规范表示从高位到低位生成的顺序。 复杂度分析 ~~~~~~~~~~ 题目把输入限制在 ``[1, 3999]``,十进制位数、单位表长度和输出长度都有常量上界,因此两种方法的时间与 工作空间都可记为 ``O(1)``。不计返回字符串,贪心实现只维护剩余整数、单位下标和结果构造状态。