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

总览

具体实现和测试代码

系列解析(TBD):

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

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

第一章:面试的流程

STAR 模型介绍项目:

  • Situation:简短的项目背景。如规模、功能、目标用户等。
  • Task:自己完成的任务。注意区分负责与参与。
  • Action:为完成任务做了哪些工作,怎么做的。
  • Result:自己的贡献。量化。

掌握技能程度:

  • 了解:上过课或看过书,没做过项目。不建议列出,除非职位需要。
  • 熟悉:项目开发中用到的技能。
  • 精通:有能力解决领域内别人解决不了的问题。

应聘者需具备的素质:

  • 扎实的基础知识:编程语言、数据结构、算法。
  • 高质量的代码:正确、完整、鲁棒。
  • 清晰的思路:能清晰分析,解决复杂问题。三种方法:简单的具体例子;画图;分解成若干子问题。
  • 优化效率的能力:能从时间、空间两方面优化算法效率。
  • 优秀的综合能力:具备优秀的沟通能力、学习能力和发散思维能力。

第二章:面试需要的基础知识

C++ 相关书籍:

  • 《Effective C++》:常见问题与解决技巧。
  • 《C++ Primer》:全面了解语法。
  • 《深入探索 C++ 对象模型》:有助于深入了解 C++ 对象的内部。
  • 《The C++ Programming Language》:全面深入掌握。

C# 相关书籍:

  • 《Professional C#》:写给有其他语言经验的程序员。
  • 《CLR Via C#》:全面 + CLR + .NET

面试题 2:实现 Singleton 模式

题目:设计一个类,我们只能生成该类的一个实例。

单例设计模式的意图如下:

  • 确保类有且只有一个对象被创建。
  • 为对象提供一个访问点,以使程序可以全局访问该对象。
  • 控制共享资源的并行访问。

Python 有以下几种实现方式:

  • 所有的模块都是单例
  • 覆盖 __new__ 方法
  • 懒汉式实例化
  • 使用元类
  • Monostate 单例模式

详细可参考这篇解析:Python 单例模式。

具体实现和测试代码可参考:02_Singleton

面试题 3(一):找出数组中重复的数字

题目:在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如,如果输入长度为 7 的数组 {2, 3, 1, 0, 2, 5, 3},那么对应的输出是重复的数字 2 或者 3。

很 Naive 的方法就是创建一个 dict,然后遍历一遍统计每个数字的次数,同时判断次数是否超过 2,如果超过就返回对应的 key。字典也可以换为 list,下标作为 number,值作为次数。或者就是把数组排序后,判断前后两个数字是否相等。

这些都是常规方法,书中的算法非常精巧,它基于这样的事实:有重复的数字时必然有些位置没数字,而有些位置有多个数字。基本步骤如下:从头到尾扫描数组,扫描到下标为 i 的数字(设为 m),看看 m 和 i 是否相等;如果是则扫描下一个数字;如果不是,则再看是否和 numbers[m] 相等。如果和 numbers[m] 相等,就找到了一个重复数字;如果不是,把 numbers[i]numbers[m] 互换。

1
2
3
4
5
6
7
for k in range(len(numbers)):
while numbers[k] != k:
if numbers[k] == numbers[numbers[k]]:
return numbers[k]
tmp = numbers[k]
numbers[k] = numbers[tmp]
numbers[tmp] = tmp

具体实现和测试代码可参考:03_01_DuplicationInArray

面试题 3(二):不修改数组找出重复的数字

题目:在一个长度为 n+1 的数组里的所有数字都在 1 到 n 的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,但不能修改输入的数组。例如,如果输入长度为 8 的数组 {2, 3, 5, 4, 3, 2, 6, 7},那么对应的输出是重复的数字 2 或者 3。

Naive 的方法不提了。这里的思路是:统计一定范围内出现的次数,如果有重复,出现次数就会超过范围。比如 1-3 范围内应该有 3 个数字,但统计出来 3 个以上就一定有重复数字。然后我们就可以用二分法来解决了。

