LeetCode 的 Runtime 指标是否可信？

今天做完  Roman to Integer 这道题后感觉运行时间稍长就开始了优化代码。然后就发现越优化越不科学！拿来中文版的 leetCode 网站来运行发现更加神奇。

题目详情

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

一

但看到题目的时候，想到可以用到键值对。然后针对特殊的规则，如果没到最后一个字母就判断当前字母表示的数值是否小于后一个字母表示的数值… …我的第一个版本代码如下：

public static int getValues(String roman){
		int values = 0;
		Map <Character,Integer> map = new HashMap();
		map.put('I', 1);
		map.put('V', 5);
		map.put('X', 10);
		map.put('L', 50);
		map.put('C', 100);
		map.put('D', 500);
		map.put('M', 1000);
		
		char[] romanArray = roman.toCharArray();
		
		for(int i = 0; i < romanArray.length; i++){
			if((i != romanArray.length-1)&&(map.get(romanArray[i]) < map.get(romanArray[i+1]))){
				values = values + (map.get(romanArray[i+1]) - map.get(romanArray[i]));
				i++;
			}else{
				values += map.get(romanArray[i]);
			}
			
		}
		return values;		
	}

Submission Detail

3999 / 3999 test cases passed.	Status: Accepted
Runtime: 43 ms	Submitted: 1 hour, 42 minutes ago

---

You are here! 
Your runtime beats 65.95 % of java submissions.

二

然后想到可以用用一个函数来替代 HashMap 的作用。第二个版本的代码：

class Solution {
    public static int val(char rom){
		int temp = 0;
		switch (rom){
		case 'I':
			temp = 1;
			break;
		case 'V':
			temp = 5;
			break;
		case 'X':
			temp = 10;
			break;
		case 'L':
			temp = 50;
			break;
		case 'C':
			temp = 100;
			break;
		case 'D':
			temp = 500;
			break;
		case 'M':
			temp = 1000;
		}
		return temp;
	}
    public int romanToInt(String s) {
       int values = 0;
		char[] romanArray = s.toCharArray();
		for(int i = 0; i < romanArray.length; i++){
			if((i != romanArray.length-1)&&(val(romanArray[i]) < val(romanArray[i+1]))){
				values = values + (val(romanArray[i+1]) - val(romanArray[i]));
				i++;
			}else{
				values += val(romanArray[i]);
			}
			
		}
		
		return values;
    }
}

Submission Detail

3999 / 3999 test cases passed.	Status: Accepted
Runtime: 38 ms	Submitted: 47 minutes ago

---

You are here! 
Your runtime beats 88.23 % of java submissions.

看来是有一点进步的！但是我实在想不到如何缩短运行时间了，所以我去看别人的

然后我通过 ctrl v + ctrl c，运行：

39 ms … …

还没我的代码运行时间短！然后我打开中文版的 leetCode 将上面的的代码依次复制运行，运行结果如下：

其中120 ms 是我从中文版网站中找的最优解代码… …

总结

• 这是玄学
• 英文版的服务器比中文版的服务器好
• 尽量挑没人做题的时候提交
• 以后除非有更好的思路和方法，再也不做优化！