剑指offer【20~29】

题目链接:

剑指offer 20-29


Python 实现:

20. 表示数值的字符串

方法1:使用正则表达式,格式为 import rere.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 的 tryexcept 语句。

# -*- 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 终于过了一遍,大多数题目还是很简单的,但是题目具有代表性,涉及链表、数组、深搜回溯、字符串、数组、数学、位运算、动态规划等。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指offer【50~59】

    排序数组,很明显二分查找,找到第一个 >= k 的元素索引以及第一个 > k 的元素索引,两者相减即为答案,即 lowerBound - upperBound。...

    echobingo
  • 剑指offer【30~39】

    除了存储数据的栈 stack,再定义一个最小栈 minstack。minstack 的长度和 stack 保持同步,只不过其是一个递减栈。如 stack = [...

    echobingo
  • 剑指offer【03~09】

    注意:这道题如果数据范围变为 [1, n],那么可以将其转化为使用快慢指针判断有环问题,和 Leetcode 【Two Pointers】287. Find t...

    echobingo
  • Scrapy用pipelines把字典保

    py3study
  • python GUI库图形界面开发之PyQt5打开保存对话框QFileDialog详细使用方法与实例

    QFIleDialog是用于打开和保存文件的标准对话框。QFileDialog类继承自QDialog类

    砸漏
  • python程序界面

    py3study
  • 如何实现四元数的运算

    在前面的一篇文章《Python中的5对必知的魔法方法》中所介绍的“魔法方法”,或者说是特殊方法,其命名均是双下划线开始和结束。英文中称为“dunder meth...

    老齐
  • 使用PyQt5实现图片查看器的示例代码

    在学习 PyQt5 的过程中我会不断地做一些小的 Demo,用于让自己能够更好地理解和学习,这次要做的就是一个图片查看器,主要功能包括打开图片、拖动图片、放大和...

    砸漏
  • 使用ReactiveCocoa开发RSS阅读器

    目前已经完成的功能有对RSS的解析和Atom解析,RSS内容本地数据库存储和读取,抓取中状态进度展示,标记阅读状态,标记全部已读等。这些功能里我对一些异步操作产...

    用户7451029
  • 基于Django的电子商务网站开发(连载16)

    (1)通过循环语句formylist in self.mylists:遍历所有测试用例。

    小老鼠

扫码关注云+社区

领取腾讯云代金券