leetcode题库解答源码(python3).pdf

leetcode题库解答源码（python3）

下⾯和⼤家分享本⼈在leetcode上已经ace的题⽬源码（python3）：本⼈会持续更新！～

classLeetcode_Solution(object):
deftwoSum_1(self,nums,target):
"""
:typenums:List[int]
:typetarget:int
:rtype:List[int]
"""
'''
此解法复杂度为#O(n^2)
new_nums=[]
foriinrange(len(nums)):
forjinrange(i+1,len(nums)):
ifnums[i]+nums[j]==target:
new_nums.append(i)
new_nums.append(j)
returnnew_nums
'''
此解法复杂度为#O(n)
拓展：若解不唯⼀，可先将#nums排序后进⾏下⾯操作，将全部符合对输出
iflen(nums)<=1:
returnFalse
else:
dict={}
foriinrange(len(nums)):
字典底层是⽤hash表实现的，⽆论字典中有多少元素，查找的平云复杂度均为#O(1)
ifnum[i]indict:
return[dict[nums[i]],i]
else:
dict[target-nums[i]]=i

defreverse_7(self,x):
"""
:typex:int
:rtype:int
"""
MAX=2**31-1
min=-1*2**31
ifx<0:
y=-1*int(str(-x)[::-1])
else:
y=int(str(x)[::-1])
ify>Maxory<min:
return0
returny

defisPalindrome_9(self,x):
renum=0
ifx<0or(x%10==0andx!=0):
returnFalse
whilex>renum:
renum=renum*10+x%10
x/=10
returnx==renumorx==renum/10

defromanToInt_13(self,s):
"""
:types:str
:rtype:int
"""
dic={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
sum=0
foriinrange(len(s)-1):
ifdic[s[i]]<dic[s[i+1]]:
sum-=dic[s[i]]
else:
sum+=dic[s[i]]
returnsum+dic[s[-1]]

deflongestCommonPrefix_14(self,strs):
"""
:typestrs:List[str]
:rtype:str
"""
iflen(strs)==0:#Horizontalscanning/////anotherway:verticalscanning
return''
prefix=strs[0]
foriinrange(1,len(strs)):
whilestrs[i].find(prefix)!=0:
prefix=prefix[0:len(prefix)-1]
ifprefix=='':
return''
returnprefix

defisValid_20(self,s):
"""
:types:str
:rtype:bool
"""
'''
list=[]
a=b=c=0
iflen(s)==0:
returnTrue
foriinrange(len(s)):
ifs[i]=='(':
list.append(s[i])
a+=1
ifs[i]=='{':
list.append(s[i])
b+=1
ifs[i]=='[':
list.append(s[i])
c+=1
ifs[i]==')':
iflen(list)!=0andlist[-1]=='(':
list.pop()
a-=1
else:
returnFalse
ifs[i]=='}':
iflen(list)!=0andlist[-1]=='{':
list.pop()
b-=1
else:
returnFalse
ifs[i]==']':
iflen(list)!=0andlist[-1]=='[':
list.pop()
c-=1
else:
returnFalse
iflen(list)==0anda==b==c==0:
returnTrue
else:
returnFalse
'''
dic={')':'(','{':'}','[':']'}
stack=[]
foriins:
ifiindi