剑指offer全集python（1/3）第一大部分

ゞ浴缸里的玫瑰 2022-03-02 06:54 178阅读 0赞

**目录**

2.使用python实现单例模式

3.二维数组中数的搜索

4.替换空格

5.从尾到头打印单链表值

6.根据前序，中序构造二叉树

7.使用2个栈实现队列

8.旋转数组的最小数字

9.斐波那契数列

14.调整数组顺序使奇数位于偶数前面

15.链表中倒数第k个结点

16.反转单链表

17.合并两个有序的链表

18.树的子结构

19.二叉树的镜像

20.顺时针打印矩阵

21.包含min函数的栈

22. 栈的压入弹出序列

--------------------

![2020042316344868.PNG][]

### 2.使用python实现单例模式 ###

#使用python 实现单例模式
    #单例模式（Singleton Pattern）是一种常用的软件设计模式，该模式的主要目的是确保某一个类只有一个实例存在。
    
    #1.__new__ 是什么
    # __new__方法接受的参数虽然也是和__init__一样，但__init__是在类实例创建之后调用，而 __new__方法正是创建这个类实例的方法。
    # __new__ 方法必须返回值，__init__方法不需要返回值。
    
    class Human(object):
        def __new__(cls, *agrs, **kwargs):
            a = object.__new__(cls, *agrs, **kwargs)
            print('__new__')
            print(a)
            return a  # __new__ 方法必须返回值，__init__方法不需要返回值。
    
        def __init__(self, name='lisi'):
            print('__init__')
            print(self)
            self.name = name
            
        def getName(self):
            print(self.name)
    
    hu = Human() #不能传参数
    hu.getName()
    #可以发现： __new__方法的调用是发生在__init__之前的
    # __new__
    # <__main__.Human object at 0x00000000021FF5F8>
    # __init__
    # <__main__.Human object at 0x00000000021FF5F8>
    # lisi
    
    # 对于int这种 不可变的对象，我们只有重载它的__new__方法才能起到自定义的作用, 而 __init__ 方法是不起作用的。   
    class PositiveInteger(int):
        def __new__(cls, value):
            return super(PositiveInteger, cls).__new__(cls, abs(value))
        
    poi = PositiveInteger(-3)
    print(poi) # 3
    
    #使用__new__ 实现单例模式
    class Singlton(object):
        _instance = None
        def __new__(cls, *args, **kwargs):
            if not cls._instance:
                cls._instance = super(Singlton, cls).__new__(cls, *args, **kwargs)
            return cls._instance
    
    class myClass(Singlton):
        pass
        
    a = myClass()
    b = myClass()
    print(a is b )  #True
    print(a == b) #True 
    print(id(a), id(b)) # 40345672 40345672
    
    # 装饰器： 它可以让其他函数或类在不需要做任何代码修改的前提下增加额外功能，装饰器的返回值也是一个函数/类对象。装饰器的作用就是为已经存在的对象添加额外的功能
    #初始的函数
    def myFunc(): #需要增加功能的函数
        print('myFunc call')
        
    def deco(func): # 将函数作为参数
        def wrapper():
            print('before func') #假设为增加的功能 1
            func()
            print('afther func')# 增加的功能2 
        return wrapper 
    
    myFunc = deco(myFunc)
    myFunc() #直接调用原来的函数
    # before func
    # myFunc call
    # afther func
    
    @deco  # 语法糖
    def myFunc2():  #对函数进行功能扩展
        print('this is my Function2')
    myFunc2() #@ 相当于省略了myFunc2 = deco(myFunc2)
    
    #-----对带有参数的函数进行功能扩展-----
    def deco2(func):
        def wrapper(a, b):
            print('before func ')
            res = func(a, b)
            print('afther func')
            return res
        return wrapper 
    
    @deco2 
    def func2(a, b):
        print('res is %d'%(a+b))
        return a+b 
    
    res = func2(2, 5)
    print(res)
    
    #-----对参数不确定数的函数进行功能扩展-----
    def deco3(func):
        def wrapper(*args, **kwargs):
            print('before func')
            res = func(*args, **kwargs)
            print('afther func ')
            return res 
        return wrapper 
    
    @deco3 
    def func3(a, b, c, d):
        res = a+b+c+d
        print('sum is %d'%(res))
        return res 
    func3(1, 2, 3, 4)
    
    @deco3
    def func4(a, b, c):
        res = a + b + c 
        print('sum is %d'%(res))
        return res 
    func4(1, 2, 3)
    
    #-----使用装饰器实现单例模式-----
    
    def singleton(cls, *args, **kwargs):
        instance = {}
        def getInstance():
            if cls not in instance:
                instance[cls] = cls(*args, **kwargs)
            return instance[cls]
        return getInstance
    
    @singleton 
    class myClass2(object):
        a = 1 
    
    a = myClass2()
    b = myClass2()
    print(a is b)
    print(a == b)

