Python小白 Leetcode刷题历程 No.81-No.85 搜索旋转排序数组Ⅱ、删除排序链表中的重复元素Ⅱ、删除排序链表中的重复元素、柱状图中最大的矩形、最大矩形

写在前面：

作为一个计算机院的大学生，总觉得仅仅在学校粗略的学习计算机专业课是不够的，尤其是假期大量的空档期，作为一个小白，实习也莫得路子，又不想白白耗费时间。于是选择了Leetcode这个平台来刷题库。编程我只学过基础的C语言，现在在自学Python，所以用Python3.8刷题库。现在我Python掌握的还不是很熟练，算法什么的也还没学，就先不考虑算法上的优化了，单纯以解题为目的，复杂程度什么的以后有时间再优化。计划顺序五个题写一篇日志，希望其他初学编程的人起到一些帮助，写算是对自己学习历程的一个见证了吧。

有一起刷LeetCode的可以关注我一下，我会一直发LeetCode题库Python3解法的，也可以一起探讨。

觉得有用的话可以点赞关注下哦，谢谢大家！
········································································································································································
题解框架：

    1.题目，难度
    2.题干,题目描述
    3.题解代码（Python3（不是Python，是Python3））
    4.或许有用的知识点（不一定有）
    5.解题思路
    6.优解代码及分析（当我发现有比我写的好很多的代码和思路我就会写在这里）

········································································································································································

No.81.搜索旋转排序数组Ⅱ

难度：中等
题目描述：

在这里插入图片描述

题解代码（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.当数组为 [1,2,1,1,1],nums[mid] == nums[left] == nums[right]，需要 left++, right --;
3.当 nums[left]<= nums[mid]，说明是在左半边的递增区域
​ a. nums[left] <=target < nums[mid]，说明 target 在 left 和 mid 之间。我们令 right = mid - 1;
​ b. 不在之间，我们令 left = mid + 1;
4.当 nums[mid] < nums[right]，说明是在右半边的递增区域
​ 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。
这道题可以用快慢指针的思想。
这道题也可以使用递归的思想。

解题思路：
先定义一个哑节点（注意哑节点的值不能再测试样例中出现），之后运用快慢指针的思想，按照题目要求只改变指针的指向即可。

优解代码及分析：
优解代码（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.删除排序链表中的重复元素Ⅱ’的阉割版。先定义一个哑节点（注意哑节点的值不能再测试样例中出现），之后运用快慢指针的思想，按照题目要求只改变指针的指向即可。

优解代码及分析：
优解代码（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

或许有用的知识点：
这道题要用到单调栈的思想。

解题思路：
这道题可以用单调递增栈的思想，所谓用单调递增栈解决这道题，其实可以把这个想象成锯木板，如果木板都是递增的那我很开心，如果突然遇到一块木板i矮了一截，那我就先找之前最高的一块（其实就是第i-1块），计算一下这个木板单独的面积，然后把它锯成次高的，这是因为我之后的计算都再也用不着这块木板本身的高度了。再然后如果发觉次高的仍然比现在这个i木板高，那我继续单独计算这个次高木板的面积（应该是第i-1和i-2块），再把它俩锯短。直到发觉不需要锯就比第i块矮了，那么就再次保证了木板是递增的，那我继续开开心心往右找更高的。当然为了避免到了最后一直都是递增的，所以可以在最后加一块高度为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,'行为底，其高度数组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

或许有用的知识点：
这道题要用到单调栈的思想。

解题思路：
这道题其实和上一道题‘No.84.柱状图中最大的矩形’的解题思路很类似，在0-1二维矩阵中，逐行为底将0-1二维矩阵转换成直方柱的形式，每行解法和上一道题‘No.84.柱状图中最大的矩形’就一样了，如下图：

在这里插入图片描述

这道题可以用单调递增栈的思想，所谓用单调递增栈解决这道题，其实可以把这个想象成锯木板，如果木板都是递增的那我很开心，如果突然遇到一块木板i矮了一截，那我就先找之前最高的一块（其实就是第i-1块），计算一下这个木板单独的面积，然后把它锯成次高的，这是因为我之后的计算都再也用不着这块木板本身的高度了。再然后如果发觉次高的仍然比现在这个i木板高，那我继续单独计算这个次高木板的面积（应该是第i-1和i-2块），再把它俩锯短。直到发觉不需要锯就比第i块矮了，那么就再次保证了木板是递增的，那我继续开开心心往右找更高的。当然为了避免到了最后一直都是递增的，所以可以在最后加一块高度为0的木板。
以代码中的matrix（同题目样例）为例，将代码连带注释一起在IDLE运行，运行的代码和代码每一行运行的逐步结果如下：

在这里插入图片描述
在这里插入图片描述