剑指offer（四）

发表于 | 更新于 | 分类于 | 阅读次数
字数统计 1.6k | 阅读时长 7

剑指offer（16-20）。

合并两个排序的链表

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

思路

  1. 递归
  2. 非递归

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

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. 递归

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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. 非递归，借用一个栈或者队列

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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. 按照矩阵最上一行、最右一列，最下一行和最左一列分别处理

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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. 设置一个辅助栈来存储最小的元素

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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]

------ 本文结束------
bluesliuf wechat
坚持技术分享，欢迎大家扫码交流！