z****e
发帖数: 54598 | 1 看了就懂了
public class Solution {
public int romanToInt(String s) {
// Start typing your Java solution below
// DO NOT write main() function
if(s.length() == 0) return 0;
if(s.startsWith("CM")) return 900+romanToInt(s.substring(2));
if(s.startsWith("CD")) return 400+romanToInt(s.substring(2));
if(s.startsWith("XC")) return 90+romanToInt(s.substring(2));
if(s.startsWith("XL")) return 40+romanToInt(s.substring(2));
if(s.startsWith("IX")) return 9+romanToInt(s.substring(2));
if(s.startsWith("IV")) return 4+romanToInt(s.substring(2));
if(s.startsWith("M")) return 1000+romanToInt(s.substring(1));
if(s.startsWith("D")) return 500+romanToInt(s.substring(1));
if(s.startsWith("C")) return 100+romanToInt(s.substring(1));
if(s.startsWith("L")) return 50+romanToInt(s.substring(1));
if(s.startsWith("X")) return 10+romanToInt(s.substring(1));
if(s.startsWith("V")) return 5+romanToInt(s.substring(1));
if(s.startsWith("I")) return 1+romanToInt(s.substring(1));
return 0;
}
} | t*******2
发帖数: 182 | 2 真有公司会问这个么。。
【在 z****e 的大作中提到】
: 看了就懂了
: public class Solution {
: public int romanToInt(String s) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(s.length() == 0) return 0;
: if(s.startsWith("CM")) return 900+romanToInt(s.substring(2));
: if(s.startsWith("CD")) return 400+romanToInt(s.substring(2));
: if(s.startsWith("XC")) return 90+romanToInt(s.substring(2));
: if(s.startsWith("XL")) return 40+romanToInt(s.substring(2));
| a*****a
发帖数: 46 | 3 Code readability也很重要。
很多细节也会影响程序的效率。比如s.substring(2)每次都会生成一个新的string，无
形中就增加了时间和空间复杂度，recursion也会增加时间和空间复杂度。这都是可以
优化的地方。
1: public String intToRoman(int num) {
2: int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
3: String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "
IX", "V", "IV", "I"};
4: StringBuilder res = new StringBuilder();
5: int i=0;
6: while (num>0) {
7: int times = num / nums[i];
8: num -= nums[i]*times;
9: for (; times>0; times--) {
10: res.append(symbols[i]);
11: }
12: ++i;
13: }
14: return res.toString();
15: } | z****e
发帖数: 54598 | 4 你有没有意识到你说的这题不是我说的那题？
"
【在 a*****a 的大作中提到】
: Code readability也很重要。
: 很多细节也会影响程序的效率。比如s.substring(2)每次都会生成一个新的string，无
: 形中就增加了时间和空间复杂度，recursion也会增加时间和空间复杂度。这都是可以
: 优化的地方。
: 1: public String intToRoman(int num) {
: 2: int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
: 3: String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "
: IX", "V", "IV", "I"};
: 4: StringBuilder res = new StringBuilder();
: 5: int i=0;
| y***n
发帖数: 1594 | 5 以前有个牛人贴的code被我Evernote下来了。
int romanToInt(string s) {
int result = 0;
map lookup;
lookup['I'] = 1;
lookup['V'] = 5;
lookup['X'] = 10;
lookup['L'] = 50;
lookup['C'] = 100;
lookup['D'] = 500;
lookup['M'] = 1000;
for(int i = 0; i < s.size() -1; i++)
{
if(lookup[s[i]] < lookup[s[i+1]])
result -= lookup[s[i]];
else
result += lookup[s[i]];
}
result += lookup[s[s.size()-1]];
return result;
}
int main(int argc, char *argv[]) {
cout<
}
arosima 的blog非常牛。 | a*****a
发帖数: 46 | 6 呀，是我眼花了，但是romantoint也不需要recursion或者那么多if啊。我的意思是，
一般面试题本身不是特别难的，考察的就是细节了。
这是我写的，yuren贴的那个更简洁些。
public int romanToInt(String s) {
HashMap map = new HashMap();
map.put('M', 1000);
map.put('D', 500);
map.put('C', 100);
map.put('L', 50);
map.put('X', 10);
map.put('V', 5);
map.put('I', 1);
int res = 0;
for (int i=0; i
char c = s.charAt(i);
if ((c == 'C' || c == 'X' || c == 'I')
&& i+1 < s.length() && map.get(s.charAt(i+1)) > map.get(c)) {
res += map.get(s.charAt(i+1)) - map.get(c);
++i;
} else {
res += map.get(c);
}
}
return res;
}
【在 z****e 的大作中提到】
: 你有没有意识到你说的这题不是我说的那题？
:
:
: "
| s*****n
发帖数: 5488 | 7 的确细节比较重要。substring不会duplicate string.因为string是immutable.
"
【在 a*****a 的大作中提到】
: Code readability也很重要。
: 很多细节也会影响程序的效率。比如s.substring(2)每次都会生成一个新的string，无
: 形中就增加了时间和空间复杂度，recursion也会增加时间和空间复杂度。这都是可以
: 优化的地方。
: 1: public String intToRoman(int num) {
: 2: int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
: 3: String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "
: IX", "V", "IV", "I"};
: 4: StringBuilder res = new StringBuilder();
: 5: int i=0;
| s*****n
发帖数: 5488 | 8 从code reviewer的角度来看，楼主贴的代码无疑是最好的，最容易bug free的。
period. | m*****n
发帖数: 204 | 9 但是讲究效率的话还是应该用lookup。其实连map都不必要，直接上两级的array就行，
反正lookup structure可以搞成singleton
【在 s*****n 的大作中提到】
: 从code reviewer的角度来看，楼主贴的代码无疑是最好的，最容易bug free的。
: period.
| z****e
发帖数: 54598 | 10 适当的优化还是可以做的
比如用s=s.substring加一重循环干掉递归
这样的话就比较接近现实生活中的真实代码了
【在 s*****n 的大作中提到】
: 从code reviewer的角度来看，楼主贴的代码无疑是最好的，最容易bug free的。
: period.
| z****e
发帖数: 54598 | 11 string pool的概念稍微有些深了
而且她的stringbuilder多少也有些没有必要
string在编译之后jvm会自动优化成stringbuilder
在多数时候
【在 s*****n 的大作中提到】
: 的确细节比较重要。substring不会duplicate string.因为string是immutable.
:
:
: "
| g**G
发帖数: 767 | 12 或者我一般toCharArray，用char array和下标操作
【在 z****e 的大作中提到】
: string pool的概念稍微有些深了
: 而且她的stringbuilder多少也有些没有必要
: string在编译之后jvm会自动优化成stringbuilder
: 在多数时候
| r**********g
发帖数: 22734 | |
|
