Python小白 Leetcode刷題歷程 No.11-No.15 盛最多水的容器暑椰、整數(shù)轉(zhuǎn)羅馬字母、羅馬數(shù)字轉(zhuǎn)整數(shù)荐绝、最長公共前綴一汽、三數(shù)之和
寫在前面：
作為一個計算機院的大學(xué)生，總覺得僅僅在學(xué)校粗略的學(xué)習(xí)計算機專業(yè)課是不夠的低滩，尤其是假期大量的空檔期召夹，作為一個小白，實習(xí)也莫得路子恕沫，又不想白白耗費時間监憎。于是選擇了Leetcode這個平臺來刷題庫。編程我只學(xué)過基礎(chǔ)的C語言婶溯，現(xiàn)在在自學(xué)Python鲸阔，所以用Python3.8刷題庫。現(xiàn)在我Python掌握的還不是很熟練迄委，算法什么的也還沒學(xué)褐筛，就先不考慮算法上的優(yōu)化了，單純以解題為目的叙身，復(fù)雜程度什么的以后有時間再優(yōu)化渔扎。計劃順序五個題寫一篇日志，希望其他初學(xué)編程的人起到一些幫助信轿，寫算是對自己學(xué)習(xí)歷程的一個見證了吧晃痴。
有一起刷LeetCode的可以關(guān)注我一下，我會一直發(fā)LeetCode題庫Python3解法的虏两，也可以一起探討愧旦。
覺得有用的話可以點贊關(guān)注下哦，謝謝大家定罢！
········································································································································································
題解框架：
1.題目笤虫，難度
2.題干,題目描述
3.題解代碼（Python3（不是Python，是Python3））
4.或許有用的知識點（不一定有）
5.解題思路
6.優(yōu)解代碼及分析（當(dāng)我發(fā)現(xiàn)有比我寫的好很多的代碼和思路我就會寫在這里）
········································································································································································
No.11.盛最多水的容器
難度:中等
題目描述：
題解代碼（Python3.8）
class Solution:
def maxArea(self, height: List[int]) -> int:
i,j,smax=0,len(height)-1,0
while i<j:
if height[i] < height[j]:
smax=max(smax,height[i]*(j-i))
i +=1
else:
smax=max(smax,height[j]*(j-i))
j -=1
return smax
或許有用的知識點：
這道題用雙指針法，固定大邊琼蚯，移動小邊酬凳，是可以證明正確性和安全性的，即略去的情況都必定不是最大值遭庶。
解題思路：
最簡單的辦法是兩邊f(xié)or循環(huán)遍歷所有可能宁仔，但這樣太麻煩了，我們顯然有更簡單的方法峦睡。思考一下翎苫，我們可以設(shè)置兩個指針，i代表左邊的容器壁榨了，j代表右邊的容器壁煎谍。首先我們要while i<j 的情況下才進(jìn)行運算，之后我們判斷左邊和右邊哪個容器壁短龙屉，我們移動短的容器壁呐粘，然后記錄最大面積即可。
No.12.整數(shù)轉(zhuǎn)羅馬字母
難度:中等
題目描述：
題解代碼（Python3.8）
class Solution:
def intToRoman(self, num: int) -> str:
dic={'I':1,'IV':4,'V':5,'IX':9,'X':10,'XL':40,'L':50,'XC':90,'C':100,'CD':400,'D':500,'CM':900,'M':1000}
res=""
for val in sorted(dic.values())[::-1]:
if num==0:
break
tmp=num//val
if tmp==0:
continue
res +=(list (dic.keys()) [list (dic.values()).index (val)])*tmp
num -=val*tmp
return res
或許有用的知識點：
sorted(dic.values())[::-1]表示把字典的值從小到大排列转捕，再倒序取出作岖，其中若由鍵取值比較簡單 value=dict[key],
而由值取鍵則需要key=list (dic.keys()) [list (dic.values()).index (val)]。
由鍵取值與代碼健壯性的關(guān)系：
index函數(shù)：
解題思路：
顯然這個題需要采用貪心算法五芝，我們可以用字典的值和鍵分別表示羅馬字母與數(shù)字痘儡，由題意通常情況是大數(shù)的羅馬字母在前，因此我們只需要把特殊情況寫進(jìn)字典与柑，就可以認(rèn)為全部滿足通常情況大數(shù)的羅馬字母在前谤辜。字典的結(jié)構(gòu)為：dict( key : value)這個題應(yīng)該讓key為數(shù)字，value為羅馬字母比較好寫价捧，但是我開始寫反了丑念，就反著做了。我們采用貪心算法结蟋，從最大羅馬字母開始循環(huán)脯倚，有的話就加載res上，有幾個加幾個嵌屎，沒有就繼續(xù)循環(huán)推正。
No.13.羅馬數(shù)字轉(zhuǎn)整數(shù)
難度：簡單
題目描述：
題解代碼（Python3.8）
class Solution:
def romanToInt(self, s: str) -> int:
dic={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
ans=0
for i in range(len(s)):
if i<=len(s)-2 and dic[s[i]]<dic[s[i+1]]:
ans-=dic[s[i]]
else:
ans+=dic[s[i]]
return an
解題思路：
同上個題類似，還是先創(chuàng)建字典宝惰，這次不用考慮特殊情況植榕，然后for循環(huán)遍歷s中每個羅馬字母，當(dāng)這個字母不是最后一個尼夺，而且這個字母對應(yīng)的字典值比下一個小尊残，則這是出現(xiàn)了特殊情況炒瘸，總和應(yīng)減去這個值；其余的時候累加對應(yīng)值就可以了寝衫。
NO.14.最長公共前綴
難度：簡單
題目描述：
題解代碼（Python3.8）
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if len(strs)==0:
return ""
if len(strs)==1:
return strs[0]
s=""
l=len(strs[0])
for i in range(1,len(strs)): #判斷最短字符串長度
l=min(l,len(strs[i]))
for i in range(l): #在最短長度中
k=1
for j in range(1,len(strs)): #對第j個字符串的第i個字符
if strs[j][i]==strs[0][i]:
k +=1
else:
k=0
break
if k==0:
break
if k==len(strs):
s +=strs[1][i]
return s
或許有用的知識點：
解題思路：用一個for循環(huán)判斷最短字符串長度顷扩，再用兩個for循環(huán)判斷第j個字符串的第i的字符是否跟第1個字符串的第i個字符相等，如果不相等就退出循環(huán)慰毅。
優(yōu)解代碼及分析：
優(yōu)解代碼（Python3.8）
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
res=""
for tmp in zip(*strs):
tmp_set=set(tmp)
if len(tmp_set)==1:
res +=tmp[0]
else:
break
return res
分析：
將多個字符串看成一個元組隘截，利用zip（*tuple）對元組進(jìn)行拆包，如果最短的字符串由n個字母組成汹胃，元組拆包就能得到tmps=[(各個字符串的第一個字母)婶芭，(各個字符串的第二個字母)，……统台，(各個字符串的第n個字母)]雕擂。提取res的第一個元素并使用set()函數(shù)去重，如果都一樣贱勃，則長度len()==1，把該字母寫入res中谤逼，當(dāng)出現(xiàn)len()!=1贵扰，則退出。
NO.15.三數(shù)之和
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
l=len(nums) #特解
if l<3:
return []
res=[]
nums.sort()
for i in range(l-2):
if nums[i]>0: #最小數(shù)>0流部，跳出循環(huán)
break
if i>0 and nums[i]==nums[i-1]: #最小數(shù)與上一輪循環(huán)相同戚绕，防止重復(fù)解，跳過
continue
L=i+1
R=l-1
while L<R:
if nums[i]+nums[L]+nums[R] == 0:
res.append([nums[i],nums[L],nums[R]])
while L<R and nums[L]==nums[L+1]: #左指針向右跳過重復(fù)值枝冀，防止重復(fù)解
L +=1
while L<R and nums[R]==nums[R-1]: #右指針向左跳過重復(fù)值舞丛，防止重復(fù)解
R -=1
L +=1
R -=1
elif nums[i]+nums[L]+nums[R] > 0: #三數(shù)和>0，右指針大了果漾，左移
R -=1
else: #三數(shù)和<0球切，左指針小了，右移
L +=1
return res
或許有用的知識點：
set(list)函數(shù)可以將list中重復(fù)元素過濾绒障，set是無序的吨凑，Python不支持dict的key為set，list或dict類型户辱，因為list和dict類型是unhashable（不可哈希）的鸵钝；
不可哈希的list表，可通過if i not in list查重庐镐；
list.append(‘ ’)可以在list末尾添加元素恩商，list.insert( i,’ ‘)可以在list的i處添加元素；list.pop()可以刪除list末尾的元素必逆，list.pop( i )可以刪除list中i處的元素怠堪；
set.add(key)可以在set中添加元素韧献，set.remove(key)可以在set中刪除元素。
解題思路：
見到這個題第一反應(yīng)是用三個for循環(huán)遍歷數(shù)組研叫，計算三數(shù)之和锤窑，但是后來發(fā)現(xiàn)超時了，顯然不應(yīng)該這樣做嚷炉。于是我將數(shù)組排序渊啰，第一個數(shù)也就是最小數(shù)一定小于零，否則可以退出循環(huán)申屹；當(dāng)我們確定了最小數(shù)绘证，就只剩下中間數(shù)和最大數(shù)，我們用雙指針法哗讥。最小數(shù)與上一輪循環(huán)相同嚷那，防止重復(fù)解，跳過杆煞；確定最小數(shù)后魏宽，判斷最小數(shù)+左指針+右指針是否等于0，若等于零决乎，左指針向右跳過重復(fù)值队询，防止重復(fù)解，右指針向左跳過重復(fù)值构诚，防止重復(fù)解蚌斩，之后左指針+1，右指針-1范嘱。若不等于0送膳，判斷，若三數(shù)和>0丑蛤，右指針大了叠聋，應(yīng)左移；若三數(shù)和<0盏阶，左指針小了晒奕，右移。
