剑指offer【20~29】

echobingo

发布于 2019-12-20 11:57:48

3090

发布于 2019-12-20 11:57:48

文章被收录于专栏：Bingo的深度学习杂货店 Bingo的深度学习杂货店Bingo的深度学习杂货店

题目链接：

剑指offer 20-29

Python 实现：

20. 表示数值的字符串

方法1：使用正则表达式，格式为 import re，re.match(r"^...$", s) ，其中 ^ 表示匹配 s 的开始，$ 表示匹配 s 的结尾，... 就是自己写的表达式。匹配成功会返回一个对象，则为 True，否则为 False。

Python 常见的正则表达式符号： \d：数字；?：0次或1次；*：0次到n次；+：1次到n次；\.：匹配 "."；[]：字符集合；()：分组；.：任意字符。

注意： （1）"-.123" 也是合法的，对应代码中的 \d*； （2）如果不加结尾符 $，则对于 "12e" 这种也会匹配成功（比如 12e+5，它会匹配中间的 12e，从而造成错误），因此需要在末尾加上 $。

# -*- coding:utf-8 -*-
import re  # 导入正则表达式
class Solution:
    # s字符串
    def isNumeric(self, s):
        # write code here
        if re.match(r"^[+-]?\d*(\.\d+)?([eE][+-]?\d+)?$", s):  # 匹配成功会返回一个对象
            return True
        else:
            return False

方法2：尝试将 s 转化为 float(s)，转换成功返回 True，否则返回 False。因此需要用到 Python 的 try、except 语句。

# -*- coding:utf-8 -*-
class Solution:
    # s字符串
    def isNumeric(self, s):
        # write code here
        try:  # 转化成功返回 True
            float(s)
            return True
        except:  # 转化失败返回 False
            return False

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

因为要保证相对位置，所以只能用空间和时间复杂度均为 O(n) 的算法。（如果不需要保证相对位置，可以用双指针，类似于快排 partition 部分的操作，空间 O(1)，时间 O(n)）

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        le, ri = [], []
        for num in array:
            if num & 1:
                le.append(num)
            else:
                ri.append(num)
        return le + ri

22. 链表中倒数第 K 个结点

# -*- 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
        slow = fast = head
        while fast and k:
            fast = fast.next
            k -= 1
        if k > 0:  # k 大于链表长度
            return None
        while fast:
            slow = slow.next
            fast = fast.next
        return slow

23. 链表中环的入口结点

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        is_cycle = False
        slow = fast = pHead
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:  # 快慢指针相遇
                is_cycle = True
                break
        if not is_cycle:  # 没有环
            return None
        begin = pHead
        while begin != slow:  # 一步一步走，相遇即为环入口
            begin = begin.next
            slow = slow.next
        return begin

24. 反转链表

可以使用迭代和递归，迭代就是指针的移动和交换，容易实现。这里实现的递归的方法。

# -*- 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
        second = pHead.next
        newHead = self.ReverseList(second)
        second.next = pHead
        pHead.next = None  # 断开
        return newHead

25. 合并两个排序的链表

# -*- 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
        pre1, cur1, cur2 = None, pHead1, pHead2
        while cur1 and cur2:  # 合并后的链表为链表1
            if cur1.val <= cur2.val:
                pre1 = cur1
                cur1 = cur1.next
            elif not pre1:
                pre1 = cur2
                cur2 = cur2.next
                pre1.next = cur1
            else:
                pre1.next = cur2
                pre1 = pre1.next
                cur2 = cur2.next
                pre1.next = cur1
        if not cur1 and pre1:  # 链表1为空，直接接链表2
            pre1.next = cur2
        return pHead1

26. 树的子结构

类似于字符串查找，因为是树结构的原因，在每次匹配失效后，子树 B 要从头开始匹配。因此，这道题分为两个步骤： （1）判断以树 A 当前节点构成的树能否与子树 B 相匹配； （2）判断以树 A 当前节点的左孩子或者右孩子构成的树能否与子树 B 相匹配。
对于判断是否匹配，需要再写一个函数，这个函数也是递归实现的。
这道题容易将两个函数混淆在一起，注意每次匹配失效后，子树 B 要从头开始匹配的这个关键点。

# -*- 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
        if not pRoot1 or not pRoot2:
            return False
        return self.isHasSubtreeSame(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)
    
    def isHasSubtreeSame(self, r1, r2):
        if not r2:
            return True
        if not r1 or r1.val != r2.val:
            return False
        return self.isHasSubtreeSame(r1.left, r2.left) and self.isHasSubtreeSame(r1.right, r2.right)

27. 二叉树的镜像

将当前结点的左右子树的地址对调即可。

# -*- 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
        tmp = root.left  # 防止交换后原先的 root.left 被修改
        root.left = self.Mirror(root.right)
        root.right = self.Mirror(tmp)
        return root

28 对称的二叉树

要转化为判断根节点的左子树和右子树是否对称，因此需要另写一个函数递归判断。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def isSymmetrical(self, pRoot):
        # write code here
        if not pRoot:
            return True
        return self.isSubtreeSym(pRoot.left, pRoot.right)
    
    def isSubtreeSym(self, le, ri):
        if not le and not ri:  # 均为空
            return True
        if not le or not ri:  # 有一个为空
            return False
        if le.val != ri.val:  # 均不为空
            return False
        return self.isSubtreeSym(le.left, ri.right) and self.isSubtreeSym(le.right, ri.left)

29. 顺时针打印矩阵

按层的概念，从外到内一层一层填充。每次填充前，先记录每一层的左上角和右下角的位置。同时，还要对奇数行或奇数列的情况加 if 判断，防止出现重复填充的问题。

# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here
        row, col = len(matrix) - 1, len(matrix[0]) - 1  # 右下角 (row, col)
        ri = ci = 0  # 左上角 (ri, ci)
        res = []
        while ri <= row and ci <= col:
            for i in range(ri, col + 1):
                res.append(matrix[ri][i])
            for i in range(ri + 1, row + 1):
                res.append(matrix[i][col])
            if ri != row:  # 奇数行，只填充一次
                for i in range(col - 1, ci - 1, -1):
                    res.append(matrix[row][i])
            if ci != col:  # 奇数列，只填充一次
                for i in range(row - 1, ri, -1):
                    res.append(matrix[i][ci])
            # 每填充一层之后，下一次填充的左上角位置为 (ri,ci)，右下角位置为 (row,col)
            ri += 1; ci += 1; row -= 1; col -= 1
        return res

剑指 offer 终于过了一遍，大多数题目还是很简单的，但是题目具有代表性，涉及链表、数组、深搜回溯、字符串、数组、数学、位运算、动态规划等。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

python