leetcode之旅-13-罗马数字转整数

1. 题目描述

2. 我的解法

我的解法特别弱，就是遍历一遍字符串，用switch 分情况讨论，遇到特殊情况就多余一位判断

1	class Solution {
2	public int romanToInt(String s) {
3	int len = s.length();
4	int sum = 0;
5	for (int i=0;i<len;i++)
6	{
7	char c=s.charAt(i);
8	switch(c)
9	{
10	case 'I':
11	if(i+1<len)
12	{
13	if(s.charAt(i+1)=='V')
14	{sum+=4;
15	i++;
16	break;
17	}
18	else if(s.charAt(i+1)=='X')
19	{
20	sum+=9;
21	i++;
22	break;
23	}
24	}
25	sum+=1;break;
26	case 'V':sum+=5;break;
27	case 'X':
28	if(i+1<len)
29	{
30	if(s.charAt(i+1)=='L')
31	{sum+=40;
32	i++;
33	break;
34	}
35	else if(s.charAt(i+1)=='C')
36	{
37	sum+=90;
38	i++;
39	break;
40	}
41	}
42	sum+=10;break;
43	case 'L':sum+=50;break;
44	case 'C':
45	if(i+1<len)
46	{
47	if(s.charAt(i+1)=='D')
48	{sum+=400;
49	i++;
50	break;
51	}
52	else if(s.charAt(i+1)=='M')
53	{
54	sum+=900;
55	i++;
56	break;
57	}
58	}
59	sum+=100;break;
60	case 'D':sum+=500;break;
61	case 'M':sum+=1000;break;
62	}
63	}
64	return sum;
65	}
66	}

3 解法二

别人的优雅的解法都是充分利用了罗马数字的特性。如IV=4，正常读=6 IX=9 正常读=11.正常读比正确读大2.所以提前-2。但是鉴于indexOf的效率O(nm)，就是遍历查找，应该挺慢的

1	public int romanToInt(String s) {
2	int sum=0;
3	//提前减2
4	if(s.indexOf("IV")!=-1){sum-=2;}
5	if(s.indexOf("IX")!=-1){sum-=2;}
6	if(s.indexOf("XL")!=-1){sum-=20;}
7	if(s.indexOf("XC")!=-1){sum-=20;}
8	if(s.indexOf("CD")!=-1){sum-=200;}
9	if(s.indexOf("CM")!=-1){sum-=200;}
10
11	char c[]=s.toCharArray();
12	int count=0;
13
14	for(;count<=s.length()-1;count++){
15	if(c[count]=='M') sum+=1000;
16	if(c[count]=='D') sum+=500;
17	if(c[count]=='C') sum+=100;
18	if(c[count]=='L') sum+=50;
19	if(c[count]=='X') sum+=10;
20	if(c[count]=='V') sum+=5;
21	if(c[count]=='I') sum+=1;
22
23	}
24
25	return sum;
26
27	}

时间复杂度：O（n+6n2)==(13n)
解法一和解法二的时间截图

3.解法三

规律的第二中理解 IV=4。可以理解为-1+5=4。IX=9 可以理解为 -1+10=9其他的特殊情况亦然,这个比解法二块一些，还是比解法一慢 5ms，getVal部分换成map应该更快

private int getVal(char c){
      switch (c){
          case 'M':
              return 1000;
          case 'D':
              return 500;
          case 'C':
              return 100;
          case 'L':
              return 50;
          case 'X' :
              return 10;
          case 'V':
              return 5;
          case 'I':
              return 1;
      }
      throw new IllegalArgumentException("unsupported character");
  }

  public int romanToInt(String s) {
      int res = 0;
      if(s.length() == 0) return res;
      for (int i = 0; i < s.length() - 1; i++) {
          int cur = getVal(s.charAt(i));
          int nex = getVal(s.charAt(i+1));
          if(cur < nex){
              res -= cur;
          }else{
              res += cur;
          }
      }
      return res + getVal(s.charAt(s.length()-1));
  }

1	private int getVal(char c){
2	switch (c){
3	case 'M':
4	return 1000;
5	case 'D':
6	return 500;
7	case 'C':
8	return 100;
9	case 'L':
10	return 50;
11	case 'X' :
12	return 10;
13	case 'V':
14	return 5;
15	case 'I':
16	return 1;
17	}
18	throw new IllegalArgumentException("unsupported character");
19	}
20
21	public int romanToInt(String s) {
22	int res = 0;
23	if(s.length() == 0) return res;
24	for (int i = 0; i < s.length() - 1; i++) {
25	int cur = getVal(s.charAt(i));
26	int nex = getVal(s.charAt(i+1));
27	if(cur < nex){
28	res -= cur;
29	}else{
30	res += cur;
31	}
32	}
33	return res + getVal(s.charAt(s.length()-1));
34	}