剑指 Offer2(Python 版)解析(Ch4)

具体实现和测试代码

系列解析(TBD):

  • Python 单例模式
  • 好玩儿的 DP
  • 递归还是递归
  • 双指针的威力
  • 双列表的威力
  • 有趣的排列组合

特别说明:下文中的实例代码一般仅包括核心算法(不一定能直接运行),完整代码可以参考对应的链接。

第四章:解决面试题的思路

  • 画图让抽象问题形象化
  • 举例让抽象问题具体化
  • 把复杂问题分解成若干小问题,再递归解决小问题

面试题 27:二叉树的镜像

题目:请完成一个函数,输入一个二叉树,该函数输出它的镜像。

镜像就是左右子树互换的过程:

1
2
3
4
5
6
7
8
9
def mirror(tree):
if not tree:
return
tree.left, tree.right = tree.right, tree.left
if tree.left:
mirror(tree.left)
if tree.right:
mirror(tree.right)
return tree

或者用循环:

1
2
3
4
5
6
7
8
9
10
11
12
def mirror(tree):
if not tree:
return
stack = [tree]
while stack:
node = stack.pop()
node.left, node.right = node.right, node.left
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return tree

具体实现和测试代码可参考:27_MirrorOfBinaryTree

面试题 28:对称的二叉树

题目:请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

可以定义一种先右节点再左节点的遍历方法,如果遍历结果与正常的遍历结果一样,说明是对称的。

1
2
3
4
5
6
7
8
9
10
11
12
def is_symmetrical(tree):
return is_symmetrical_core(tree, tree)

def is_symmetrical_core(t1, t2):
if not t1 and not t2:
return True
if not t1 or not t2:
return False
if t1.val != t2.val:
return False
return is_symmetrical_core(t1.left, t2.right) and
is_symmetrical_core(t1.right, t2.left)

下面的 core 函数其实就是同时按不同顺序做遍历。三叉树也是类似的操作,要注意的是 mid 也要比较,因为 mid 也有子树。

二叉树的具体实现和测试代码可参考:28_01_SymmetricalBinaryTree

三叉树的具体实现和测试代码可参考:28_02_SymmetricalTernaryTree

面试题 29:顺时针打印矩阵

题目:输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

这道题看似简单,却很容易出错,尤其是一圈一圈打印矩阵时,涉及到很多边界条件的判断。比如一开始就很容易写成这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def print_matrix(mx):
rows, cols = mx.shape
start = 0
while rows > 2 * start and cols > 2 * start:
print_circle(mx, rows, cols, start)
start += 1

def print_circle(mx, rows, cols, start):
cend = cols - 1 - start
rend = rows - 1 - start
for i in range(start, cend+1):
print(mx[start][i])
for i in range(start+1, rend+1):
print(mx[i][cend])
for i in reversed(range(start, cend)):
print(mx[rend][i])
for i in reversed(range(start+1, rend)):
print(mx[i][start])

从左到右和从上到下时应该没问题,可是最后两步的从右到左和从下到上就需要判断边界了。对于前者,要保证 start < rend,否则只有一行的矩阵就会有问题,因为 rend 和 start 都是 0,会重复打印;反之,后面这种情况则在只有一列的矩阵时有问题。修改后如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def print_circle(mx, rows, cols, start):
cend = cols - 1 - start
rend = rows - 1 - start
for i in range(start, cend+1):
print(mx[start][i])
for i in range(start+1, rend+1):
print(mx[i][cend])
# 防止只有一行时打印
if rend > start:
for i in reversed(range(start, cend)):
print(mx[rend][i])
# 防止只有一列时打印
if cend > start:
for i in reversed(range(start+1, rend)):
print(mx[i][start])

具体实现和测试代码可参考:29_PrintMatrix

面试题 30:包含 min 函数的栈

