Python小白 Leetcode刷題歷程 No.26-No.30 刪除排序數(shù)組中的重復(fù)項床玻、移除元素毁涉、實現(xiàn)strStr()、兩數(shù)相除锈死、串聯(lián)所有單詞的子串
寫在前面：
作為一個計算機院的大學(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.26.刪除排序數(shù)組中的重復(fù)項
難度：簡單
題目描述：
題解代碼（Python3.8）
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
for i in range(len(nums)-1,0,-1):
if nums[i]==nums[i-1]:
nums.pop(i)
return len(nums)
或許有用的知識點：
temp=list.pop(i)琳钉，是彈出list中第個元素，并儲存到temp中;
list.pop(i)就是直接彈出第i個元素蛛倦；
同理歌懒，list.pop()就是直接彈出最后一個元素。
解題思路：
本題要求‘必須在原地修改數(shù)組’溯壶，因此不能新建數(shù)組及皂，只能在原數(shù)組上遍歷并刪除重復(fù)元素∏腋模考慮到刪除元素會影響數(shù)組長度验烧，于是采用倒序遍歷的方式刪除重復(fù)元素。
No.27.移除元素
難度：簡單
題目描述：
題解代碼（Python3.8）
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
for i in range(len(nums)-1,-1,-1):
if nums[i]==val:
nums.pop(i)
return len(nums)
解題思路：
跟上一題的解題思路基本一致又跛。要求‘必須在原地修改數(shù)組’碍拆，因此不能新建數(shù)組，只能在原數(shù)組上遍歷并刪除數(shù)值為val的元素慨蓝「谢欤考慮到刪除元素會影響數(shù)組長度，于是采用倒序遍歷的方式刪除數(shù)值為val的元素菌仁。
No.28.實現(xiàn)strStr()
難度：簡單
題目描述：
題解代碼（Python3.8）
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if len(needle)==0:
return 0;
l_h=len(haystack)
l_n=len(needle)
for i in range(l_h-l_n+1):
if haystack[i]!=needle[0]:
continue
elif l_n==1:
return i
for j in range(1,l_n):
if i+j>=l_h or haystack[i+j]!=needle[j]:
break
if j==l_n-1:
return i
return -1
或許有用的知識點：
（“return haystack.find(needle) ”在Python中一行就可以解決本題浩习，但對鍛煉算法沒有作用静暂，只作為了解）
KMP算法是一種改進的字符串匹配算法济丘，算法的時間復(fù)雜度O(m+n)，可用于快速的解決許多字符串的匹配問題。本題先不展示該方法摹迷。
解題思路：
我一開始不了解KMP算法疟赊，直接用的遍歷。當(dāng)主字符串中出現(xiàn)與模式字符串相同的首字母峡碉，開始判斷隨后字符是否相等近哟，若相等钧排，則返回相應(yīng)索引值途茫。
其實本題應(yīng)該用雙指針法取劫，一個指針在主字符串族购，一個指針在模式字符串形帮。不過我的方法其實和雙指針法不謀而合丧荐，i和j相當(dāng)于兩個指針望众，代碼也大同小異谤碳。
No.29.兩數(shù)相除
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
res=0
sign = 1 if dividend^divisor>=0 else -1 #判斷符號
dividend,divisor=abs(dividend),abs(divisor)
count=0
while dividend>=divisor: #計算出divisor*(2**n)>dividend中n的最小值
count+=1
divisor<<=1
while count>0: #逐見n直到n=0時結(jié)束
count-=1
divisor>>=1
res<<=1 #此時除數(shù)=原除數(shù)*(2**n)
if dividend>=divisor: #如果被除數(shù)大于除數(shù)未斑，說明被除數(shù)中還有原除數(shù)*1*(2**n)
res+=1 #此處+1咕宿，經(jīng)過n次循環(huán)，就會變成(2**n)
dividend-=divisor #被除數(shù)減去本輪的‘原除數(shù)*1*(2**n)’
return min(max(res*sign,-2**31),2**31-1)
或許有用的知識點：
計算機中數(shù)字為二進制儲存蜡秽，其中左移右移操作也是針對二進制格式的府阀。
解題思路：
既然題目要求不能用乘除法，我們考慮最基礎(chǔ)的位操作芽突，Python不用考慮正負數(shù)邊界试浙，實則簡化了題目。用位操作诉瓦，將除數(shù)和被除數(shù)想成二進制形式即可計算川队。代碼中由本題逐行詳細的注釋，應(yīng)該比較容易理解睬澡。
No.30.串聯(lián)所有單詞的子串
難度：困難
題目描述：
題解代碼（Python3.8）
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
from collections import Counter
if not s or not words:
return []
words_len = len(words[0]) # 一個單詞的長度
words_num = len(words) # words中單詞的個數(shù)
words_cnt = Counter(words) # {'foo': 1, 'bar': 1}
s_len = len(s) # 字符串s的長度
res = [] # 存儲起始位置
W = words_len * words_num # 此處窗口大小為 2*3
left = 0
while (left + W) <= s_len: #遍歷所有可能的窗口
tmp = []
i = left
for j in range(words_num): # 將窗口內(nèi)的字符串添加到tmp中
tmp.append(s[i:i + words_len])
i = i + words_len
tmp = Counter(tmp) #判斷該窗口字符串是否滿足條件
if tmp == words_cnt:
res.append(left)
left = left + 1
else:
left = left + 1
return res
或許有用的知識點：
調(diào)用Counter函數(shù)需要調(diào)用頭文件’from collections import Counter’
將一個list固额，tuple，dict煞聪，字符串等轉(zhuǎn)化成Counter形式斗躏，將會輸出dict中key : value形式，其中key為元素昔脯，value為該元素的個數(shù)啄糙。
Counter是無序性的，很適合做本題云稚，Counter[key]=(相對應(yīng))value隧饼，如下圖：
解題思路：
這個題用到Counter就變得比較容易了，我在代碼中逐行寫了詳細的注釋静陈，很好理解燕雁，我的思路比較簡單诞丽，計算滑動窗口的長度，遍歷滿足滑動窗口的所有字符串拐格，判斷其Counter值與目標(biāo)值是否相等即可僧免，但缺點是運行太慢了。
優(yōu)解代碼及分析：
優(yōu)解代碼（Python3.8）
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
from collections import Counter
if not s or not words:return [] #特解
word_len = len(words[0]) #一個單詞的長度
word_num = len(words) #單詞數(shù)量
n = len(s) #字符串長度
words = Counter(words) #將單詞組成的list轉(zhuǎn)成counter形式
res = []
for i in range(0, word_len): #根據(jù)單詞長度n捏浊，將字符串中目標(biāo)單詞出現(xiàn)的位置分為n種情況
cur_cnt = 0
left = i
right = i
cur_Counter = Counter() #設(shè)置一個Counter類型的變量
while right + word_len <= n: #右指針以單詞長度為單位截取從i開始的所有字符串
w = s[right:right + word_len]
right += word_len
cur_Counter[w] += 1 #將截取的字符串作為Counter的鍵懂衩，該鍵的值+1
cur_cnt += 1
while cur_Counter[w] > words[w]: #如果該單詞數(shù)量超過目標(biāo)單詞數(shù)量（或目標(biāo)單詞數(shù)量為0）
left_w = s[left:left+word_len] #從左開始刪除單詞
left += word_len
cur_Counter[left_w] -= 1
cur_cnt -= 1
if cur_cnt == word_num : #如果左右指針間單詞數(shù)等于目標(biāo)單詞數(shù)（目標(biāo)單詞各出現(xiàn)一次）
res.append(left)
return res
分析：
這個代碼并沒有采用滑動窗口法，而是使用了雙指針法金踪，比較難想浊洞，但很巧妙，復(fù)雜度很低胡岔。我在代碼中逐行寫了詳細的注釋沛申，很好理解。
