塞进裤子ヾ(≧O≦)〃嗷~

0%

leetcode-13罗马数字转整数

最初想法:
用一个dict存储罗马数字,当char是I、X、C时特殊处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
romandict = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}
mysum=0
for i in range(len(s)):
mysum += int(romandict[s[i]])
if s[i] == "I" and i+1 <len(s):
if s[i+1]=="V" or s[i+1] == "X":
mysum -= 2
elif s[i] == "X" and i+1 <len(s):
if s[i+1]=="L" or s[i+1] == "C":
mysum -= 20
elif s[i] == "C" and i+1 <len(s):
if s[i+1]=="D" or s[i+1] == "M":
mysum -= 200
return mysum

改进:将IX,IV,XL,XC,CD,CM也存储到romandict中,遇到这些字符时让i+2.

改进:

找规律,利用dict.get()

1
dict.get(key, default=None)#返回指定键的值,如果值不在字典中返回默认值

构建一个字典记录所有罗马数字子串,注意长度为2的子串记录的值是(实际值 - 子串内左边罗马数字代表的数值)

这样一来,遍历整个 ss 的时候判断当前位置和前一个位置的两个字符组成的字符串是否在字典内,如果在就记录值,不在就说明当前位置不存在小数字在前面的情况,直接记录当前位置字符对应值

举个例子,遍历经过 IVIV 的时候先记录 II 的对应值 11 再往前移动一步记录 IVIV 的值 33,加起来正好是 IVIV 的真实值 44。max 函数在这里是为了防止遍历第一个字符的时候出现 [-1:0][−1:0] 的情况

链接:https://leetcode-cn.com/problems/roman-to-integer/solution/2-xing-python-on-by-knifezhu/

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
romandict = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000,"IV":3,
"IX":8,"XL":30,"XC":80,"CD":300,"CM":800}
mysum = 0
for index, elem in enumerate(s):
mysum += romandict.get(s[max(0,index-1):index+1],romandict[elem])

return mysum

改进:

找规律了,时间缩小了一半

从后往前扫描,如果当前的罗马数字a比前一个罗马数字b大,就将和减a。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
romandict = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}
mysum = 0
prev = len(s)-1 #上一个元素的索引
for i in range(len(s)-1,-1,-1):
if romandict[s[i]] < romandict[s[prev]]:
mysum -= romandict[s[i]]
else:
mysum += romandict[s[i]]
prev = i
return mysum
if help:小手一抖点个广告 or 大手一挥资助一下