### 3.二维数组中数的搜索 ###

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

*  每行的元素从左到右升序排列。
 *  每列的元素从上到下升序排列。

**示例:**

现有矩阵 matrix 如下：

[
      [1,   4,  7, 11, 15],
      [2,   5,  8, 12, 19],
      [3,   6,  9, 16, 22],
      [10, 13, 14, 17, 24],
      [18, 21, 23, 26, 30]
    ]

给定 target = `5`，返回 `true`。

给定 target = `20`，返回 `false`。

思路：从左下角或者右上角开始比较

class Solution(object):
        def searchMatrix(self, matrix, target):
            """
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            """
            
            if not matrix:
                return False
            
            rows, cols = len(matrix), len(matrix[0])
            #从左下角开始搜索
            row, col = rows - 1, 0
            while row >= 0 and col <= cols-1:
                if matrix[row][col] == target:
                    return True 
                elif matrix[row][col] < target:
                    col += 1
                else:
                    row -= 1 # row一直减少
            return False

### 4.替换空格 ###

<table> 
 <tbody> 
  <tr> 
   <td>请实现一个函数，将一个字符串中的空格替换成“%20”。</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。</td> 
  </tr> 
 </tbody> 
</table>

**\# 下列的字符串是 不可变对象，使用 + 操作时，会产生许多的对象，所以最好使用第二种方法**

class Solution():
        
        def replaceSpace(self, s):
            if type(s) != str:
                return 
            new_s = ''
            for sr in s:
                if sr == ' ':
                    new_s += '%20'
                else:
                    new_s += sr 
            return new_s 
    so = Solution()
    s = ' ab c d e '
    print(so.replaceSpace(s))
    # %20ab%20c%20d%20e%20
    print(s.replace(' ', '%20'))

**第二种方法：转换成列表形式**

class Solution:
        def replaceSpace(self, s):
            if type(s) != str:
                return
            li = list(s)
            for i in range(len(li)):
                if li[i] == ' ':
                    li[i] = '%20'
            res = "".join(li)
            return res
    so = Solution()
    s = ' ab c d e '
    print(so.replaceSpace(s))

### 5.从尾到头打印单链表值 ###

# 从尾到头依次打印单链表的值
    class ListNode:
        def __init__(self, x=None):
            self.val = x
            self.next = None
    
    class Solution:
        def printListFromTailToHead(self, listNode):
            if not listNode: #如果头部结点为空
                return 
            stack = []
            while listNode:
                stack.append(listNode.val)
                listNode = listNode.next 
            while stack:
                print(stack.pop())
    #         return sorted(stack, reverse=True)   
     
        def printListFromTailToHead2(self, listNode):
            if not listNode:
                return 
            li = []
            while listNode:
                li.insert(0, listNode.val)
                listNode = listNode.next 
            return li 
    
    node1 = ListNode(10)
    node2 = ListNode(11)
    node3 = ListNode(13)
    node1.next = node2
    node2.next = node3
    
    singleNode = ListNode(12)
    
    test = ListNode()
    
    S = Solution()
    print(S.printListFromTailToHead2(node1))
    print(S.printListFromTailToHead2(test))
    print(S.printListFromTailToHead2(singleNode))

### 6.根据前序，中序构造二叉树 ###

根据一棵树的前序遍历与中序遍历构造二叉树。

**注意:**  
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]  中， 左， 右
    中序遍历 inorder = [9,3,15,20,7]   左， 中， 右

返回如下的二叉树：

3
       / \
      9  20
        /  \
       15   7

思路：前序的第一个元素是根结点的值，在中序中找到该值，中序中该值的左边的元素是根结点的左子树，右边是右子树，然后递归的处理左边和右边