1
2
3
4
5
6
7
8
9
10
11
12
start, end = 1, len(numbers)
while end >= start:
mid = (end - start) // 2
# 统计 1-mid 之间数字的次数
count = count_range(numbers, start, mid)
if end == start and count > 1:
return start
# 次数大于范围
if count > mid - start + 1:
end = mid
else:
start = mid + 1

这个思想的关键是虽然 numbers 无序,但是用了有序的 range 去二分地统计次数。

具体实现和测试代码可参考:03_02_DuplicationInArrayNoEdit

面试题 4:二维数组中的查找

题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

关键信息是数组的有序性:从左到右递增、从上到下递增。我们可以选择右上(或左下)的数字开始,如果给定数字大于右上数字,那一定在下面的行,否则,一定在左边的列。注意:左上或右下不行。其实右上或左下正好是信息交叉点,即熵值最大的点,不确定性最大,此时比较后给我们的信息量最大;而左上或右下没有不确定性,我们确信那里是最小值或最大值。

1
2
3
4
5
6
7
while col > 0 and row < m:
if matrix[row][col] > x:
col -= 1
elif matrix[row][col] < x:
row += 1
else:
return True

具体实现和测试代码可参考:04_FindInPartiallySortedMatrix

面试题 5:替换空格

题目:请实现一个函数,把字符串中的每个空格替换成 “%20”。例如输入 “We are happy.”,则输出 “We%20are%20happy.”。

用 replace 这题就那啥了,不过也不复杂。首先确定空格的数量,然后就确定新字符串的总长度,接着从头到尾复制就好了,碰到空格,就把要替换的内容复制到新的这边。

1
2
3
4
5
6
7
8
9
10
while new_len >= raw_len >0:
if s[raw_len-1] == " ":
new_s[new_len-1] = "0"
new_s[new_len-2] = "2"
new_s[new_len-3] = "%"
new_len -= 3
else:
new_s[new_len-1] = s[raw_len-1]
new_len -= 1
raw_len -= 1

具体实现和测试代码可参考:05_ReplaceSpaces

面试题 6:从尾到头打印链表

题目:输入一个链表的头节点,从尾到头反过来打印出每个节点的值。

指针翻转会修改链表。链表遍历后翻转类似于正好就是栈的特性。

1
2
3
4
5
6
stack, res = [], []
while head:
stack.append(head.val)
head = head.next
while stack:
res.append(stack.pop())

或者使用递归:

1
2
3
4
def print_linked_list(head, res):
if head:
res.insert(0, head.val)
print_linked_list(head.next, res)

具体实现和测试代码可参考:06_PrintListInReversedOrder

面试题 7:重建二叉树

题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1,2, 4, 7, 3, 5, 6, 8} 和中序遍历序列 {4, 7, 2, 1, 5, 3, 8, 6},则重建出图 2.6 所示的二叉树并输出它的头节点。

二叉树的遍历方法:

  • 前序遍历:先根节点再左右节点
  • 中序遍历:先左节点再中右节点
  • 后序遍历:先左右节点再中节点
  • 宽度优先遍历:按层遍历
  • 深度优先遍历:按路径遍历

二叉树的特例:

  • 二叉搜索树:左节点小于或等于根节点;右节点大于或等于根节点。
  • 堆:分为最大堆和最小堆;前者根节点值最大,后者相反。
  • 红黑树:把树的节点定义为红黑两色,并通过规则确保从根节点到叶节点的最长路径不超过最短路径的两倍。

前序遍历序列的第一个数字就是根节点;根据中序遍历序列可以得到根节点的位置,根节点左边的数字是左子树(假设为 ltm 个);右边的是右子树(假设为 rtm 个)。前序遍历序列根节点后面的 ltm 个就是左子树,再往后的 rtm 个就是右子树。简易画图,很直观。

1
2
3
4
5
6
7
8
9
def construct(preorder, inorder):
if not preorder or not inorder:
return
root = preorder[0]
root_index = inorder.index(root)
tree = TreeNode(root)
tree.left = construct(preorder[1:root_index+1], inorder[:root_index])
tree.right = construct(preorder[root_index+1:], inorder[root_index+1:])
return tree

具体实现和测试代码可参考:07_ConstructBinaryTree

