LeetCode 12. Integer to Roman 原创Java参考解答
问题描述
https://leetcode.com/problems/integer-to-roman/
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
解题思路
题目是求做一个能把整数转换为罗马字母数字的函数。
这道题需要有对罗马数字的表示方法的了解。参考wiki百科
一个数字可以由7个基本罗马数字拼凑组成。7个罗马数字分别是 I(1)、V(5)、X(10)、L(50)、C(100)、D(500)和M(1000)。
罗马数字特点:
- 一个罗马数字重复几次,就表示这个数的几倍。比如 III (3)。
- 罗马数字右加左减:
- 在较大的罗马数字的右边记上较小的罗马数字,表示大数字加小数字。VI (6)
- 在较大的罗马数字的左边记上较小的罗马数字,表示大数字减小数字。IV (4)
本题解题算法正是演绎用罗马字符拼凑数字。
设两个数组,一个装数字:1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1。另一个装数字对应的罗马字母M (1000), CM (900), D (500), CD (400), C (100), XC (90), L (50), XL (40), X (10), IX (9), V (5), IV (4) and I (1)。
按数值从大到小的顺序试着用罗马字来拼凑数字,拼一次则在字符串加上该罗马字,并把数值从目标数字中减去。
参考代码
public class Solution { public String intToRoman(int num) { int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 }; String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" }; StringBuilder sb = new StringBuilder(); for (int i = 0; i < values.length; i++) { while (num >= values[i]) { num -= values[i]; sb.append(romans[i]); } } return sb.toString(); } }