题目链接：
剑指offer 20-29
目录：
20. 表示数值的字符串
21. 调整数组顺序使奇数位于偶数前面
22. 链表中倒数第 K 个结点
23. 链表中环的入口结点
24. 反转链表
25. 合并两个排序的链表
26. 树的子结构
27. 二叉树的镜像
28 对称的二叉树
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 终于过了一遍，大多数题目还是很简单的，但是题目具有代表性，涉及链表、数组、深搜回溯、字符串、数组、数学、位运算、动态规划等。这里做一个总结：
剑指offer【03~09】
剑指offer【10~19】
剑指offer【20~29】
剑指offer【30~39】
剑指offer【40~49】
剑指offer【50~59】
剑指offer【60~68】
