剑指offer（四）

柔情只为你懂 2022-02-18 11:27 247阅读 0赞

剑指offer（16-20）。

### 合并两个排序的链表 ###

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

**思路**

1.  递归
2.  非递归

**代码实现**

class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
    #递归方法
    class Solution:
        # 返回合并后列表
        def Merge(self, pHead1, pHead2):
            list_merge=None    #构建一个新的链表存储合并后的链表
            if pHead1==None:   #一个为空就返回另外一个链表
                return pHead2
            if pHead2==None:
                return pHead1
    
            if pHead1.val<=pHead2.val:
                list_merge=pHead1
                list_merge.next=self.Merge(pHead1.next,pHead2)
            else:
                list_merge=pHead2
                list_merge.next=self.Merge(pHead1,pHead2.next)
            return list_merge
    
    #非递归方法
    class Solution2:
        # 返回合并后列表
        def Merge(self, pHead1, pHead2):
            head=ListNode(90)
            p=head
            if pHead1==None:
                return pHead2
            if pHead2==None:
                return pHead1
            while pHead1 and pHead2:
                if pHead1.val<=pHead2.val:
                    head.next=pHead1
                    pHead1=pHead1.next
                else:
                    head.next=pHead2
                    pHead2=pHead2.next
                head=head.next           #后移，方便链接下一次循环中选取的结点
            if pHead1:                   #pHead1和pHead2一个为空，将其链接到合并后的链表中
                head.next=pHead1
            if pHead2:
                head.next=pHead2
            return p.next

### 树的子结构 ###

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

**思路**

1.  递归

**代码实现**

class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    class Solution:
        def HasSubtree(self, pRoot1, pRoot2):
            result=False
            if pRoot1!=None and pRoot2!=None:                      #当Tree1和Tree2都不为空时比较，否则直接返回False
                if pRoot1.val==pRoot2.val:                         #如果找到了对应Tree2根节点的点
                    result=self.doesTree1haveTree2(pRoot1,pRoot2)  #以这个根节点为起点判断是否包含Tree2
                if not result:
                    result=self.HasSubtree(pRoot1.left,pRoot2)     #如果没找到，去root左儿子当作起点，递归判断是否包含Tree2
                if not result:
                    result=self.HasSubtree(pRoot1.right,pRoot2)    #如果没找到，去root右儿子当作起点，递归判断是否包含Tree2
            return result
    
        def doesTree1haveTree2(self,node1,node2):
            if node2==None:                         #如果Tree2已经遍历完了都能对上，返回True
                return True
            if node1==None:                         #如果Tree2还没遍历完，Tree1却遍历完了，返回False
                return False
            if node1.val!=node2.val:                #其中只要有一个节点没对上，返回False
                return False
            #如果根节点对应的上，再分别去子节点里匹配
            return self.doesTree1haveTree2(node1.left,node2.left) and self.doesTree1haveTree2(node1.right,node2.right)

### 二叉树的镜像 ###

**题目描述**  
操作给定的二叉树，将其变换为源二叉树的镜像。  
二叉树的镜像定义：源二叉树  
8  
/  
6 10  
/ \\ /  
5 7 9 11  
镜像二叉树  
8  
/  
10 6  
/ \\ /  
11 9 7 5

**思路**

1.  递归
2.  非递归，借用一个栈或者队列

**代码实现**

class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    #方法一，递归
    class Solution:
        # 返回镜像树的根节点
        def Mirror(self, root):
            if root==None:
                return None
            if root:
                root.left,root.right=root.right,root.left   #翻转根节点的左右孩子结点
                if root.left!=None:                         #递归翻转左子树
                    self.Mirror(root.left)
                if root.right!=None:                        #递归翻转右子树
                    self.Mirror(root.right)
            return root
    
    #方法二，非递归，借用一个栈实现（其实借用一个队列也可以，思路是一样的）
    class Solution2:
        # 返回镜像树的根节点
        def Mirror(self, root):
            if root==None:
                return None
            result=[]             #创建一个空栈
            result.append(root)
            while result:
                tree=result[-1]  #取栈顶元素
                result.pop(-1)   #栈顶元素出栈
                if (tree.left!=None or tree.right!=None):       #交换结点的左右孩子
                    tree.left,tree.right=tree.right,tree.left
                if tree.left:                                  #左孩子入栈
                    result.append(tree.left)
                if tree.right:
                    result.append(tree.right)                 #右孩子入栈
            return root

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

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

**思路**

1.  可以模拟魔方逆时针旋转的方法，一直做取出第一行的操作  
    例如  
    1 2 3  
    4 5 6  
    7 8 9  
    输出并删除第一行后，再进行一次逆时针旋转，就变成：  
    6 9  
    5 8  
    4 7  
    继续重复上述操作即
2.  按照矩阵最上一行、最右一列，最下一行和最左一列分别处理

**代码实现**

class Solution:
        # matrix类型为二维列表，需要返回列表
        def printMatrix(self, matrix):
            result=[]                           #最终顺时针读取完成后的列表
            while matrix:
                result+=matrix.pop(0)           #循环取出矩阵第一行
                if not matrix or not matrix[0]: #矩阵是否为空，个人感觉matrix[0]这个判断没有必要
                    break
                matrix=self.turn(matrix)       #逆时针旋转矩阵
            return result
    
        def turn(self,matrix):
            rows=len(matrix)                 #矩阵的行数
            cols=len(matrix[0])              #矩阵列数
            new_matrix=[]                    #最终逆时针旋转后的矩阵
            for i in range(cols):
                new_matrix_cut=[]            #存储每一次循环时，每一列的矩阵值
                for j in range(rows):
                    new_matrix_cut.append(matrix[j][i])
                new_matrix.append(new_matrix_cut)       #每一列读取完后，附加到总的矩阵列表
            new_matrix.reverse()                        #列表中的矩阵反转
            return new_matrix
    
    #方法二
    class Solution2:
        def printMatrix(self, matrix):
            res = []                              #最终顺时针读取完成后的列表
            while matrix:
                res += matrix.pop(0)             #从前向后读取最上面的一行数据
                if matrix and matrix[0]:
                    for row in matrix:           #读取最右边的一列（即每一行的最后一个数据）
                        res.append(row.pop())
                if matrix:                       #从后向前读取最下边的一行
                    res += matrix.pop()[::-1]
                if matrix and matrix[0]:        # 读取最左边一列的数据（即每一行的第一个数据）
                    for row in matrix[::-1]:
                        res.append(row.pop(0))
            return res

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

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

**思路**

1.  设置一个辅助栈来存储最小的元素

**代码实现**

class Solution:
        def __init__(self):
            self.stack=[]            #主栈
            self.min_stack=[]        #辅助栈，存储最小的元素
    
        def push(self, node):        #入栈
            self.stack.append(node)   #新元素入主栈
            if not self.min_stack or node<self.min_stack[-1]: #如果辅助栈为空或者新元素比辅助栈顶元素小，新元素也入辅助栈
                self.min_stack.append(node)
    
        def pop(self):              #出栈
            if self.min_stack[-1]==self.stack[-1]: #如果辅助栈顶元素和主栈顶元素相同，辅助栈顶元素出栈
                self.min_stack.pop()
            self.stack.pop()                      #主栈顶元素出栈
    
        def top(self):                            #返回栈顶元素
            return self.stack[-1]
    
        def min(self):                           #最小值为辅助栈顶元素值
            return self.min_stack[-1]