Python小白 Leetcode刷題歷程 No.81-No.85 搜索旋轉(zhuǎn)排序數(shù)組Ⅱ、刪除排序鏈表中的重復元素Ⅱ、刪除排序鏈表中的重復元素、柱狀圖中最大的矩形、最大矩形
寫在前面：
作為一個計算機院的大學生，總覺得僅僅在學校粗略的學習計算機專業(yè)課是不夠的，尤其是假期大量的空檔期，作為一個小白，實習也莫得路子，又不想白白耗費時間。于是選擇了Leetcode這個平臺來刷題庫。編程我只學過基礎的C語言，現(xiàn)在在自學Python，所以用Python3.8刷題庫?，F(xiàn)在我Python掌握的還不是很熟練，算法什么的也還沒學，就先不考慮算法上的優(yōu)化了，單純以解題為目的，復雜程度什么的以后有時間再優(yōu)化。計劃順序五個題寫一篇日志，希望其他初學編程的人起到一些幫助，寫算是對自己學習歷程的一個見證了吧。
有一起刷LeetCode的可以關注我一下，我會一直發(fā)LeetCode題庫Python3解法的，也可以一起探討。
覺得有用的話可以點贊關注下哦，謝謝大家！
········································································································································································
題解框架：
1.題目，難度
2.題干,題目描述
3.題解代碼（Python3（不是Python，是Python3））
4.或許有用的知識點（不一定有）
5.解題思路
6.優(yōu)解代碼及分析（當我發(fā)現(xiàn)有比我寫的好很多的代碼和思路我就會寫在這里）
········································································································································································
No.81.搜索旋轉(zhuǎn)排序數(shù)組Ⅱ
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def search(self, nums: List[int], target: int) -> bool:
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return True
if nums[mid] == nums[left] == nums[right]:
left += 1
right -= 1
elif nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid -1
else:
left = mid +1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid -1
return False
或許有用的知識點：
這道題要用到二分算法。
二分算法的mid值用‘mid = left + (right - left) // 2’比較好，這樣可以最大限度的防止溢出。
解題思路：
二分法，判斷二分點，有幾種可能性：
1.直接 nums[mid] == target
2.當數(shù)組為 [1,2,1,1,1],nums[mid] == nums[left] == nums[right]，需要 left++, right --;
3.當 nums[left]<= nums[mid]，說明是在左半邊的遞增區(qū)域
? a. nums[left] <=target < nums[mid]，說明 target 在 left 和 mid 之間。我們令 right = mid - 1;
? b. 不在之間，我們令 left = mid + 1;
4.當 nums[mid] < nums[right]，說明是在右半邊的遞增區(qū)域
? a. nums[mid] < target <= nums[right]，說明 target 在 mid 和 right 之間，我們令 left = mid + 1
? b. 不在之間，我們令 right = mid - 1;
時間復雜度：O(logn)。
No.82.刪除排序鏈表中的重復元素Ⅱ
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head == None or head.next == None:
return head
dummy = ListNode(-999)
dummy.next = head
slow = dummy
fast =dummy.next
while fast:
while fast.next and slow.next.val == fast.next.val:
fast = fast.next
if slow.next == fast:
slow = fast
else:
slow.next = fast.next
fast = fast.next
return dummy.next
或許有用的知識點：
當處理鏈表且需要考慮空鏈表時，我們或許可以設置一個啞結點，即dummy=LIstNode（-999），dummy.next = head。
這道題可以用快慢指針的思想。
這道題也可以使用遞歸的思想。
解題思路：
先定義一個啞節(jié)點（注意啞節(jié)點的值不能再測試樣例中出現(xiàn)），之后運用快慢指針的思想，按照題目要求只改變指針的指向即可。
優(yōu)解代碼及分析：
優(yōu)解代碼（Python3.8）
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head:
return head
if head.next and (head.val == head.next.val):
while (head.next != None) and (head.val == head.next.val):
head = head.next
return self.deleteDuplicates(head.next)
else:
head.next = self.deleteDuplicates(head.next)
return head
分析：
這種解法使用了遞歸的思想，對鏈表層層遞歸即可。
No.83.刪除排序鏈表中的重復元素
難度：簡單
題目描述：
題解代碼（Python3.8）
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
dummy = ListNode(-999)
dummy.next = head
slow = dummy
fast =dummy.next
while fast:
if slow.val != fast.val:
slow =slow.next
slow.val = fast.val
fast = fast.next
slow.next = None
return head
或許有用的知識點：
當處理鏈表且需要考慮空鏈表時，我們或許可以設置一個啞結點，即dummy=LIstNode（-999），dummy.next = head。
這道題可以用快慢指針的思想。
這道題也可以使用遞歸的思想。
解題思路：
這道題和上一道題‘No.82.刪除排序鏈表中的重復元素Ⅱ’思路差不多，可以說是上一道題‘No.82.刪除排序鏈表中的重復元素Ⅱ’的閹割版。先定義一個啞節(jié)點（注意啞節(jié)點的值不能再測試樣例中出現(xiàn)），之后運用快慢指針的思想，按照題目要求只改變指針的指向即可。
優(yōu)解代碼及分析：
優(yōu)解代碼（Python3.8）
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head:
return head
if head.next and (head.val == head.next.val):
while head.next and (head.val == head.next.val):
head = head.next
return self.deleteDuplicates(head)
else:
head.next = self.deleteDuplicates(head.next)
return head
分析：
這道題和上一道題‘No.82.刪除排序鏈表中的重復元素Ⅱ’思路差不多，可以說是上一道題‘No.82.刪除排序鏈表中的重復元素Ⅱ’的閹割版。這種解法使用了遞歸的思想，對鏈表層層遞歸即可。
No.84.柱狀圖中最大的矩形
難度：困難
題目描述：
題解代碼（Python3.8）
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = []
heights = [0] + heights + [0]
res = 0
for i in range(len(heights)):
while stack and heights[stack[-1]] > heights[i]:
#print('儲存索引的棧',stack,'其棧頂元素',heights[stack[-1]],'>當前元素',heights[i])
tmp = stack.pop()
#print('判斷以原棧頂元素',heights[tmp],'為左端元素向右平移得到的矩形面積',(i-stack[-1]-1)*heights[tmp],'是否比res',res,'大，更新res')
res = max(res,(i-stack[-1]-1)*heights[tmp])
stack.append(i)
#print('將當前元素',heights[i],'入棧,此時儲存索引的棧',stack,'保證了棧仍為遞增棧')
#print('------------- i++ ------------')
return res
或許有用的知識點：
這道題要用到單調(diào)棧的思想。
解題思路：
這道題可以用單調(diào)遞增棧的思想，所謂用單調(diào)遞增棧解決這道題，其實可以把這個想象成鋸木板，如果木板都是遞增的那我很開心，如果突然遇到一塊木板i矮了一截，那我就先找之前最高的一塊（其實就是第i-1塊），計算一下這個木板單獨的面積，然后把它鋸成次高的，這是因為我之后的計算都再也用不著這塊木板本身的高度了。再然后如果發(fā)覺次高的仍然比現(xiàn)在這個i木板高，那我繼續(xù)單獨計算這個次高木板的面積（應該是第i-1和i-2塊），再把它倆鋸短。直到發(fā)覺不需要鋸就比第i塊矮了，那么就再次保證了木板是遞增的，那我繼續(xù)開開心心往右找更高的。當然為了避免到了最后一直都是遞增的，所以可以在最后加一塊高度為0的木板。
以heights=[2,1,5,6,2,3]為例，將代碼連帶注釋一起在IDLE運行的逐步結果如下：
No.85.最大矩形
難度：困難
題目描述：
題解代碼（Python3.8）
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if (not matrix) or (not matrix[0]):
return 0
l_row = len(matrix)
l_col = len(matrix[0])
heights = [0]*(l_col+2)
res = 0
for i in range(l_row):
stack = []
for j in range(l_col):
if matrix[i][j] == '1':
heights[j+1] += 1
else:
heights[j+1] =0
#print('以第',i,'行為底，其高度數(shù)組heights為',heights)
#以下同上一題‘No.84.柱狀圖中最大的矩形’
for j in range(l_col+2):
while stack and heights[stack[-1]] > heights[j]:
#print('儲存索引的棧',stack,'其棧頂元素',heights[stack[-1]],'>當前元素',heights[j])
tmp = stack.pop()
#print('判斷以原棧頂元素',heights[tmp],'為左端元素向右平移得到的矩形面積',(j-stack[-1]-1)*heights[tmp],'是否比res',res,'大，更新res')
res = max(res,(j-stack[-1]-1)*heights[tmp])
stack.append(j)
#print('將當前元素',heights[j],'入棧,此時儲存索引的棧',stack,'保證了棧仍為遞增棧')
#print('------------- j++ -------------')
return res
或許有用的知識點：
這道題要用到單調(diào)棧的思想。
解題思路：
這道題其實和上一道題‘No.84.柱狀圖中最大的矩形’的解題思路很類似，在0-1二維矩陣中，逐行為底將0-1二維矩陣轉(zhuǎn)換成直方柱的形式，每行解法和上一道題‘No.84.柱狀圖中最大的矩形’就一樣了，如下圖：
這道題可以用單調(diào)遞增棧的思想，所謂用單調(diào)遞增棧解決這道題，其實可以把這個想象成鋸木板，如果木板都是遞增的那我很開心，如果突然遇到一塊木板i矮了一截，那我就先找之前最高的一塊（其實就是第i-1塊），計算一下這個木板單獨的面積，然后把它鋸成次高的，這是因為我之后的計算都再也用不著這塊木板本身的高度了。再然后如果發(fā)覺次高的仍然比現(xiàn)在這個i木板高，那我繼續(xù)單獨計算這個次高木板的面積（應該是第i-1和i-2塊），再把它倆鋸短。直到發(fā)覺不需要鋸就比第i塊矮了，那么就再次保證了木板是遞增的，那我繼續(xù)開開心心往右找更高的。當然為了避免到了最后一直都是遞增的，所以可以在最后加一塊高度為0的木板。
以代碼中的matrix（同題目樣例）為例，將代碼連帶注釋一起在IDLE運行，運行的代碼和代碼每一行運行的逐步結果如下：
