[LeetCode] 12. Integer to Roman ☆☆
2024-09-27 09:00:54
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
解释:
罗马数字采用七个罗马字母作数字、即Ⅰ(1)、X(10)、C(100)、M(1000)、V(5)、L(50)、D(500)。记数的方法:
- 相同的数字连写,所表示的数等于这些数字相加得到的数,如 Ⅲ=3;
- 小的数字在大的数字的右边,所表示的数等于这些数字相加得到的数,如 Ⅷ=8、Ⅻ=12;
- 小的数字(限于 Ⅰ、X 和 C)在大的数字的左边,所表示的数等于大数减小数得到的数,如 Ⅳ=4、Ⅸ=9;
- 在一个数的上面画一条横线,表示这个数增值 1,000 倍(本题不涉及)
例如:整数 1437 的罗马数字为 MCDXXXVII, 我们不难发现,千位,百位,十位和个位上的数分别用罗马数字表示了。 1000 - M, 400 - CD, 30 - XXX, 7 - VII。所以我们要做的就是用取商法分别提取各个位上的数字,然后分别表示出来:
100 - C
200 - CC
300 - CCC
400 - CD
500 - D
600 - DC
700 - DCC
800 - DCCC
900 - CM
解法:
每次取下最高位上的数字x,判断其范围为 (0-3)、(4)、(5-8)、(9) 中的哪一类,再根据每一类的特点添加字符。
public class Solution {
public String intToRoman(int num) {
StringBuilder res = new StringBuilder("");
char[] roman = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};
int[] value = {1000, 500, 100, 50, 10, 5, 1}; for (int i = 0; i < value.length; i += 2) {
int x = num / value[i];
if (x < 4) {
while (x-- > 0) res.append(roman[i]);
} else if (x == 4) {
res.append(roman[i]).append(roman[i - 1]);
} else if (x < 9) {
res.append(roman[i - 1]);
while (x-- > 5) res.append(roman[i]);
} else {
res.append(roman[i]).append(roman[i - 2]);
}
num %= value[i];
}
return res.toString();
}
}
本题由于限制了输入数字范围这一特殊性,因此也可以采用贪婪算法,建立一个数表,每次通过查表找出当前最大的数并匹配对应的字符串,然后减去再继续查表。代码如下:
public class Solution {
public String intToRoman(int num) {
StringBuilder res = new StringBuilder("");
String[] roman = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
int[] value = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}; for (int i = 0; i < value.length; i++) {
int x = num / value[i];
while (x-- > 0) res.append(roman[i]);
num %= value[i];
}
return res.toString();
}
}
另外,由于限制了输入数字范围,存在的情况有限,还可以把所有的情况都列出来,然后直接按位查表,O(1)的时间复杂度,代码如下:
public class Solution {
public String intToRoman(int num) {
StringBuilder res = new StringBuilder("");
String[] r1 = {"", "M", "MM", "MMM"};
String[] r2 = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
String[] r3 = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
String[] r4 = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}; res.append(r1[num / 1000]).append(r2[(num % 1000) / 100]).append(r3[(num % 100) / 10]).append(r4[(num % 10) / 1]);
return res.toString();
}
}
最新文章
- C#小方法PadLeft 和 PadRight
- Volley框架使用笔记
- selenium使用笔记(二)——Tesseract OCR
- HTML编辑器
- 对Objective-C相关的类、方法、属性、成员变量介绍
- 微信JS SDK Demo 官方案例
- IIS Express 及 vs2008下使用IIS Express
- C++ 初始化与赋值
- 【转】./a.out 2>;&;1 >; outfile
- ubuntu service
- 初遇ping++
- spring框架DI(IOC)和AOP 原理及方案
- ORA-12638: 无法检索身份证明 解决的方法
- React+ajax+java 上传图片并预览
- 8.13.2 TreeSet实现Comparable接口的两种方式
- Python内置函数(11)——complex
- C# Redis 过期机制不生效问题
- 最长上升子序列(dp)
- mysql5.7.20完全卸载 win10
- openssl rsa/pkey
热门文章
- Python中的Dictionary
- tomcat web页面管理应用配置
- MySQL中使用trim()删除两侧字符
- 面试:谈谈你对jQuery的理解
- Java 多线程序的一点理解
- Android UI设计的基本元素有哪些
- FullCalendar(日程管理控件)
- 【题解】Atcoder ARC#94 F-Normalization
- BZOJ1934:[SHOI2007]善意的投票 &; BZOJ2768:[JLOI2010]冠军调查——题解
- [Leetcode] valid parentheses 有效括号对