面试题 8:二叉树的下一个节点

题目:给定一棵二叉树和其中的一个节点,如何找出中序遍历顺序的下一个节点?树中的节点除了有两个分别指向左右子节点的指针以外,还有一个指向父节点的指针。

  • 如果一个节点有右子树,下一个节点就是右子树的左子节点。
  • 如果一个节点没有右子树,如果节点是它父节点的左子节点,下一个节点就是父节点。
  • 如果一个节点既没有右子树,并且还是父节点的右子节点,就只能沿着父节点指针一直向上遍历,直到找到一个是它父节点的左子节点的节点。

建议画图,会直观些。

1
2
3
4
5
6
7
8
9
10
11
12
if node.right:
pright = node.right
while pright.left:
pright = pright.left
pnext = pright
else:
current = node
parent = node.parent
while parent and current == parent.right:
current = parent
parent = parent.parent
pnext = parent

具体实现和测试代码可参考:08_NextNodeInBinaryTrees

面试题 9:用两个栈实现队列

题目:用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead,分别完成在队列尾部插入节点和在队列头部删除节点的功能。

队列是先进先出,而栈是先进后出。append 时可以直接进去,delete 时稍微有些麻烦,必须把栈元素全部挪一遍才能找到最先进栈的元素,然后把它删掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Queue:
def __init__(self):
self.stack1 = []
self.stack2 = []

def append_tail(self, x):
self.stack1.append(x)

def delete_head(self):
if not self.stack2:
while self.stack1:
# 后进先出
item = self.stack1.pop()
self.stack2.append(item)
# 为空时
if not self.stack2:
return
return self.stack2.pop()

相应地,用两个队列实现栈也是类似的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Stack:
def __init__(self):
self.queue1 = []
self.queue2 = []

def append(self, x):
self.queue1.append(x)

def delete(self):
if not self.queue2:
while self.queue1:
# 先进先出
item = self.queue1.pop(0)
self.queue2.append(item)
if not self.queue2:
return
return self.queue2.pop()

具体实现和测试代码可参考:09_QueueWithTwoStacks

面试题 10:斐波那契数列

题目:写一个函数,输入 n,求斐波那契(Fibonacci)数列的第 n 项。

递归代码简单,但性能可能不如循环(频繁入栈出栈),还有可能导致栈溢出。实际应用中要根据具体问题具体分析,不能简单地说某个一定好。也可以用递归的思路分析问题,写出循环的代码。

Naive 的方法不提了,递归很容易写出来,问题就是每次都要重复计算之前计算过的;自然而然,我们想要把计算过的存起来下次直接用。

1
2
3
4
5
6
7
8
def fib(n):
if n == 0 or n == 1:
return n
store = [0, 1]
for i in range(2, n+1):
res = sum(store)
store = [store[-1], res]
return res

书中另外介绍了一种方法,基于一个公式:

1
2
3
[[f(n), f(n-1)], [f(n-1), f(n-2)]] = [[1, 1], [1, 0]] ^(n-1)
a^n = a^{n/2} a^{n/2} when n is even
a^n = a^{(n-1)/2} a^{(n-1)/2} a when n is odd

简单起见,我们直接用 numpy 模块:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import numpy as np
def fib(n):
if n < 2:
return [0, 1][n]
base = np.array([[1, 1], [1, 0]])
return matrix_multiply(base, n-1)[0][0]

def matrix_multiply(base, exp):
if exp == 1:
res = base
elif exp > 1 and exp % 2 == 0:
res = matrix_multiply(base, exp/2)
res = np.dot(res, res)
elif exp > 1 and exp % 2 == 1:
res = matrix_multiply(base, (exp-1)/2)
res = np.dot(res, res).dot(base)
else:
res = base
return res

具体实现和测试代码可参考:10_Fibonacci

另外,青蛙跳台阶、铺地砖等都是类似的题目。

面试题 11:旋转数组的最小数字

题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组 {3, 4, 5, 1, 2} 为 {1, 2, 3, 4, 5} 的一个旋转,该数组的最小值为 1。