利用二叉树前序遍历和中序遍历的特性。前序遍历的第一个值一定为根节点，对应于中序遍历中间的一个点。在中序遍历序列中，这个点左侧的均为根的左子树，这个点右侧的均为根的右子树。这时可以利用递归，分别取前序遍历\[1:i+1\]和中序遍历的\[:i\]对应与左子树继续上一个过程，取前序遍历\[i+1:\]和中序遍历\[i+1\]对应于右子树继续上一个过程，最终得以重建二叉树。

'''
    输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
    假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
    例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
    '''
    
    class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    class Solution:
        # 返回构造的TreeNode根节点
        def reConstructBinaryTree(self, pre, tin):
            if not pre or not tin: #只要一个数组为空，则退出函数
                return 
            if set(pre) != set(tin):#如果数组中有重复元素
                return 
            
            root = TreeNode(pre[0])
            i = tin.index(pre[0])
            
            root.left = self.reConstructBinaryTree(pre[1: i+1], tin[: i])
            root.right = self.reConstructBinaryTree(pre[i+1: ], tin[i+1: ])
            return root
        
    pre = [1, 2, 3, 5, 6, 4]
    tin = [5, 3, 6, 2, 4, 1]
    test = Solution()
    newTree = test.reConstructBinaryTree(pre, tin)
    print(newTree)
    #中序遍历
    def inorder(newTree):
        if newTree:
            inorder(newTree.left)
            print(newTree.val)
            inorder(newTree.right)
    inorder(newTree)

### 7.使用2个栈实现队列 ###

需要两个栈Stack1和Stack2，push的时候直接push进Stack1。pop需要判断Stack1和Stack2中元素的情况，Stack1空的话，直接从Stack2 pop，Stack1不空的话，把Stack1的元素push进入Stack2，然后pop Stack2的值。

1.push: 直接push进stack1。需要pop全部stack2，才开始将stack1元素放进stack2中

2.pop：if stack2 不为空，直接pop stack2； if stack2 为空，需要将stack1元素全部放入stack2中，然后pop

# -*- coding:utf-8 -*-
    class Solution:
        def __init__(self):
            self.stack1 = []
            self.stack2 = []
            
        def push(self, node):
            # write code here
            self.stack1.append(node)
            
        def pop(self):
            # return xx
            if not self.stack1 and not self.stack2: 
                return 
            
            if not self.stack2: #如果stack2为空
                while self.stack1:
                    self.stack2.append(self.stack1.pop())
            return self.stack2.pop()

**延伸：两个队列实现栈：**

# 使用两个队列实现栈
    class Solution:
        def __init__(self): # 队列 不是这个为空就是 另一个为空
            self.queue1 = []
            self.queue2 = []
            
        def push(self, node):
            if not self.queue2: # 如果队列 2 为空的话
                self.queue1.append(node)
            else:
                self.queue2.append(node)
        
        def pop(self):
            if not self.queue1 and not self.queue2:
                return 
            
            if not self.queue2:
                length = len(self.queue1)
                for i in range(length-1):
                    self.queue2.append(self.queue1.pop(0)) # 将数组的依次首个元素弹出，只留下最后一个元素
                return self.queue1.pop() # 此时queue1 为空
                
            else:
                length = len(self.queue2)
                for i in range(length-1):
                    self.queue1.append(self.queue2.pop(0))
                return self.queue2.pop()
                
    P = Solution()
    P.push(10)
    P.push(11)
    P.push(12)
    print(P.pop())
    P.push(13)
    print(P.pop())
    print(P.pop())
    print(P.pop())
    print(P.pop())

### 8.旋转数组的最小数字 ###

<table> 
 <tbody> 
  <tr> 
   <td>把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。</td> 
  </tr> 
 </tbody> 
</table>

**二分查找的变形，注意到旋转数组的首元素肯定不小于旋转数组的尾元素，设置中间点。如果中间点大于首元素，说明最小数字在后面一半，如果中间点小于尾元素，说明最小数字在前一半。依次循环。同时，当一次循环中首元素小于尾元素，说明最小值就是首元素。但是当首元素等于尾元素等于中间值，只能在这个区域顺序查找。**

