昨天晚上十一点多,在公司楼下蹲着等外卖,吹着一点点凉风,手机叮一下,群里那个刚转正的小李给我发了个截图:“哥,面试又问整数转罗马数字了,你有现成的 Java 写法没?”我一看,这不就是那个老生常谈的题嘛,不过说实话,真要你当场从零写,多数人还是会卡几秒的。
先把规则说清楚哈,不然后面代码都是瞎写。罗马数字有这些基本符号:I=1,V=5,X=10,L=50,C=100,D=500,M=1000。然后有几个“减法规则”的组合:4不是IIII,而是IV;9是IX;40是XL;90是XC;400是CD;900是CM。面试官一般会限定整数范围 1~3999,这个区间刚好用这些符号就够了。
当时小李的第一反应是:要不要把千位、百位、十位、个位拆开,搞四个数组,一个数组管千位,["","M","MM","MMM"],一个管百位,["","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"],以此类推,然后按位拼起来。这个方案其实完全没问题,也挺好理解,就是写起来有点啰嗦,而且数组抄错一个位置就寄了。
我跟他说,我现在更习惯用“贪心”的写法,思路听起来就很接地气: 既然罗马数字本质上就是“从大到小凑数”,那咱就准备一份从大到小的“面值表”,比如 1000, 900, 500, 400, …, 1,对应 M, CM, D, CD, …, I。然后拿着这个表,从最大的开始往下扫,只要当前数字还大于等于这个面值,就减掉它,同时往结果字符串后面拼上对应的罗马符号。就像一直在找“能用的最大钞票”。
用 Java 写出来大概是这样,小李当场就抄走了,你也可以直接用:
public
class IntToRomanDemo {
public String intToRoman(int num) {
// 从大到小列出所有“合法面值”,包括那些减法组合
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"};
StringBuilder sb = new StringBuilder();
// 贪心地从大到小“凑”这个数
for (int i = 0; i < values.length && num > 0; i++) {
while (num >= values[i]) {
num -= values[i];
sb.append(symbols[i]);
}
}
return sb.toString();
}
public static void main(String[] args) {
IntToRomanDemo demo = new IntToRomanDemo();
System.out.println(demo.intToRoman(3)); // III
System.out.println(demo.intToRoman(4)); // IV
System.out.println(demo.intToRoman(9)); // IX
System.out.println(demo.intToRoman(58)); // LVIII
System.out.println(demo.intToRoman(1994)); // MCMXCIV
}
}
复杂度这块儿也很轻松,这个算法最多循环多少次?values 的长度固定是 13,num 的大小也在 3999 以内,一个数最多也就拼十几二十个字符,所以你可以大大方方地说:时间复杂度是 O(1),空间也是 O(1),常数级的。
最后我跟小李说,你面试的时候别上来就怼代码,可以先口头把这套“从大到小凑钱”的比喻讲一遍,再边说边写,面试官基本就不会为难你了。行了,我外卖到了,先去吃饭,下次有机会再给你们聊聊“罗马数字转整数”那一半怎么写。