旋转数组有几个特性:

  • 两个数组都是排好序的
  • 前面的数组元素都大于或等于后面的
  • 最小的元素正好是两个数组的分界点

可以尝试用二分查找:如果中间的元素位于前面的数组,那么应该大于或等于第一个元素,最小的在后面的数组。然后把第一个元素的位置移动到中间,继续在后面一半中查找。

1
2
3
4
5
6
7
8
9
beg, end = 0, len(lst) - 1
while lst[end] < lst[beg]:
if end - beg == 1:
return lst[end]
mid = (beg + end) // 2
if lst[mid] > lst[beg]:
beg = mid
else:
end = mid

还需要考虑两种特殊情况:旋转之后首元素比末尾元素小或相等。如果旋转后最后一个元素比第一个元素还大,那就说明没旋转,最小的就是第一个元素;如果旋转后的最后一个元素和第一个元素一样大,这种情况是由于重复元素导致的,我们不清楚重复元素有多少个以及位于何处,所以只能按正常的查找方法查找。

具体实现和测试代码可参考:11_MinNumberInRotatedArray

面试题 12:矩阵中的路径

题目:请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如在下面的 3×4 的矩阵中包含一条字符串 “bfce” 的路径(路径中的字
母用下划线标出)。但矩阵中不包含字符串 “abfb” 的路径,因为字符串的第一个字符 b 占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。
A B T G
C F C S
J D E H

使用回溯法,依次判断矩阵的每个元素能否形成给定的路径。有几个关键点需要注意:

  • 顺序找到 string 的每个元素才能结束
  • 每次记录访问过的元素
  • 如果没有找到下个元素就回溯一个元素,同时修改对应的访问记录
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
import numpy as np

def has_path(array, path):
rows, cols = array.shape
visited = np.zeros((rows, cols))
plen = 0
for row in range(rows):
for col in range(cols):
if has_path_core(array, row, col, rows, cols, path, plen, visited):
return True
return False

def has_path_core(array, row, col, rows, cols, path, plen, visited):
if plen == len(path):
return True
hasp = False
if (0 =< row < rows and 0 <= col < cols
and array[row][col] == path[plen]
and not visited[row][col]):
visited[row][col] = True
plen += 1
hasp = (has_path_core(array, row, col-1, rows, cols, path, plen, visited) or
has_path_core(array, row-1, col, rows, cols, path, plen, visited) or
has_path_core(array, row, col+1, rows, cols, path, plen, visited) or
has_path_core(array, row+1, col, rows, cols, path, plen, visited))
if not hasp:
plen -= 1
visited[row][col] = False
return hasp

具体实现和测试代码可参考:12_StringPathInMatrix

面试题 13:机器人的运动范围

题目:地上有一个 m 行 n 列的方格。一个机器人从坐标 (0, 0) 的格子开始移动,它每一次可以向左、右、上、下移动一格,但不能进入行坐标和列坐标的数位之和大于 k 的格子。例如,当 k 为 18 时,机器人能够进入方格 (35, 37),因为 3+5+3+7=18。但它不能进入方格 (35, 38),因为 3+5+3+8=19。请问该机器人能够到达多少个格子?

和上一题类似,不过返回值是格子数。另外,并不需要回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
def moving_count_core(row, col, rows, cols, threshold, visited):
count = 0
if (0 <= row < rows and 0 <= col < cols
and get_digit_num(row) + get_digit(col) <= threshold
and not visited[row][col]):
visited[row][col] = True
count = 1 + (
moving_count_core(row-1, col, rows, cols, threshold, visited) +
moving_count_core(row+1, col, rows, cols, threshold, visited) +
moving_count_core(row, col-1, rows, cols, threshold, visited) +
moving_count_core(row, col+1, rows, cols, threshold, visited)
)
return count

具体实现和测试代码可参考:13_RobotMove

感慨下,有时候明明知道怎么做就是写不出代码来;一个朋友说那还是不知道,我觉得也是。这可能就是知道的层次不同吧,总归须知此事要躬行。

面试题 14:剪绳子

