剑指 Offer2（Python 版）解析（Ch2）

具体实现和测试代码：

系列解析（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 的个数。