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

0%

最初想法:

用栈实现,若栈顶元素与要加入的元素配对,栈顶元素出栈,最后看栈的长度。

当栈顶元素有右括号时,直接return False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
mydict = {"{":1,"}":-1,"(":2,")":-2,"[":3,"]":-3}
mystack = []
for idx,elem in enumerate(s):
if len(mystack) > 0:
if int(mydict[mystack[-1]])<0:
return False
if int(mydict[elem])+int(mydict[mystack[-1]])==0:#配对成功
mystack.pop()#栈顶元素出栈
continue
mystack.append(elem)

if len(mystack)==0:
return True
else:
return False

改进下:

len(s)为奇数,直接return false。

最初想法:
用一个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

最初想法:
读取第一个字符串中的第1个字符,与剩余的字符串比较第1个字符;

。。。

读取第一个字符串中的第i个字符,与剩余的字符串比较第i个字符;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def longestCommonPrefix(strs):
"""
:type strs: List[str]
:rtype: str
"""
if len(strs) == 0:
return ""
allstr = ""#最长公共前缀
for i in range(len(strs[0])):
for mystr in strs[1: ]:
if len(mystr)==i or strs[0][i] != mystr[i]:
return allstr
allstr += strs[0][i]
return allstr

使用zip获取每个字符串的同一位置的字母:

1
2
3
4
5
6
7
8
9
10
11
def longestCommonPrefix(strs):
if len(strs) == 0:
return ""
allstr = ""
zipped = zip(*strs) #*list表示将list解包,
for i in zipped:
if len(set(i)) == 1: #说明没有不同元素
allstr += i[0]
else:
break
return allstr

注意*list的使用

http://sbaban.com/Python%E8%A3%85%E9%A5%B0%E5%99%A8.html

先将字符串排序,然后比较第一个和最后一个元素有多少相同的字符就行

1
2
3
4
5
6
7
8
9
10
11
12
def longestCommonPrefix(strs):
n = len(strs)
if n==0:
return ""
strs.sort() #按字母排序
allstr = ""
for i in range(len(strs[0])):
if i<len(strs[n-1]) and strs[0][i] == strs[n-1][i]:
allstr += strs[0][i]
else:
break
return allstr