题目概览七个不同的符号代表罗马数字其值如下符号值I1V5X10L50C100D500M1000罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则如果该值不是以 4 或 9 开头请选择可以从输入中减去的最大值的符号将该符号附加到结果减去其值然后将其余部分转换为罗马数字。如果该值以 4 或 9 开头使用减法形式表示从以下符号中减去一个符号例如 4 是 5 (V) 减 1 (I):IV9 是 10 (X) 减 1 (I)IX。仅使用以下减法形式4 (IV)9 (IX)40 (XL)90 (XC)400 (CD) 和 900 (CM)。只有 10 的次方I,X,C,M最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)50 (L) 或 500 (D)。如果需要将符号附加4次请使用减法形式。给定一个整数将其转换为罗马数字。示例 1输入num 3749输出MMMDCCXLIX解释3000 MMM 由于 1000 (M) 1000 (M) 1000 (M) 700 DCC 由于 500 (D) 100 (C) 100 (C) 40 XL 由于 50 (L) 减 10 (X) 9 IX 由于 10 (X) 减 1 (I) 注意49 不是 50 (L) 减 1 (I) 因为转换是基于小数位示例 2输入num 58输出LVIII解释50 L 8 VIII示例 3输入num 1994输出MCMXCIV解释1000 M 900 CM 90 XC 4 IV提示1 num 3999来源12. 整数转罗马数字 - 力扣LeetCode解题分析方法一模拟贪心算法这是最直观和常用的方法。核心思想是每次都尽可能使用当前最大的罗马数字符号来表示剩余的数字。算法步骤预先定义两个数组values[]按从大到小的顺序存储所有可能的“数字值”包括常规符号如 1000, 500, 100...和特殊的减法形式如 900, 400, 90...。symbols[]存储与values[]一一对应的罗马数字字符串。初始化一个结果字符串如StringBuilder。从最大的数字值values[0]开始遍历数组如果当前数字num大于等于values[i]则将对应的symbols[i]追加到结果中并从num中减去values[i]。重复此步骤直到num小于values[i]然后移动到下一个更小的值。当num被减至 0 时转换完成返回结果字符串。为什么可行因为罗马数字的表示规则本质上就是“贪心”的对于任何给定的数字总是优先使用能表示它的最大符号。预定义的数组已经包含了所有必要的减法形式如 IV, IX, XL 等确保了算法能正确处理 4 和 9 相关的边界情况。复杂度分析时间复杂度O(1)。虽然有一个循环但循环次数是固定的数组长度 13与输入num的大小无关。在最坏情况下如 num1内层 while 循环可能执行多次但总操作次数仍有一个很小的常数上界。空间复杂度O(1)。只使用了固定大小的数组和结果字符串。class Solution { // 按从大到小的顺序定义所有可能的“值-符号”对 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 roman new StringBuilder(); // 遍历每一个值 for (int i 0; i values.length; i) { // 当剩余数字大于等于当前值时就使用对应的符号 while (num values[i]) { roman.append(symbols[i]); num - values[i]; } // 如果数字已经减到0可以提前结束非必需优化 if (num 0) { break; } } return roman.toString(); } }代码说明使用StringBuilder来高效构建结果字符串。内层使用while循环确保同一个符号可以连续使用多次例如3000 对应三个 “M”。数组包含了所有必要的减法形式如 900 对应 “CM”因此算法能自动处理 4、9、40、90、400、900 这些情况。提前判断num 0可以提前退出循环是一个小的优化。示例推演num 3749num3749 1000追加 “M”num2749。num2749 1000追加 “M”num1749。num1749 1000追加 “M”num749。此时已得到 “MMM”。num749 900 但 500追加 “D”num249。得到 “MMMD”。num249 400 但 100追加 “C”num149。得到 “MMMDC”。num149 100追加 “C”num49。得到 “MMMDCC”。num49 90 但 40追加 “XL”num9。得到 “MMMDCCXL”。num9 9追加 “IX”num0。得到最终结果 “MMMDCCXLIX”。方法二硬编码这种方法利用了罗马数字表示法的确定性对于给定的整数1 ≤ num ≤ 3999其千位、百位、十位、个位上的数字是确定的且每个数位上的数字0-9对应的罗马数字组合也是固定的。因此我们可以预先为每个数位上的所有可能数字0-9编码好对应的罗马数字字符串然后通过简单的数学运算取出每一位的数字拼接对应的字符串即可。核心思路数位分离将输入整数num分解为千位、百位、十位、个位四个数字。查表映射为每个数位预先定义一个长度为 10 的字符串数组下标 0-9 分别对应数字 0-9 在该数位上的罗马数字表示其中 0 对应空字符串。拼接结果将四个数位对应的罗马数字字符串按顺序千位、百位、十位、个位拼接起来即为最终结果。算法步骤定义四个字符串数组thousands[]千位数字 0-3 对应的罗马数字0 为空字符串1 为 M2 为 MM3 为 MMM。hundreds[]百位数字 0-9 对应的罗马数字例如 0, 1C, 2CC, 3CCC, 4CD, 5D, 6DC, 7DCC, 8DCCC, 9CM。tens[]十位数字 0-9 对应的罗马数字例如 0, 1X, 2XX, 3XXX, 4XL, 5L, 6LX, 7LXX, 8LXXX, 9XC。ones[]个位数字 0-9 对应的罗马数字例如 0, 1I, 2II, 3III, 4IV, 5V, 6VI, 7VII, 8VIII, 9IX。通过整数除法和取余运算获取每一位的数字千位num / 1000百位(num % 1000) / 100或num % 1000 / 100十位(num % 100) / 10或num % 100 / 10个位num % 10根据每一位的数字作为下标从对应的数组中取出罗马数字字符串依次拼接到结果中。返回拼接后的字符串。为什么可行因为罗马数字的表示是按位独立的。千位只由 M 组成百位由 C, D, M 的组合构成十位由 X, L, C 的组合构成个位由 I, V, X 的组合构成。每个数位上的数字 0-9 都有唯一确定的罗马数字表示包括减法形式如 IV, IX, XL, XC, CD, CM且不同数位之间的表示不会相互干扰。因此预先编码所有可能性并查表拼接是完全正确的。复杂度分析时间复杂度O(1)。仅进行固定次数的数学运算除法、取余和字符串拼接操作与输入大小无关。空间复杂度O(1)。使用了四个固定大小的数组总长度 4×1040和一个结果字符串均为常数空间。class Solution { // 千位0-3 对应空字符串、M、MM、MMM String[] thousands {, M, MM, MMM}; // 百位0-9 对应的罗马数字 String[] hundreds {, C, CC, CCC, CD, D, DC, DCC, DCCC, CM}; // 十位0-9 对应的罗马数字 String[] tens {, X, XX, XXX, XL, L, LX, LXX, LXXX, XC}; // 个位0-9 对应的罗马数字 String[] ones {, I, II, III, IV, V, VI, VII, VIII, IX}; public String intToRoman(int num) { // 使用 StringBuffer 或 StringBuilder 进行高效拼接 StringBuffer roman new StringBuffer(); // 获取千位数字并拼接对应字符串 roman.append(thousands[num / 1000]); // 获取百位数字并拼接对应字符串 roman.append(hundreds[num % 1000 / 100]); // 获取十位数字并拼接对应字符串 roman.append(tens[num % 100 / 10]); // 获取个位数字并拼接对应字符串 roman.append(ones[num % 10]); return roman.toString(); } }代码说明数组定义清晰对应每个数位注释说明了每个下标的含义。使用StringBuffer或StringBuilder进行字符串拼接效率高于直接使用操作符。通过简单的除法和取余运算获取每一位的数字代码简洁且易于理解。由于题目限制1 num 3999千位数字范围是 0-3因此thousands数组只需定义 4 个元素。示例推演num 3749千位3749 / 1000 3→thousands[3] MMM百位3749 % 1000 749749 / 100 7→hundreds[7] DCC注意700 是 DCC不是 CC...十位3749 % 100 4949 / 10 4→tens[4] XL个位3749 % 10 9→ones[9] IX拼接MMM DCC XL IX MMMDCCXLIX方法对比贪心模拟法更通用体现了罗马数字的构造规则易于理解和扩展。硬编码法更高效、更直接利用了问题范围的有限性num ≤ 3999代码极其简洁在实际编码竞赛或面试中可能是更优的选择。
JAVA练习369- 整数转罗马数字
题目概览七个不同的符号代表罗马数字其值如下符号值I1V5X10L50C100D500M1000罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则如果该值不是以 4 或 9 开头请选择可以从输入中减去的最大值的符号将该符号附加到结果减去其值然后将其余部分转换为罗马数字。如果该值以 4 或 9 开头使用减法形式表示从以下符号中减去一个符号例如 4 是 5 (V) 减 1 (I):IV9 是 10 (X) 减 1 (I)IX。仅使用以下减法形式4 (IV)9 (IX)40 (XL)90 (XC)400 (CD) 和 900 (CM)。只有 10 的次方I,X,C,M最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)50 (L) 或 500 (D)。如果需要将符号附加4次请使用减法形式。给定一个整数将其转换为罗马数字。示例 1输入num 3749输出MMMDCCXLIX解释3000 MMM 由于 1000 (M) 1000 (M) 1000 (M) 700 DCC 由于 500 (D) 100 (C) 100 (C) 40 XL 由于 50 (L) 减 10 (X) 9 IX 由于 10 (X) 减 1 (I) 注意49 不是 50 (L) 减 1 (I) 因为转换是基于小数位示例 2输入num 58输出LVIII解释50 L 8 VIII示例 3输入num 1994输出MCMXCIV解释1000 M 900 CM 90 XC 4 IV提示1 num 3999来源12. 整数转罗马数字 - 力扣LeetCode解题分析方法一模拟贪心算法这是最直观和常用的方法。核心思想是每次都尽可能使用当前最大的罗马数字符号来表示剩余的数字。算法步骤预先定义两个数组values[]按从大到小的顺序存储所有可能的“数字值”包括常规符号如 1000, 500, 100...和特殊的减法形式如 900, 400, 90...。symbols[]存储与values[]一一对应的罗马数字字符串。初始化一个结果字符串如StringBuilder。从最大的数字值values[0]开始遍历数组如果当前数字num大于等于values[i]则将对应的symbols[i]追加到结果中并从num中减去values[i]。重复此步骤直到num小于values[i]然后移动到下一个更小的值。当num被减至 0 时转换完成返回结果字符串。为什么可行因为罗马数字的表示规则本质上就是“贪心”的对于任何给定的数字总是优先使用能表示它的最大符号。预定义的数组已经包含了所有必要的减法形式如 IV, IX, XL 等确保了算法能正确处理 4 和 9 相关的边界情况。复杂度分析时间复杂度O(1)。虽然有一个循环但循环次数是固定的数组长度 13与输入num的大小无关。在最坏情况下如 num1内层 while 循环可能执行多次但总操作次数仍有一个很小的常数上界。空间复杂度O(1)。只使用了固定大小的数组和结果字符串。class Solution { // 按从大到小的顺序定义所有可能的“值-符号”对 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 roman new StringBuilder(); // 遍历每一个值 for (int i 0; i values.length; i) { // 当剩余数字大于等于当前值时就使用对应的符号 while (num values[i]) { roman.append(symbols[i]); num - values[i]; } // 如果数字已经减到0可以提前结束非必需优化 if (num 0) { break; } } return roman.toString(); } }代码说明使用StringBuilder来高效构建结果字符串。内层使用while循环确保同一个符号可以连续使用多次例如3000 对应三个 “M”。数组包含了所有必要的减法形式如 900 对应 “CM”因此算法能自动处理 4、9、40、90、400、900 这些情况。提前判断num 0可以提前退出循环是一个小的优化。示例推演num 3749num3749 1000追加 “M”num2749。num2749 1000追加 “M”num1749。num1749 1000追加 “M”num749。此时已得到 “MMM”。num749 900 但 500追加 “D”num249。得到 “MMMD”。num249 400 但 100追加 “C”num149。得到 “MMMDC”。num149 100追加 “C”num49。得到 “MMMDCC”。num49 90 但 40追加 “XL”num9。得到 “MMMDCCXL”。num9 9追加 “IX”num0。得到最终结果 “MMMDCCXLIX”。方法二硬编码这种方法利用了罗马数字表示法的确定性对于给定的整数1 ≤ num ≤ 3999其千位、百位、十位、个位上的数字是确定的且每个数位上的数字0-9对应的罗马数字组合也是固定的。因此我们可以预先为每个数位上的所有可能数字0-9编码好对应的罗马数字字符串然后通过简单的数学运算取出每一位的数字拼接对应的字符串即可。核心思路数位分离将输入整数num分解为千位、百位、十位、个位四个数字。查表映射为每个数位预先定义一个长度为 10 的字符串数组下标 0-9 分别对应数字 0-9 在该数位上的罗马数字表示其中 0 对应空字符串。拼接结果将四个数位对应的罗马数字字符串按顺序千位、百位、十位、个位拼接起来即为最终结果。算法步骤定义四个字符串数组thousands[]千位数字 0-3 对应的罗马数字0 为空字符串1 为 M2 为 MM3 为 MMM。hundreds[]百位数字 0-9 对应的罗马数字例如 0, 1C, 2CC, 3CCC, 4CD, 5D, 6DC, 7DCC, 8DCCC, 9CM。tens[]十位数字 0-9 对应的罗马数字例如 0, 1X, 2XX, 3XXX, 4XL, 5L, 6LX, 7LXX, 8LXXX, 9XC。ones[]个位数字 0-9 对应的罗马数字例如 0, 1I, 2II, 3III, 4IV, 5V, 6VI, 7VII, 8VIII, 9IX。通过整数除法和取余运算获取每一位的数字千位num / 1000百位(num % 1000) / 100或num % 1000 / 100十位(num % 100) / 10或num % 100 / 10个位num % 10根据每一位的数字作为下标从对应的数组中取出罗马数字字符串依次拼接到结果中。返回拼接后的字符串。为什么可行因为罗马数字的表示是按位独立的。千位只由 M 组成百位由 C, D, M 的组合构成十位由 X, L, C 的组合构成个位由 I, V, X 的组合构成。每个数位上的数字 0-9 都有唯一确定的罗马数字表示包括减法形式如 IV, IX, XL, XC, CD, CM且不同数位之间的表示不会相互干扰。因此预先编码所有可能性并查表拼接是完全正确的。复杂度分析时间复杂度O(1)。仅进行固定次数的数学运算除法、取余和字符串拼接操作与输入大小无关。空间复杂度O(1)。使用了四个固定大小的数组总长度 4×1040和一个结果字符串均为常数空间。class Solution { // 千位0-3 对应空字符串、M、MM、MMM String[] thousands {, M, MM, MMM}; // 百位0-9 对应的罗马数字 String[] hundreds {, C, CC, CCC, CD, D, DC, DCC, DCCC, CM}; // 十位0-9 对应的罗马数字 String[] tens {, X, XX, XXX, XL, L, LX, LXX, LXXX, XC}; // 个位0-9 对应的罗马数字 String[] ones {, I, II, III, IV, V, VI, VII, VIII, IX}; public String intToRoman(int num) { // 使用 StringBuffer 或 StringBuilder 进行高效拼接 StringBuffer roman new StringBuffer(); // 获取千位数字并拼接对应字符串 roman.append(thousands[num / 1000]); // 获取百位数字并拼接对应字符串 roman.append(hundreds[num % 1000 / 100]); // 获取十位数字并拼接对应字符串 roman.append(tens[num % 100 / 10]); // 获取个位数字并拼接对应字符串 roman.append(ones[num % 10]); return roman.toString(); } }代码说明数组定义清晰对应每个数位注释说明了每个下标的含义。使用StringBuffer或StringBuilder进行字符串拼接效率高于直接使用操作符。通过简单的除法和取余运算获取每一位的数字代码简洁且易于理解。由于题目限制1 num 3999千位数字范围是 0-3因此thousands数组只需定义 4 个元素。示例推演num 3749千位3749 / 1000 3→thousands[3] MMM百位3749 % 1000 749749 / 100 7→hundreds[7] DCC注意700 是 DCC不是 CC...十位3749 % 100 4949 / 10 4→tens[4] XL个位3749 % 10 9→ones[9] IX拼接MMM DCC XL IX MMMDCCXLIX方法对比贪心模拟法更通用体现了罗马数字的构造规则易于理解和扩展。硬编码法更高效、更直接利用了问题范围的有限性num ≤ 3999代码极其简洁在实际编码竞赛或面试中可能是更优的选择。
