IntegerToRoman [source code]
public class IntegerToRoman {
static
/******************************************************************************/
class Solution {
public String intToRoman(int num) {
StringBuilder sb = new StringBuilder();
int[] bases = {1, 5, 10, 50, 100, 500,1000};
String[] symbols = {"I", "V", "X", "L", "C", "D", "M"};
for (int i = 6; i >= 0; ) {
int count = num / bases[i];
if (i % 2 == 0 && count == 4) { //even i only: 1, 10, 100, 1000
sb.append(symbols[i] + symbols[i + 1]);
num -= 4 * bases[i]; //do not move i yet
} else if (count > 0) {
num -= count * bases[i];
while (count-- > 0)
sb.append(symbols[i]);
//tricky: do not move i yet!
} else if (i % 2 == 0 && i > 0 && num >= 9 * bases[i - 2]) { //count == 0
sb.append(symbols[i - 2] + symbols[i]);
num -= 9 * bases[i - 2];
i -= 2; //tricky: which i next?
} else i--;
}
return sb.toString();
}
}
/******************************************************************************/
public static void main(String[] args) {
IntegerToRoman.Solution tester = new IntegerToRoman.Solution();
String[] inputs = {
"1", "I",
"4", "IV",
"9", "IX",
"19", "XIX",
"99", "XCIX",
};
for (int i = 0; i < inputs.length / 2; i++) {
int num = Integer.parseInt(inputs[2 * i]);
String ans = inputs[1 + 2 * i];
System.out.println(Printer.separator());
String output = tester.intToRoman(num);
System.out.println(
Printer.wrapColor(num, "magenta") +
" -> " + output +
Printer.wrapColor(", expected: " + ans, ans.equals(output) ? "green" : "red")
);
}
}
}
我感觉这个题目很大的一个难点还是, 不知道题目的要求到底是什么. 只好自己王网上找了一个转换表, 然后自己来尝试总结规律; 尝试总结的时候还是挺头疼的, 因为情况太多了; 没办法, 只能用简单升级的思路, 从最小的开始尝试总结?
想了半天还是有点不太理解这个问题的逻辑; 想了很多想法, 都是感觉好像能做的出来, 但是写代码就感觉无从下手; 不管了, 放弃了;
这个题目后来自己写代码的时候还有一个问题就是自己trace一个case感觉好麻烦, 所以代码最后就写的很慢; 当然, 这个问题最后还是只能靠你自己克服, 真正面试的题目也有可能trace/debug起来就是很麻烦, 不能说就直接不做了;
另外我这里最后ver1决定模仿一个很general的写法, 但是这种写法的一个问题就是最后可能虽然主体逻辑写出来了, 但是最后各种Corner Case调试起来很麻烦, 这个也是难免的, 不能因为有这个问题所以干脆算法也不写了;
最后还是按照这个算法写出来了; 所以说算法这种东西就是要自己写一遍才知道天高地厚, 自己写的时候对于这里这个conditional increment和associative iteration的思路又重新加深了; 最后的速度是124ms (9%), 无所谓了, 这一题类hardcode的解法实在是太多了;
虽然这一题最后的downvote很多, 不过真正如果按照这里这个算法来理解, 其实这个题目还是有很多的收获的; 题目本身无所谓好坏, 关键是自己学到东西;
另外这个题目的OJ其实是挺狠的, 所有的3999个数字全都test了;
discussion最优解:
public static String intToRoman(int num) {
String M[] = {"", "M", "MM", "MMM"};
String C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
String X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
String I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
}
只能说贼鸡巴无语, 这个解法的思路还是很直接的, 直接就是用10-base的方法来提取没一个位置上的digit, 然后对应的直接翻译到Roman就行了;
刚开始看到这个问题给定了4000的范围的时候, 感觉会有hardcode的解法, 不过当时的想法是以为顶多是一些无所谓的娱乐解法; 结果这里直接就是主流解法, 这个是discussion的最优解, 440+的upvote, 简直是无语了;
稍微需要注意一点的技巧就是这里他比如在计算X的时候, 先要对num一个mod100的操作, 这样就是保证得到的结果的上限不超过100;
这个题目当时思考的时候很大的一个问题还是在于不知道怎么思考这个问题的逻辑, 不知道该做的是什么, 假想自己是一个机器, 然后手上拿到了一个数字, 下面该干什么?
然而往往就是这种几乎么有逻辑的逻辑, 根本无法想出来;
这个解法其实还可以写的更短:
String[] romanPieces={"","I","II","III","IV","V","VI","VII","VIII","IX",
"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC",
"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM",
"","M","MM","MMM","MMMM"};
return romanPieces[num/1000+30]+romanPieces[(num/100)%10+20]
+romanPieces[(num/10)%10+10]+romanPieces[num%10];
这个就比较娱乐了, 看看就好, 就是四个array放到一个array里面, 这个技巧看到Stefan用到过; 这个就是一个噱头, 本质上其实一点收益都没有;
还有人狗尾续貂的认为这一题用builder更好, 但是被回应:
@chern_yee said in Simple JAVA solution:
http://stackoverflow.com/questions/1532461/stringbuilder-vs-string-concatenation-in-tostring-in-java
In this case, it doesn't really matter as long as you aren't concatenate strings in a loop, otherwise that makes not much different in terms of performance, more like personal style wise.
确实是这样, 只要不是重复的操作, 那么就没有必要用builder: 重复操作会导致每一个iteration的string都被制作, 最后一个1+1+..+1的操作变成了1+2+..+N.
另外一个类似的解法:
@zxyperfect said in Sharing my really simple solution with explanation:
string intToRoman(int num) {
string table[4][10] = {{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},
{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},
{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},
{"", "M", "MM", "MMM"}
};
string result;
int count = 0;
while(num > 0){
int temp = num % 10;
result = table[count][temp] + result;
num /= 10;
count++;
}
return result;
}
The basic idea is really simple: replace every digit in num by roman numerals.
For example, we have a num: 2438.
2 --> "MM"
4 --> "CD"
3 --> "XXX"
8 --> "VIII"
Then the result is "MMCDXXXVIII".
这个是另外一个discussion最优解:
public class Solution {
public String intToRoman(int number) {
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
String[] numerals = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
StringBuilder result = new StringBuilder();
for (int i = 0; i < values.length; i++) {
while (number >= values[i]) {
number -= values[i];
result.append(numerals[i]);
}
}
return result.toString();
}
}
这个就跟我自己思考的时候的思路非常相似了, 我当时的想法就是这样, 把所有9, 4的数字也全部当做base来处理; 当时如果继续按照这个思路走下去应该是能做出来的, 但是我后来想要做一个general的做法:
int[] bases = {1, 5, 10, 50, 100, 500,1000};
String[] symbols = {"I", "V", "X", "L", "C", "D", "M"};
就是根据这种最general的思路, 只要知道这些base, 就可以自动二次生成类似于900, 400这样的secondary base, 并且继续使用上面的算法进行计算; 但是这一步没有想到很好的办法, 所以就直接放弃了;
Obsession with Generalization
如果非要说下来, 这个可以说是因为Premature Optmization带来的思路阻塞吧? 我看到discussion里面还有人说自己的代码写出来都快一百行了, 我如果按照之前的类似他这里这个解法写出来, 未必有他的简练, 但是也不至于100行, 但是我最后就是选择没有写; 导致这个问题的失败;
CS就是这样的, 很多问题根本没有那么多的general的属性, 很多问题本身就很个性化; 对于这些问题还过分纠结于一个通用解, 基本就是浪费自己的时间了; 而且你面试的时候, 问你的就是这一个问题, 你不要自己给自己加戏, 人家面试官没有问的Follow-Up, 你还自己给自己想了, 是不是无聊? 当然了, 如果你认为自己平时练习的时候应该对自己要求高一点, 多想一点, 这个不过分, 不过我觉得first AC的代码还是应该按照实际面试的感觉去想; 真正想要晚上, 以前first AC之后继续想ver2的事情, 也不是没有干过的;
另外注意这个人对于每一个base的处理, 是使用的减法思路而不是mod思路, 这个对于这个问题来说是有利的, 因为Roman的写法本身就是一个不停的append的操作;
上面的第一种那个类似穷举的最优解, 其实就是强行用base10的转换的思路来做Roman转换: 先用mod思路来得到当前base的系数, 然后找到这个系数对应的symbol; 这里这个做法则相对更加的贴切一些;
这个是另外一个人对上面的解法的优化:
@fujitsu4 said in My java solution easy to understand:
Your function is not really optimal because you will ALWAYS iterate until the end of your values array even if your number becomes zero! Which is not optimal at all.
In addition to that you didn't even check if the input number has a valid roman representation. You had to check that (even if the exercice assumes that the number has it already), you can do that easily with one line.
Here is an improvement of your function :
public static String intToRoman(int num){
if (num < 1 || num > 3999) return "";
StringBuilder result = new StringBuilder();
String[] roman = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
int i = 0;
//iterate until the number becomes zero, NO NEED to go until the last element in roman array
while (num >0) {
while ( num >= values[i]) {
num -= values[i];
result.append(roman[i]);
}
i++;
}
return result.toString();
}
As you see, you add just a simple line and you win an optimisation since the code will stop if the current number becomes zero (instead of doing additionnal iterations in the roman array).
想法其实是对的, 其实就是加一个premature exit; 当然, 为了实现这个premature exit, 他这里故意把整个循环都换成while来写了: 实际上是没有必要的, 直接在for的header的condition那里加一个&& num > 0就行了;
这个是另外一个解法:
public class Solution {
private static LinkedHashMap<Integer, String> numToRoman = new LinkedHashMap<Integer, String>();
static {
numToRoman.put(1000, "M");
numToRoman.put(900, "CM");
numToRoman.put(500, "D");
numToRoman.put(400, "CD");
numToRoman.put(100, "C");
numToRoman.put(90, "XC");
numToRoman.put(50, "L");
numToRoman.put(40, "XL");
numToRoman.put(10, "X");
numToRoman.put(9, "IX");
numToRoman.put(5, "V");
numToRoman.put(4, "IV");
numToRoman.put(1, "I");
}
public String intToRoman(int num) {
for (Integer i : numToRoman.keySet()) {
if (num >= i) {
return numToRoman.get(i) + intToRoman(num - i);
}
}
return "";
}
}
使用linked结构和recursion来完成一个string问题的操作, 这个其实不是第一次碰到了; 注意, 这里用recursion的另外一个好处就是premature exit很自然的就用base case完成了(虽然这里用的其实是一个no-op操作, 但是实际上跟base case做法是类似的);
另外这个:
public class Solution {
public String intToRoman(int num) {
if(num>=1000) return "M"+intToRoman(num-1000);
if(num>=900) return "CM"+intToRoman(num-900);
if(num>=500) return "D"+intToRoman(num-500);
if(num>=400) return "CD"+intToRoman(num-400);
if(num>=100) return "C"+intToRoman(num-100);
if(num>=90) return "XC"+intToRoman(num-90);
if(num>=50) return "L"+intToRoman(num-50);
if(num>=40) return "XL"+intToRoman(num-40);
if(num>=10) return "X"+intToRoman(num-10);
if(num>=9) return "IX"+intToRoman(num-9);
if(num>=5) return "V"+intToRoman(num-5);
if(num>=4) return "IV"+intToRoman(num-4);
if(num>=1) return "I"+intToRoman(num-1);
return "";
}
}
如果我自己最开始的想法是决定写下去的, 最后得到的估计就是类似这个的一个代码, 你看, 其实也不是很长的, 你自己不肯写而已;
这个是另外一个discussion:
public enum Type{
M(1000),CM(900),D(500),CD(400),C(100),XC(90),L(50),XL(40),X(10),IX(9),V(5),IV(4),I(1);
private final int value;
Type(int value) {
this.value = value;
}
};
public String intToRoman(int num) {
StringBuilder output = new StringBuilder();
for (Type t:Type.values()) {
while (num>=t.value) {
output.append(t);
num -= t.value;
}
}
return output.toString();
}
这个其实跟discussion2的那个方法没有什么区别, 就是一个array能解决的事情, 非要用一个enum来做, 最后其实并没有利用到enum本身什么特殊的性质;
另外, 我自己一开始想要generalize出来的这个算法, 居然有人在2013年就提出来了:
@porker2008 said in How to improve code?:
I think the following rule works
- If num is 4 times of
x(x = 1000, 100, 10, 1), addx 5x- If num is greater than
x, addx- If num is smaller than
x(x = 1000, 100, 10, 1) but it is 9 times ofx/10, add10/x x
class Solution {
public:
string intToRoman(int num) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
string result = "";
int base[] = {1000,500,100,50,10,5,1,0};
char baseC[] = {'M','D','C','L','X','V','I'};
int basen = 0;
while(num) {
if(basen%2 == 0 && num/base[basen] == 4) {
result += baseC[basen];
result += baseC[basen-1];
num -= base[basen] * 4;
} else if(num >= base[basen]) {
result += baseC[basen];
num -= base[basen];
} else if(basen%2 == 0 && num / base[basen+2] == 9) {
result += baseC[basen+2];
result += baseC[basen];
num -= base[basen+2]*9;
} else {
basen++;
}
}
return result;
}
};
这个算法虽然看起来啰嗦, 但是背后的逻辑比简单的穷举要elegant很多, 而且这个算法也更容易extend; 注意他这里为了实现减法思维, 使用了conditional increment来完成操作; 这个conditional increment的操作, 在这里非常重要, 因为你要理解他的逻辑:
100 90 50 40 10
难点在于, 要怎么处理90和40, 同时不能把90和40直接放到作为参数的array里面; 既然明确了你最后想要达到的目的, 直接就开始从这个角度开始思考就行了; 如果我们只有100,50,10, 那么我们又要处理90和40, 那么你首先要思考的问题: 你在属于100,50,10当中谁的iteration里面处理90和40? 就是因为这么一个uncertainty没有想到去针对, 导致我最后整个算法都无从下手;
他这里采用的思路就很直接, 这些secondary base, 直接靠到最近的base上面, 所以对于100, 我们要同时判断400(比100大)和90(比100小)就行了; 在整个循环的body里面, 只要保证三个branch的顺序按照他的列举的顺序, 完成一个从大到小的优先级顺序, 就不会出问题(不会把应该当做400处理的直接当成100来处理); 因为对于一个100, 我们其实要判断三个数字, 所以conditional increment在这里最后其实就很关键; 当然, conditional increment在这里另外一个当然就是用减法思维完成append;
这个是一个类似的解法:
class Solution {
public String intToRoman(int num) {
String roman = "IVXLCDM";
StringBuilder result = new StringBuilder("");
int divide = 1000;
for (int i = 6; i >= 0; i-=2) {
int temp = num / divide;
if (temp == 0) {
divide /= 10;
continue;
}
if (temp <= 3) {
result.append(createChars(roman.charAt(i),temp));
}
else if (temp == 4) {
result.append(roman.charAt(i));
result.append(roman.charAt(i+1));
}
else if (temp == 5) {
result.append(roman.charAt(i+1));
}
else if (temp <= 8) {
result.append(roman.charAt(i+1));
result.append(createChars(roman.charAt(i),temp-5));
}
else {
result.append(roman.charAt(i));
result.append(roman.charAt(i+2));
}
num %= divide;
divide /= 10;
}
return result.toString();
}
private String createChars(char c, int temp) {
String result = "";
for (int i = 0; i < temp; i++)
result += c;
return result;
}
}
但是这个解法的作者其实并没有主要吹嘘自己算法的这个方面, 他其实认为主要的卖点是他这里用的是mod思维而不是减法思维, 因为他认为减法思维对于同一个digit要iterate多次, 所以不好; 不过你可以看他的逻辑注意, 他的思路其实还是利用类似的一个400,100,90的判断思路的; 事实上, 他这里这个算法, 干脆把50也一起放进去判断了, 不过因为5**这种两边都能靠, 所以最后你还是要自己主观选一个方向, 他最后选择向小的方向靠; 也就是对于100, 我们判断的其实是500, 400, 100, 90.
Problem Description
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
Difficulty:Medium
Total Accepted:112.5K
Total Submissions:251.3K
Contributor: LeetCode
Companies Twitter
Related Topics Math String
Similar Questions Roman to Integer Integer to English Words