# 剑指offer【20~29】

#### Python 实现：

##### 20. 表示数值的字符串

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

```# -*- 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```

```# -*- coding:utf-8 -*-
class Solution:
# s字符串
def isNumeric(self, s):
# write code here
try:  # 转化成功返回 True
float(s)
return True
except:  # 转化失败返回 False
return False```
##### 21. 调整数组顺序使奇数位于偶数前面

```# -*- 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:
# 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
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
# write code here
pHead.next = None  # 断开
##### 25. 合并两个排序的链表
```# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
# 返回合并后列表
# 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
##### 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. 顺时针打印矩阵

```# -*- 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```

0 条评论

• ### 剑指offer【50~59】

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

• ### 剑指offer【30~39】

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

• ### 剑指offer【03~09】

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

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

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

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

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

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

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

• ### 基于Django的电子商务网站开发（连载16）

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