-*- coding:utf-8 -*-
    class Solution:
        def minNumberInRotateArray(self, rotateArray):
            # write code here
            if not rotateArray:
                return 0
            
            length = len(rotateArray)
            left, right = 0, length-1
            if rotateArray[left] < rotateArray[right]: #如果第一个数都比最后一个数小，则代表没有旋转
                return rotateArray[left]
            
            minVal = rotateArray[0]
            while (right - left) > 1:
                mid = (left + right) // 2
                if rotateArray[mid] >= rotateArray[left]:
                    left = mid 
                elif rotateArray[mid] <= rotateArray[right]:
                    right = mid 
                elif rotateArray[right] == rotateArray[left] == rotateArray[mid]:
                    for i in range(length):
                        if minVal > rotateArray[i]:
                            minVal = rotateArray[i]
                            right = i 
            minVal = rotateArray[right]
            return minVal

# -*- coding:utf-8 -*-
    class Solution:
        def minNumberInRotateArray(self, rotateArray):
            # write code here
            if not rotateArray:
                return 0
            
            minIndex = 0
            left, right = 0, len(rotateArray)-1
            while rotateArray[left] >= rotateArray[right]:
                if right - left == 1:
                    minIndex = right 
                    break  #退出循环
                mid = (left + right) // 2
                if rotateArray[mid] >= rotateArray[left]:
                    left = mid 
                elif rotateArray[mid] <= rotateArray[right]:
                    right = mid 
                #特殊情况[1, 1, 0, 1]
                elif rotateArray[mid] == rotateArray[left] == rotateArray[right]:
                    for i in range(len(rotateArray)):
                        if rotateArray[minIndex] > rotateArray[i]:
                            minIndex = i 
                            
            return rotateArray[minIndex]

不使用二分法

# -*- coding:utf-8 -*-
    class Solution:
        def minNumberInRotateArray(self, rotateArray):
            # write code here
            if not rotateArray:
                return 0
            
            minVal = rotateArray[0]
            for i in range(len(rotateArray)):
                if minVal > rotateArray[i]:
                    minVal = rotateArray[i]
                    res = i 
            return rotateArray[res]

### 9.斐波那契数列 ###

递归的形式

# -*- coding:utf-8 -*-
    class Solution:
        def Fibonacci(self, n):
            # write code here
            a, b = 0, 1
            if n == 0:
                return 0 
            if n == 1:
                return 1 
            return self.Fibonacci(n-1) + self.Fibonacci(n-2)

非递归形式

# -*- coding:utf-8 -*-
    class Solution:
        def Fibonacci(self, n):
            # write code here
            a, b = 0, 1
            if n == 0:
                return 0
            for i in range(n):
                a, b = b, a+b 
            return a

### 14.**调整数组顺序使奇数位于偶数前面** ###

**题目描述**

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

# -*- coding:utf-8 -*-
    class Solution:
        def reOrderArray(self, array):
            # write code here
            li1, li2 = [], []
            for ar in array:
                if ar % 2 == 1:
                    li1.append(ar)
                else:
                    li2.append(ar)
            return li1 + li2

# -*- coding:utf-8 -*-
    class Solution:
        def reOrderArray(self, array):
            # write code here
            left = [ar for ar in array if ar % 2 ==1]
            right = [ar for ar in array if ar % 2 == 0]
            return left + right

### 15.链表中倒数第k个结点 ###

输入一个链表，输出该链表中倒数第k个结点。

<table> 
 <tbody> 
  <tr> 
   <td>如果在只希望一次遍历的情况下, 寻找倒数第k个结点, 可以设置两个指针</td> 
  </tr> 
  <tr> 
   <td>第一个指针先往前走k-1步, 然后从第k步开始第二个指针指向头结点</td> 
   <td>&nbsp;</td> 
  </tr> 
  <tr> 
   <td>然后两个指针一起遍历</td> 
  </tr> 
  <tr> 
   <td>当地一个指针指向尾节点的时候, 第二个指针正好指向倒数第k个结点</td> 
   <td>&nbsp;</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
  </tr> 
 </tbody> 
</table>

# -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def FindKthToTail(self, head, k):
            # write code here
            if not head or k <= 0:
                return None 
            
            pBehind = head  
            for i in range(k-1): #找到第 k-1 个结点
                if pBehind.next != None:
                    pBehind = pBehind.next 
                else:
                    return None
    
            pHead = head
            while pBehind.next != None: # 然后一起往前走
                pBehind = pBehind.next 
                pHead = pHead.next 
                
            return pHead

### 16.反转单链表 ###