题目:给你一根长度为 n 绳子,请把绳子剪成 m 段(m、n 都是整数,n>1 并且 m≥1)。每段的绳子的长度记为 k [0]、k [1]、……、k [m]。k [0]*k [1]*…*k [m] 可能的最大乘积是多少?例如当绳子的长度是 8 时,我们把它剪成长度分别为 2、3、3 的三段,此时得到最大的乘积 18。

动态规划适合于能分解成子问题,并且子问题也有最优解的问题。动态规划求解的问题特点如下:

  • 求一个问题的最优解
  • 整体问题最优解依赖子问题最优解
  • 小问题之间还有相互重叠的更小的子问题

贪婪算法每一步都做出一个贪婪的选择,但需保证这样的做法能够得到最优解。此例中,n ≥ 5 时,尽可能剪成 3 的段,当剩下的绳子为 4 时,剪成 2 2,这样乘积就能最大。

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
# 动态规划
def dp(n):
if n <= 3:
return [0, 0, 1, 2][n]
products = [0, 1, 2, 3] + [0] * (n-3)
for i in range(4, n+1):
mx = 0
for j in range(1, i//2+1):
pt = products[j] * products[i-j]
if pt > mx:
mx = pt
products[i] = mx
return products[-1]

# 贪婪
def greedy(n):
if n <= 3:
return [0, 0, 1, 2][n]
n3 = n // 3
remain = n - n3 * 3
if remain == 1:
return 3 ** (n3-1) * 4
elif remain == 2:
return 3 ** n3 * 2
else:
return 3 ** n3

具体实现和测试代码可参考:14_CuttingRope

面试题 15:二进制中 1 的个数

题目:请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如把 9 表示成二进制是 1001,有 2 位是 1。因此如果输入 9,该函数输出 2。

一个数字与 1 做与运算,可以判断最低位是不是 1,因此我们可以不断右移数字或左移 flag 来实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 右移数字
while n:
if n & 1:
count += 1
n = n >> 1

# 左移 flag
flag = 1
while flag:
if n & flag:
count += 1
flag = flag << 1
if flag > n:
break

书中还介绍了一个更精巧的算法:一个整数减去 1,与原整数做与运算,会把该整数最右边的 1 变为 0。

1
2
3
while n:
n = n & (n-1)
count += 1

最后,注意负数和溢出的情况,Python 中的情况(自动对大数做了处理)和 C 或 CPP 不一样。

具体实现和测试代码可参考:15_NumberOf1InBinary

还有两个相关题目:

  • 判断一个数是不是 2 的整数次方。如果是,二进制中只有一个 1,减去 1 再和自己与运算,就会把唯一的 1 变为 0,所以整个结果为 0。比如 8 & (8-1) == 0
  • 输入整数 m n,需要改变 m 的二进制多少位能得到 n。第一步求异或;第二步求异或中 1 的个数。

第三章:高质量的代码

  • 规范性
    • 书写清晰
    • 布局清晰
    • 命名合理
  • 完整性
    • 完成基本功能
    • 考虑边界条件
    • 做好错误处理(错误输入)
      • 用返回值告知出错
      • 设置一个全局变量
      • 抛一个异常
  • 鲁棒性
    • 采取防御性编程
    • 处理无效的输入

面试题 16:数值的整数次方

题目:实现函数 double Power (double base, int exponent),求 base 的 exponent 次方。不得使用库函数,同时不需要考虑大数问题。

不考虑大数问题,但负数问题还是要考虑的。Naive 的方法就是循环相乘 exponent 次。但显然有了之前斐波那契数列的经验,我们自然想用更快速的方法:exponent 是偶数的时候,先算 exponent/2 次方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def base_by_exp(base, exp):
# 不要直接用 == 0
if exp < 0 and is_equal_zero(base):
print("Invalid input.")
return 0

if exp < 0:
return 1/calc(base, -exp)
else:
return calc(base, exp)

def calc(base, exp):
if exp == 0:
return 1
if exp == 1:
return base
res = calc(base, exp//2)
res *= res
if exp % 2 == 1:
res = res * base
return res

具体实现和测试代码可参考:16_Power

面试题 17:打印 1 到最大的 n 位数

题目:输入数字 n,按顺序打印出从 1 最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数即 999。

Naive 的做法当然是求出这个最大的数:10 ** (n-1) - 1,然后挨个打印出来就行了。但这没有考虑大数问题,虽然 Python 对大数做了处理,但其他语言可能并没有,所以一般使用字符串来模拟。显然需要模拟字符串上的加法,我们把每位用一个字符表示,创建一个表示各位的 list。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def print_1ton(n):
str_num = [0] * (n+1)
# 如果最高位没有进一
while not str_num[0]:
print(str_num)
str_num = increase(str_num)

def increase(str_num):
over = 0
nlen = len(str_num)
for i in range(nlen-1, -1, -1):
addn = str_num[i] + over
if i == nlen - 1:
addn += 1
if addn >= 10:
addn -= 10
str_num[i] = addn
over = 1
else:
str_num[i] = addn
break
return str_num

书中还介绍了使用全排列的方法,貌似更简单:全排列的基本思想是,每一位都是 0-9 的一个数,然后继续设置下一位,直到最后一位。

1
2
3
4
5
6
7
8
9
10
11
def print_1ton(n):
nums = [0] * (n+1)
return increase(nums, 0)

def increase(nums, index):
if index == len(nums) - 1:
print(nums)
return
for i in range(10):
nums[index+1] = i
increase(nums, index+1)

稍稍解释下,这里 index 从 0 开始,所以一开始不会打印,直到 index 等于 n 时,这时候就是个位数开始(前面的每位都是 0)依次打印到高位的过程。

具体实现和测试代码可参考:17_Print1ToMaxOfNDigits

面试题 18(一):在 O (1) 时间删除链表节点

题目:给定单向链表的头指针和一个节点指针,定义一个函数在 O (1) 时间删除该节点。

正常的做法是从头开始遍历,找到那个节点然后删除。但这样的复杂度是 O(N),书中使用了一种巧妙的方法:将该节点的下一个节点复制过来,然后将该节点指向下一个节点的下一节点。这就相当于把该节点删除了。不过有个前提是节点在链表中。另外,如果要删除的节点是尾节点,那就只能顺序遍历到结尾删除了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def delete_node(head, tobe_delete):
# 有下一个节点时
if tobe_delete.next:
nxt = tobe_delete.next
tobe_delete.val = nxt.val
tobe_delete.next = nxt.next
# 只有一个节点
elif not tobe_delete.next and head == tobe_delete:
head = None
else:
node = head
while node.next != tobe_delete:
node = node.next
node.next = None
return head

具体实现和测试代码可参考:18_01_DeleteNodeInList

面试题 18(二):删除链表中重复的节点

>

题目:在一个排序的链表中,如何删除重复的节点?例如,在图 3.4(a)中重复节点被删除之后,链表如图 3.4(b)所示。

需要注意两件事情:头节点也可能被删除;删除之后链表依然是连着的。另外,链表是排序的。

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
def delete_duplication(head):
prev = None
node = head
while node:
nxt = node.next
need_delete = False
# 删除条件:如果下一个和当前一样就需要删除
if nxt and nxt.val == node.val:
need_delete = True

# 如果不需要删除
if not need_delete:
prev = node
node = node.next
# 如果需要删除
else:
val = node.val
tobe_del = node
while tobe_del and tobe_del.val == val:
tobe_del = tobe_del.next
# 保证无论怎么删除链表依然是连着的
if not prev:
head = tobe_del
else:
prev.next = tobe_del
# 从最新位置开始继续循环
node = tobe_del
return head

具体实现和测试代码可参考:18_02_DeleteDuplicatedNode

面试题 19:正则表达式匹配

题目:请实现一个函数用来匹配包含 '.''*' 的正则表达式。模式中的字符 '.' 表示任意一个字符,而 '*' 表示它前面的字符可以出现任意次(含 0 次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串 "aaa" 与模式 "a.a""ab*ac*a" 匹配,但与 "aa.a""ab*a" 均不匹配。

输入是 string 和 pattern,典型的 DP 解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def dp(s, p):
T = [[0] * (len(p)+1) for i in range(len(s)+1)]
T[0][0] = 1
for j in range(len(p)):
if p[j] == "*":
T[0][j+1] = T[0][j-1]
for i in range(len(s)):
for j in range(len(p)):
if s[i] == p[j] or p[j] == ".":
T[i+1][j+1] = T[i][j]
elif p[j] == "*":
T[i+1][j+1] = T[i+1][j-1]
if not T[i+1][j+1]:
if p[j-1] == "." or p[j-1] == s[i]:
T[i+1][j+1] = T[i][j+1]
return T[-1][-1]

画个表格这个代码就很容易写出来了。还可以使用递归:

1
2
3
4
5
6
7
8
9
10
11
12
def dp(s, p):
first_match = s[0] == p[0] or p[0] == "."
if p[1] == "*":
if first_match:
# 0 time, 1 time, 2 times
return dp(s, p[2:]) or dp(s[1:], p[2:]) or dp(s[1:], p)
else:
# 0 time
return dp(s, p[2:])
if first_match:
return dp(s[1:], p[1:])
return False

递归代码看起来就是简单清晰。

具体实现和测试代码可参考:19_RegularExpressionsMatching

面试题 20:表示数值的字符串

题目:请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串 “+100”、“5e2”、“-123”、“3.1416” 及 “-1E-16” 都表示数值,但 “12e”、“1a3.14”、“1.2.3”、“+-5” 及 “12e+5.4” 都不是。

书中给出数字的表示方法:A[.[B]][e|EC].B[e|EC],A 是整数部分,B 是小数部分,C 是指数部分。A 和 C 可以带正负号,B 不可以。所以,可以首先定义扫描数字部分:

1
2
3
4
5
6
7
8
9
10
11
12
def scan_integer(s):
if s and (s[0] == "+" or s[0] == "-"):
s = s[1:]
return scan_unsigned_integer(s)

def scan_unsigned_integer(s):
checked = []
nums = "0 1 2 3 4 5 6 7 8 9".split()
i = 0
while s and s[i] in nums:
i += 1
return s[i:]

这里不考虑类似 +++2 这种情况,Python 中没问题,不过 Java 或 C++ 中这并不是有效的数字。但是 00000001.1 是有效的,具体情况根据需要设计。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def is_num(s):
remain = scan_integer(s)
# 正常整数
if not remain:
return True
elif remain[0] == ".":
remain = scan_unsigned_integer(remain[1:])
# 正常的小数
if not remain:
return True
elif remain[0] in ["e", "E"]:
remain = scan_integer(remain[1:])
# 带 e 的数字
if not remain:
return True
return False

具体实现和测试代码可参考:20_NumericStrings

面试题 21:调整数组顺序使奇数位于偶数前面

题目:输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

Python 可以直接用排序搞定:

1
sorted(nums, key=lambda x: x%2, reverse=True)

否则,就需要维护两个指针,一个在开头,一个在结尾,因为不需要排序,所以只需要交换位置即可,类似归并排序的第一步。

1
2
3
4
5
6
7
8
9
10
11
func = lambda x: x%2
def reorder(nums, func):
left, right = 0, len(nums) - 1
while left < right:
while left < right and func(nums[left]):
left += 1
while left < right and not func(nums[right]):
right -= 1
if left < right:
nums[left], nums[right] = nums[right], nums[left]
return nums

具体实现和测试代码可参考:21_ReorderArray

面试题 22:链表中倒数第 k 个节点

题目:输入一个链表,输出该链表中倒数第 k 个节点。为了符合大多数人的习惯,本题从 1 开始计数,即链表的尾节点是倒数第 1 个节点。例如一个链表有 6 个节点,从头节点开始它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

如果知道长度,用长度减去 k 从头开始遍历就能找到节点,但知道长度需要首先遍历一遍链表。如果要只遍历一次,我们可以使用双指针。很多类似的场景都可以用这个方法。不过这里特别注意边界和 k 的取值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def find_kth_from_end(head, k):
if k < 0 or not head:
return None
front = head
behind = head
for i in range(k-1):
if front.next:
front = front.next
# 防止 k 超过链表长度
else:
return None
while front.next:
front = front.next
behind = behind.next
return behind

具体实现和测试代码可参考:22_KthNodeFromEnd

面试题 23:链表中环的入口节点

题目:一个链表中包含环,如何找出环的入口节点?例如,在图 3.8 的链表中,环的入口节点是节点 3。

与上一题一样,可以用两个指针来解决。首先确定链表中是否包括环,如果是,那么长度是多少;如果不是返回 0。然后根据环的长度 n,第一个指针先走 n 步,第二个指针和第一个指针相遇的地方就是入口。

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
def is_there_a_loop(head):
front, behind = head, head
lenth = 0
while front.next and behind.next.next:
front = front.next
behind = behind.next.next
# 有环
if front.val == behind.val:
tag = front.val
while front.next:
front = front.next
lenth += 1
# Return 条件
if front.val == tag:
return length

def entry_of_loop(head):
loop_len = is_there_a_loop(head)
if not loop_len:
return None
first, second = head, head
for i in range(loop_len):
first = first.next
while first:
if first.val == second.val:
return first
first = first.next
second = second.next

或者可以先找到两个指针相遇的节点,然后根据这个节点可以确定 loop 长度(再次相遇时);剩下的就和上面方法一样了。

具体实现和测试代码可参考:23_EntryNodeInListLoop

面试题 24:反转链表

题目:定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

这道题属于常规操作,没有太多要说的。

1
2
3
4
5
6
7
8
9
10
11
12
def reverse(head):
preverse = None
node = head
prev = None
while node:
nxt = node.next
if not nxt:
preverse = node
node.next = prev
prev = node
node = nxt
return preverse

需要注意防止链表最后一个节点断掉的问题,不过我感觉可以直接把 prev 返回去:

1
2
3
4
5
6
7
8
9
def reverse(head):
node = head
prev = None
while node:
nxt = node.next
node.next = prev
prev = node
node = nxt
return prev

不知道这样是不是我忽略了哪个地方,如果有知道的童鞋请帮忙指正。此外,还可以使用递归:

1
2
3
4
5
6
7
def reverse(head):
if not head or not head.next:
return head
p = reverse(head.next)
head.next.next = head
head.next = None
return p

具体实现和测试代码可参考:24_ReverseList

面试题 25:合并两个排序的链表

题目:输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是按照递增排序的。例如输入图 3.11 中的链表 1 和链表 2,则合并之后的升序链表如链表 3 所示。

这道题和归并排序的归并步骤类似,因为两个链表本来就是排好序的,所以挨个比较元素,自然就按顺序排好了。递归和循环都可以。

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
def merge(head1, head2):
link = Node(None)
ptr = link
while head1 and head2:
if head1.val <= head2.val:
ptr.next = head1
ptr = ptr.next
head1 = head1.next
else:
ptr.next = head2
ptr = ptr.next
head2 = head2.next
if head1:
ptr.next = head1
if head2:
ptr.next = head2
return link.next

def merge_recurision(head1, head2):
if not head1:
return head2
if not head2:
return head1
if head1.val < head2.val:
link = head1
link.next = merge_recurision(head1.next, head2)
else:
link = head2
link.next = merge_recurision(head1, head2.next)
return link

具体实现和测试代码可参考:25_MergeSortedLists

面试题 26:树的子结构

题目:输入两棵二叉树 A 和 B,判断 B 是不是 A 的子结构。

首先在 A 中找到 B 的根节点,然后判断 A 中以该节点为根节点的子树是否包含 B。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def has_subtree(tree, sub):
res = False
if tree and sub:
# step1
if equal(tree.val, sub.val):
# step2
res = tree_has_sub(tree, sub)
if not res:
res = has_subtree(tree.left, sub)
if not res:
res = has_subtree(tree.right, sub)
return res

def tree_has_sub(tree, sub):
if not sub:
return True
if not tree:
return False
if not equal(tree.val, sub.val):
return False
return tree_has_sub(tree.left, sub.left) and tree_has_sub(tree.right, sub.right)

Step2 时,因为根节点已经一致了,所以我们继续判断左右节点是否一致(同时满足一致)。

具体实现和测试代码可参考:26_SubstructureInTree

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

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

面试题 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 种方法。