算功@LeetCode:Roman to Integer

Log

• 【170808】完成 01 版 Python 提交

题目

Roman to Integer

【题目类型备注】

数学，字符串

提交

01

【语言】

Python

【时间】

170808

【思路】

研究了 Wikipedia 的「罗马数字」词条后，结合题目要求（题目能保证输入为合法的罗马数字输入，仅要求转换），特别注意到词条中对于 99 = 90 + 9 = (100 - 1) + (10 - 1) 的介绍、以及左减最多 1 位，有如下思路是：

1. 每次处理十进制阿拉伯数字中的 1 位，相当于处理罗马数字中最多 2 位
2. 从首位开始，若当前位与邻近下一位降序，说明不需要减，直接加入该位对应数值；若为升序，则加入值为下一位数值减该位数值
3. 根据上一步处理的结果，决定下一轮处理的位置是当前位的下一位（降序时）或下两位（升序时，因为下一位已经被用过了）。如此循环到末位前
4. 根据处理末位前最后一次是处理升序问题还是降序问题，决定是否要将末位加入答案中

【代码】

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        roman = {
            'I':1, 'V':5,
            'X':10, 'L':50,
            'C':100,'D':500,
            'M':1000
        }
        maxlen = len(s)
        if 1 == maxlen:
            return roman[s]
        
        i, ans = 0, 0
        #ct = 0
        while (i+1 <= maxlen-1):
            if roman[s[i]] >= roman[s[i+1]]:
                ans += roman[s[i]]
                i += 1
            else:
                ans += (roman[s[i+1]] - roman[s[i]])
                i += 2
        
        # if stop in the last character
        if i < maxlen:
            ans += roman[s[-1]]
        
        return ans

【结果】

运行时：149 ms

报告链接：https://leetcode.com/submissions/detail/113008239/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 42.31 % of python submissions.

00

参考解法：

• [language]。。。

自己实现一遍最优解：

• [language]。。。