输入的链表头指针为None或者整个链表只有一个结点时，反转后的链表出现断裂，返回的翻转之后的头节点不是原始链表的尾结点。因此需要引入一个翻转后的头结点，以及一个指向当前结点的指针，一个指向当前结点前一个结点的指针，一个指向当前结点后一个结点的指针，防止出现断裂。推广：递归实现反转链表

# Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def reverseList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if not head or not head.next: #如果头结点为空，或者只有一个结点的haul
                return head 
            #x需要使用3 个结点
            then = head.next 
            head.next = None  #将头结点的next指向空
            last = then.next 
            
            while then:
                then.next = head  #将其指向头结点
                head = then  # 更新头结点
                then = last 
                if then:
                    last = then.next 
            return head

一种更为简单的实现方法;

#!/usr/bin/env python
    # -*- coding: utf-8 -*-
    """
    __title__ = ''
    __author__ = 'mike_jun'
    __mtime__ = '2019-5-24'
    #目的： 反转单链表
    
    """
    def reverseLink(head):
        #pass
        if not head or not head.next:
            return head
        p = head
        newHead = None
        while p:
            temp = p.next
            p.next = newHead
            newHead = p
            p = temp
        return newHead
    
    #创建一个单链表
    class Node():
        def __init__(self, values):
            self.next = None
            self.values = values
    
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3)
    node4 = Node(4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    
    def printNode(head):
        result = []
        while head:
            result.append(head.values)
            head = head.next
        print(result)
    printNode(node1)
    newNode = reverseLink(node1)
    printNode(newNode)

递归方法实现：

# -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution:
        # 返回ListNode
        def ReverseList(self, pHead):
            # write code here
            if not pHead or not pHead.next:
                return pHead 
            else:
                reverseHead = self.ReverseList(pHead.next)
                pHead.next.next = pHead 
                pHead.next = None 
            return reverseHead

### 17.合并两个有序的链表 ###

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

使用递归方法

# -*- coding:utf-8 -*-
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution:
        # 返回合并后列表
        def Merge(self, pHead1, pHead2):
            # write code here
            if not pHead1: #如果一个链表不存在的话，返回另外一个链表
                return pHead2
            if not pHead2:
                return pHead1
            
            if pHead1.val <= pHead2.val:
                ret = pHead1
                ret.next = self.Merge(pHead1.next, pHead2)
            else:
                ret = pHead2
                ret.next = self.Merge(pHead1, pHead2.next)
                
            return ret

**2.非递归实现合并两个有序的链表**

#非递归实现合并两个有序的链表
    class Solution1:
        # 返回合并后列表
        def Merge(self, pHead1, pHead2):    
            if not pHead1:
                return pHead2
            if not pHead2:
                return pHead1
            
            start = None 
            p = None 
            while pHead1 and pHead2:
                if pHead1.val <= pHead2.val:
                    print(pHead1.val)
                    if start is None:
                        start = p = pHead1
                    else:
                        p.next = pHead1
                        p = p.next #更新p 结点
                    pHead1 = pHead1.next # 更新有序链表的结点
                else:
                    if start is None:
                        start = p = pHead2
                    else:
                        p.next = pHead2
                        p = p.next 
                    pHead2 = pHead2.next 
            #可能某个链表一直还剩值
            if not pHead1: #如果第一个链表都是空的话
                p.next = pHead2
            else:
                p.next = pHead1
            return start

### 18.树的子结构 ###

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        def HasSubtree(self, pRoot1, pRoot2):
            # write code here
            result = False 
            if pRoot1 and pRoot2: #如果两颗树结点都不为空
                if pRoot1.val == pRoot2.val:# 如果结点的值相同的话
                    result = self.DoseSubtree(pRoot1, pRoot2)
                if not result: # 不相同，则判断tree1 左子树结构
                    result = self.HasSubtree(pRoot1.left, pRoot2)
                if not result:
                    result = self.HasSubtree(pRoot1.right, pRoot2)
            return result
                    
        def DoseSubtree(self, pRoot1, pRoot2):
            if not pRoot2: #如果tree2 树为空的话，说明就是子树
                return True 
            if not pRoot1:
                return False
            if pRoot1.val != pRoot2.val:
                return False
            
    # 继续判断1,2左子树和1,2右子树
            return self.DoseSubtree(pRoot1.left, pRoot2.left) and self.DoseSubtree(pRoot1.right, pRoot2.right)

### 19.二叉树的镜像 ###

**题目描述**

操作给定的二叉树，将其变换为源二叉树的镜像。

**输入描述:**

二叉树的镜像定义：源二叉树 
        	    8
        	   /  \
        	  6   10
        	 / \  / \
        	5  7 9 11
        	镜像二叉树
        	    8
        	   /  \
        	  10   6
        	 / \  / \
        	11 9 7  5

**递归实现：**

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # 返回镜像树的根节点
        def Mirror(self, root):
            # write code here
            if not root:
                return None 
            if not root.left and not root.right:
                return root 
            root.left, root.right = root.right, root.left 
            self.Mirror(root.left)
            self.Mirror(root.right)

**非递归，队列实现**

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # 返回镜像树的根节点
        def Mirror(self, root):
            # write code here
            if not root:
                return None 
            nodeQue = [root]
            while len(nodeQue) > 0:
                nodeNum, count = len(nodeQue), 0
                while nodeNum > count:
                    count += 1
                    node = nodeQue.pop(0)
                    node.left, node.right = node.right, node.left 
                    if node.left:
                        nodeQue.append(node.left)
                    if node.right:
                        nodeQue.append(node.right)

### 20.顺时针打印矩阵 ###

**题目描述**

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

matrix类型为二维列表，需要返回列表

# -*- coding:utf-8 -*-
    class Solution:
        # matrix类型为二维列表，需要返回列表
        def printMatrix(self, matrix):
            if matrix == None:
                return
            rows = len(matrix)
            columns = len(matrix[0])
            start = 0
            while rows > start * 2 and columns > start * 2:
                self.PrintMatrixInCircle(matrix, columns, rows, start)
                start += 1
            print('')
    
        def PrintMatrixInCircle(self, matrix, columns, rows, start):
            endX = columns - 1 - start
            endY = rows - 1 - start
    
            # 从左到右打印一行
            for i in range(start, endX+1):
                number = matrix[start][i]
                print(number, ' ', end='')
    
            # 从上到下打印一行
            if start < endY:
                for i in range(start+1, endY+1):
                    number = matrix[i][endX]
                    print(number, ' ', end='')
    
            # 从右到左打印一行
            if start < endX and start < endY:
                for i in range(endX-1, start-1, -1):
                    number = matrix[endY][i]
                    print(number, ' ', end='')
    
            # 从下到上打印一行
            if start < endX and start < endY-1:
                for i in range(endY-1, start, -1):
                    number = matrix[i][start]
                    print(number, ' ', end='')

### 21.包含min函数的栈 ###

**题目描述**

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

# -*- coding:utf-8 -*-
    class Solution:
        def __init__(self): #使用两个栈来实现，两个栈的大小是相同的
            self.stack = []
            self.minStack = []
        
        def push(self, node):
            # write code here
            self.stack.append(node)
            if not self.minStack or self.min() > node: # 将最小值增加到minStack中
                self.minStack.append(node)
            else:
                self.minStack.append(self.min())
            
        def pop(self):
            # write code here
            if self.stack and self.minStack:
                self.stack.pop()
                self.minStack.pop()
            else:
                return None 
            
        def top(self):
            # write code here
            return self.stack[-1]
        def min(self):
            # write code here
            return self.minStack[-1]

### 22. 栈的压入弹出序列 ###

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

建立一个辅助栈，把push序列的数字依次压入辅助栈，每次压入后，比较辅助栈的栈顶元素和pop序列的首元素是否相等，相等的话就推出pop序列的首元素和辅助栈的栈顶元素，若最后辅助栈为空，则push序列可以对应于pop序列。

# -*- coding:utf-8 -*-
    class Solution:
        def IsPopOrder(self, pushV, popV):
            # write code here
            if not pushV or not popV:
                return False 
            
            stack = [] #建立一个辅助的栈
            for val in pushV:
                stack.append(val)
                while popV and stack[-1] == popV[0]:
                    stack.pop()
                    popV.pop(0)
            if not stack: #如果辅助栈为空的话，则表示正确
                return True 
            else:
                return False

# [剑指offer（2/3）第二大部分][offer_2_3] #

# [剑指offer（3/3）第三大部分][offer_3_3] #

[2020042316344868.PNG]: /images/20220302/64f06328ec2044578a6e01b6a24ef425.png
[offer_2_3]: https://blog.csdn.net/qq_40587575/article/details/88767488
[offer_3_3]: https://blog.csdn.net/qq_40587575/article/details/88920399