题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数。在该栈中,调用 min、push 及 pop 的时间复杂度都是 O (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
class MinStack:
def __init__(self):
self.data_stack = []
self.min_stack = []

def minx(self):
if self.min_stack:
return self.min_stack[-1]
else:
return None

def push(self, x):
self.data_stack.append(x)
if not self.min_stack or x < self.min_stack[-1]:
self.min_stack.append(x)

def pop(self):
if not self.data_stack:
return None
else:
x = self.data_stack.pop()
if x == self.min_stack[-1]:
self.min_stack.pop()
return x

具体实现和测试代码可参考:30_MinInStack

面试题 31:栈的压入、弹出序列

题目:输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 1、2、3、4、5 是某栈的压栈序列,序列 4、5、3、2、1 是该压栈序列对应的一个弹出序列,但 4、3、5、1、2 就不可能是该压栈序列的弹出序列。

建立一个辅助栈,记录入栈出栈过程,遍历弹出序列,逐个验证:如果下一个弹出的数字正好是栈顶元素,直接弹出;否则把没有入栈的数字压入栈,直到下个弹出的元素是栈顶元素为止。如果所有数字都入栈了,依然没有找到下一个弹出的数字,该序列就肯定不是弹出序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def is_pop_order(push_order, pop_order):
stack = []
for i in pop_order:
if stack and stack[-1] == i:
stack.pop()
else:
while push_order and push_order[0] != i:
x = push_order.pop(0)
stack.append(x)
if push_order:
push_order.pop(0)
else:
return False
return True

只要知道了思路,代码写起来就比较容易了。其实基本思想就是根据入栈序列复现弹出序列。

具体实现和测试代码可参考:31_StackPushPopOrder

面试题 32(一):不分行从上往下打印二叉树

题目:从上往下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。

这个是常规题目,广度优先即可,需要维护一个 queue。

1
2
3
4
5
6
7
def print_tree(tree):
queue = [tree]
while queue:
node = queue.pop(0)
print(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)

具体实现和测试代码可参考:32_01_PrintTreeFromTopToBottom

面试题 32(二):分行从上到下打印二叉树

题目:从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。

这道题有很多种解法,最简单的就是在刚刚的基础上,添加层级标记。还可以直接单独打印一层,或者使用双队列。这里我们直接打印即可:

1
2
3
4
5
6
7
8
9
def print_tree(tree):
queue = [tree]
while queue:
for i in range(len(queue)):
node = queue.pop(0)
print(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
print("\n")

具体实现和测试代码可参考:32_02_PrintTreesInLines

面试题 32(三):之字形打印二叉树

题目:请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。

有了上面的代码这个就很容易了,只需要隔层 reverse 一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def print_tree(tree):
queue = [tree]
level = 0
while queue:
level += 1
tmp = []
for i in range(len(queue)):
node = queue.pop(0)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
if level % 2 == 0:
tmp.reverse() # or tmp = reversed(tmp)
if tmp:
print(" ".join(tmp))
print("\n")

具体实现和测试代码可参考:32_03_PrintTreesInZigzag

面试题 33:二叉搜索树的后序遍历序列

题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

二叉搜索树的左节点小于根节点,右节点大于根节点。后序遍历是指先遍历左右节点,然后遍历根节点。而且后序遍历的最后一个节点是根节点。相应地,前序遍历的第一个节点是根节点,中序遍历左右两边分别是左右子树。

因此,我们可以将前 n 个比根节点小的当做左子树,后面的自然就是右子树。左右子树又可以用同样的方法确定。典型的递归操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def is_postorder(lst):
root = lst[-1]
i = 0
for i in range(len(lst)):
if lst[i] > root:
break
j = i
for j in range(i, len(lst)):
if lst[j] < root:
return False
left, right = True, True
if i > 0:
left = is_postorder(lst[:i])
if j < len(lst) - 1:
right = is_postorder(lst[j:-1])
return left and right

有几个地方需要注意下:

  • 边界,包括遍历的边界和递归左右子树 list 的边界
  • i, j 的条件判断

  • left, right 的初始值

具体实现和测试代码可参考:33_SquenceOfBST

面试题 34:二叉树中和为某一值的路径

题目:输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

很直接的想法是遍历所有的路径判断路径和。遍历路径自然想到前中后序遍历,由于从根节点开始,所以我们选择前序遍历。为了减少重复遍历,自然想到类似回溯法的思想。具体思路如下:

  • 前序遍历访问节点,节点添加到路径,累加节点值
  • 如果节点没有左右子树,判断累加和是否与输入的整数相等,相等则打印
  • 如果有左右子树,则继续访问左右子节点;退出时则要删除当前节点,并减掉该节点的值,保证下个遍历不会包含叶节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def find_path(tree, k):
curr_sum = 0
path = []
find_path_core(tree, curr_sum, k, path)

def find_path_core(tree, curr_sum, need_sum, path):
curr_sum += tree.val
path.append(tree.val)
if curr_sum == need_sum and not tree.left and not tree.right:
print(path)
if tree.left:
find_path_core(tree.left, curr_sum, need_sum, path)
if tree.right:
find_path_core(tree.right, curr_sum, need_sum, path)
if path:
curr_sum -= path.pop()

最关键的不要忘记每次的 pop。具体实现和测试代码可参考:34_PathInTree

面试题 35:复杂链表的复制

题目:请实现函数 ComplexListNode Clone (ComplexListNode pHead),复制一个复杂链表。在复杂链表中,每个结点除了有一个 m_pNext 指针指向下一个结点外,还有一个 m_pSibling 指向链表中的任意结点或者 nullptr。

该链表的特殊性体现在每一个节点都有一个指向任意节点的指针。最直接的想法就是把指向任意节点的那个节点存起来,这样两趟遍历即可。书中提供了另外一种思路:

  • 每个节点后面跟一个复制的自己
  • 节点指向任意节点的指针,下一节点也指向该任意节点的下一节点
  • 将链表拆开即得到两份一样的链表
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 ComplexNode:
def __init__(self, val):
self.val = val
self.next = None
self.sibling = None

def clone_nodes(head):
node = head
while node:
new = ComplexNode(node.val)
new.next = node.next
node.next = new
node = new.next
return head

def connect_sibling_nodes(head):
node = head
while node:
clone = node.next
if node.sibling:
clone.sibling = node.sibling.next
node = clone.next
return head

def split_nodes(head):
node = head
clone_head, clone_node = None, None
if node:
clone_head = clone_node = node.next
node.next = clone_node.next
node = node.next
while node:
clone_node.next = node.next
clone_node = clone_node.next
node.next = clone_node.next
node = node.next
return clone_head

画个图会很直观(无论用手还是用脑子)。具体实现和测试代码可参考:35_CopyComplexList

面试题 36:二叉搜索树与双向链表

题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

这道题的意思就是把二叉搜索树变成一个链表,原来的 left 和 right 就相当于链表的 parent 和 next。可以将二叉树看成三部分:左右子树和根节点,如果左右子树都排好了,用根节点连接起来自然就是需要的链表了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def convert_bst_to_dll(tree):
head = convert(tree, None)
while head and head.next:
head = head.left
return head

def convert(head, last):
if not head:
return None
curr = head
if curr.left:
last = convert(curr.left, last)

curr.left = last
if last:
last.right = curr
last = curr

if curr.right:
last = convert(curr.right, last)
return last

有几个点需要特别注意:

  • 要记得从 right 的 last 回到 left,判断条件也要留心,既要 head 存在,也要 next 存在
  • 因为要的是双向链表,所以递归时务必要回指,即:last.right = curr
  • 记得右移 last

具体实现和测试代码可参考:36_ConvertBinarySearchTree☆

面试题 37:序列化二叉树

题目:请实现两个函数,分别用来序列化和反序列化二叉树。

序列化从根节点开始,所以可以使用前序遍历。

1
2
3
4
5
6
7
def serialize(tree, res):
if not tree:
res.append("$")
return
tree.append(tree.val)
serialize(tree.left, res)
serialize(tree.right, res)

接下来按照相反的方式反序列化:

1
2
3
4
5
6
7
8
def deserialize(res):
head = None
val = res.pop(0)
if val != "$":
head = BSN(val)
head.left = deserialize(res)
head.right = deserialize(res)
return head

只要记住,反序列化正好是序列化的逆过程就好。具体实现和测试代码可参考:37_SerializeBinaryTrees

面试题 38:字符串的排列

题目:输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串 abc,则打印出由字符 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba。

这道题有几种解法,相对简单些的就是递归了:假设字符串分成两组,第一组是第一个元素,剩余的一组。然后分成两步:

  • 所有可能出现在第一个位置的字符,即把第一个字符和后面的交换
  • 固定第一个字符,求后面字符的排列
1
2
3
4
5
6
7
8
9
10
11
12
# 出处:https://www.youtube.com/watch?v=KBHFyg2AcZ4
def permutate(s, l, r, res) -> list:
if l == r - 1:
if s not in res:
res.append(s)
else:
for i in range(l, r):
lst = list(s)
lst[i], lst[l] = lst[l], lst[i]
permutate("".join(lst), l+1, r, res)
lst[l], lst[i] = lst[i], lst[l]
return res

这里有一篇文章的图挺清楚的:Write a program to print all permutations of a given string,我就是看了这个图才彻底搞清楚的,果然是一图胜千言。还有一种类似的方法:

1
2
3
4
5
6
7
8
9
10
11

def permutate(s: str, moves: list, res: list):
for i in range(len(s)):
remain = s[0:i] + s[i+1:]
moves.append(s[i])
if remain:
permutate(remain, moves, res)
else:
res.append("".join(moves))
moves.pop()
return res

此外还可以先生成所有的组合,然后剔除包含重复元素的:

1
2
3
4
5
6
def product(s, repeat):
pools = [tuple(s)] * repeat
result = [""]
for pool in pools:
result = [x+y for x in result for y in pool]
return result

不过最简洁的方式当属下面这种,思想和上面的都差不多:

1
2
3
4
5
6
7
8
# 出处:https://www.youtube.com/watch?v=IPWmrjE1_MU
def permutate(prefix, suffix, res) -> list:
if not suffix:
res.append(prefix)
else:
for i in range(len(suffix)):
permutate(prefix+suffix[i], suffix[:i]+suffix[i+1:], res)
return res

最后再介绍一种相对容易理解的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 出处:https://www.youtube.com/watch?v=hqijNdQTBH8
def permutate6(s: str) -> list:
lst = list(s)
if not lst:
return []
elif len(lst) == 1:
return [lst]
else:
res = []
for i in range(len(lst)):
head = lst[i]
remain = lst[:i] + lst[i+1:]
for p in permutate6(remain):
res.append([head] + p)
return res

递归的思路比较简单,关键点就两个:

  • 第一个位置的元素
  • 第一个位置固定后递归

用循环也可以做,itertools 中实现了这个算法,不过有点复杂,这里不再赘述了。

具体实现和测试代码可参考:38_StringPermutation☆,一共提供了 7 种方法。