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

具体实现和测试代码：

系列解析（TBD）：

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

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

第六章：面试中的各项能力

每做一道题，要总结这道题的解法有什么特点，哪些思路可以用到同类型的题目中去。

面试题 53（一）：数字在排序数组中出现的次数

题目：统计一个数字在排序数组中出现的次数。例如输入排序数组 {1, 2, 3, 3, 3, 3, 4, 5} 和数字 3，由于 3 在这个数组中出现了 4 次，因此输出 4。

O(N) 的遍历无疑是最简单的，所以肯定要考虑更快的算法（一般都是 log(N) 级别的），首先想到的就是二分查找，然后要做的是如何使用二分查找确定给定数字的出现次数。如果能找到第一个和最后一个的位置，那么只要位置相减加 1 就是次数。特别需要注意的是查找到时，需要判断是否为首元素，或上个元素也是要查找的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def get_first_index(lst: list, k: int) -> int:
    start, end = 0, len(lst) - 1
    while start <= end:
        mid = (start + end) // 2
        if lst[mid] > k:
            end = mid - 1
        elif lst[mid] < k:
            start = mid + 1
        else:
            if mid == 0 or lst[mid-1] != k:
                return mid
            else:
                end = mid - 1
    return -1

剩下的就比较简单了，不再赘述。具体实现和测试代码可参考：53_01_NumberOfK

面试题 53（二）：0 到 n-1 中缺失的数字

题目：一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0 到 n-1 之内。在范围 0 到 n-1 的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。

这个题和上面的方法类似，也可以做到 O(log(N)) 的效率，不同的是，需要对比的是值和 index。

1
2
3
4
5
6
7
8
9
10
11
def get_missing(lst: list):
    start, end = 0, len(lst) - 1
    while start <= end:
        mid = (start + end) // 2
        if lst[mid] > mid:
            end = mid - 1
            if mid == 0 or lst[mid-1] == mid - 1:
                return mid
        else:
            start = mid + 1
    return -1

具体实现和测试代码可参考：53_02_MissingNumber

面试题 53（三）：数组中数值和下标相等的元素

题目：假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数找出数组中任意一个数值等于其下标的元素。例如，在数组 {-3, -1, 1, 3, 5} 中，数字 3 和它的下标相等。

这个题也是和之前的类似，需要对比值和 index。

1
2
3
4
5
6
7
8
9
10
11
def get_num_is_index(lst: list) -> int:
    start, end = 0, len(lst) - 1
    while start <= end:
        mid = (start + end) // 2
        if lst[mid] == mid:
            return mid
        elif lst[mid] > mid:
            end = mid - 1
        else:
            start = mid + 1
    return -1

具体实现和测试代码可参考：53_03_IntegerIdenticalToIndex

面试题 53（四）：数组中数值只出现一次的数

题目：假设一个单调递增的数组里的除一个元素只出现一次外，其他每个元素都出现了两次。例如，在数组 {1, 1, 2, 3, 3} 中，数字 2 只出现了一次。假设数组至少有两个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def find_once_num(lst: list) -> int:
    start, end = 0, len(lst) - 1
    while start <= end:
        mid = (start + end) // 2
        if lst[mid] == lst[mid-1]:
            if mid % 2 == 0:
                end = mid - 1
            else:
                start = mid + 1
        elif lst[mid] == lst[mid+1]:
            if mid % 2 == 0:
                start = mid + 1
            else:
                end = mid - 1
        else:
            return lst[mid]

这里需要注意的是，当 mid 位置的值和它的上一个或下一个值相等时，我们需要根据 mid 的奇偶性来判断出现一次的元素在左边还是右边。因为不考虑 mid 和与它相等的那个位置，左边的元素个数如果是偶数个，那肯定不在左边；相反一样成立。所以，在 mid 和 mid-1 位置的元素相等时，如果 mid 能整除 2，那说明左边正好是奇数个元素，那个出现一次的元素一定在左边。

这个题目挺有意思的，其中的关键是利用位置的奇偶性来判断元素个数的奇偶性，也是二分法的灵活应用。题外插一句，0 为 index 有时候真的有点奇怪。

具体实现和测试代码可参考：53_04_MissingNumberOnce

面试题 54：二叉搜索树的第 k 大节点

题目：给定一棵二叉搜索树，请找出其中的第 k 大的节点。

这题考的是二叉树的性质：左节点 < 父结点 < 右节点，所以中序遍历的话，结果正好是从小到大排列的。补充一下三个遍历方式（其实就是以根节点为基准的）：

  • 前序遍历：先根节点再左右节点
  • 中序遍历：先左节点再中右节点
  • 后序遍历：先左右节点再中节点

这里要注意的是，按书上的意思，第 k 大节点就是第 k 个节点，我自己理解是反的，也就是第 k 个节点第 k 小节点。不过这个并不重要。

我们可以先遍历完，然后用 index 取值，也可以边遍历边计数，求第 k 大节点的话，甚至可以调整一下遍历顺序，即右节点、中间节点、左节点这样的顺序。

特别需要注意，遍历时求值时，如果使用递归方法，不要在递归函数内使用局部变量来计数或作为返回值，要使用不在函数栈上的变量，否则会出现莫名其妙的报错。

具体实现和测试代码可参考：54_KthNodeInBST

面试题 55（一）：二叉树的深度

题目：输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶结节点成树的一条路径，最长路径的长度为树的深度。

这个典型的递归思路，分别递归左右子树，每一轮结果加 1：

1
2
3
4
def tree_depth(tree):
    left = tree_depth(tree.left)
    right = tree_depth(tree.right)
    return left + 1 if left > right else right + 1

具体实现和测试代码可参考：55_01_TreeDepth

面试题 55（二）：平衡二叉树

题目：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

这个可以利用上一道题的思路，分别计算左右子树的深度，然后判断深度差是否超过 1：

1
2
3
4
5
6
7
def tree_is_balanced(tree):
    left = tree_depth(tree.left)
    right = tree_depth(tree.right)
    if abs(left - right) > 1:
        return False
    else:
        return tree_is_balanced(tree.left) and tree_is_balanced(tree.right)

需要注意最后 else 这里，要继续判断。否则类似 “人” 字形的树会判断失败。这种解法重复计算了多次节点，如果要只计算一次需要稍微调整一下，也就是在计算树深度时，如果有高度差绝对值比 1 大的情况，直接返回：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def tree_depth(tree):
    if not tree:
        return 0
    left = tree_depth(tree.left)
    if left == -1:
        return -1
    right = tree_depth(tree.right)
    if right == -1:
        return -1
    if abs(left - right) > 1:
        return -1
    return left + 1 if left > right else right + 1

def tree_is_balanced(tree):
    return tree_depth(tree) != -1

具体实现和测试代码可参考：55_02_BalancedBinaryTree

面试题 56（一）：数组中只出现一次的两个数字

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O (n)，空间复杂度是 O (1)。

注意这个题目对时间和空间复杂度都有要求。这道题没看解答之前我是没想出来，最后看了才知道利用了异或的思路，也算是骨骼清奇了。基本思路是利用任何一个数字异或自己都为 0，所以除开那两个出现 1 次的数字，整个数组其他数字异或结果应该为 0，如果能够把这两个数字分到 2 个不同的数组，结果就很容易得到了。具体算法步骤如下：

  • 依次异或数组中的元素得到结果 a，也就是 2 个只出现 1 次的数字异或的结果，它一定不为 0。
  • 找到 a 第 1 个 1 的位置，以此位置是否为 1 为标准可以将数组拆分为 2 个数组，此时那 2 个数字一定在不同的数组。
  • 分别异或 2 个数组，得到的结果就是那 2 个数字。

感慨一下，真的很巧妙的思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def appear_once_number(lst: list) -> list:
    xor, xor1, xor2 = 0, 0, 0
    for i in lst:
        xor ^= i
    last_one_index = get_last_one_index(xor)
    for i in lst:
        if (i >> last_one_index) & 1:
            xor1 ^= i
        else:
            xor2 ^= i
    return [xor1, xor2]

def get_last_one_index(n: int):
    count = 0
    while n & 1 == 0:
        n = n >> 1
        count += 1
    return count

Python 的话，这里不需要处理大数问题，否则 get_last_one_index 函数需要注意 count 的取值，不要超过最大的整数范围。

具体实现和测试代码可参考：56_01_NumbersAppearOnce

面试题 56（二）：数组中唯一只出现一次的数字

题目：在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

这也是一道骨骼清奇的题目，同样利用了二进制，因为出现了 3 次，所以求和后每一位都是 3 的倍数，这样我们把所有数字二进制求和后看每位能不能被 3 整除，不能为 1，能为 0，最后得到的结果就是要找的数字。Python 中可以利用 bin 函数直接得到二进制表示，然后补全长度循环一次即可。

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
def appear_once(lst: list) -> int:
    max_len = 32
    num = '0'.zfill(max_len)
    minus_count = 0
    for i in lst:
        if i < 0:
        	bi = bin(i)[3:]
            minus_count += 1
        else:
            bi = bin(i)[2:]
        bi = bi.zfill(max_len)
        num = bin_add(num, bi)
    res = []
    for i in num:
        res.append(int(i) % 3)
    need = int("".join(map(str, res)), 2)
    if minus_count % 3 == 1:
        return -need
    else:
        return need
def bin_add(num1, num2):
    res = []
    for i in range(len(num1)):
        res.append(int(num1[i]) + int(num2[i]))
    return "".join(map(str, res))

具体实现和测试代码可参考：56_02_NumberAppearingOnce

面试题 57（一）：和为 s 的两个数字

题目：输入一个递增排序的数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。如果有多对数字的和等于 s，输出任意一对即可。

看到有序数组首先想到的就是二分法。从两头开始求和，如果结果比 s 大，右边往左移，否则左边往右移。

1
2
3
4
5
6
7
8
9
10
def sum_is_s(lst: list, s: int):
    l, r = 0, len(lst) - 1
    while l < r:
        add = sum(lst[l], lst[r])
        if add > s:
            r -= 1
        elif add < s:
            l += 1
        else:
            return (lst[l], lst[r])

具体实现和测试代码可参考：57_01_TwoNumbersWithSum

面试题 57（二）：和为 s 的连续正数序列

题目：输入一个正数 s，打印出所有和为 s 的连续正数序列（至少含有两个数）。例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以结果打印出 3 个连续序列 1～5、4～6 和 7～8。

这道题有个关键信息是：连续正数序列，结合上面的题目，可以从 1 开始滚动增加，每增加 1 个数，判断是否与给定数字相等。不相等时，如果比给定数字小，那继续增加；反之从开头减少。

1
2
3
4
5
6
7
8
9
10
11
12
def sum_is_s(s: int):
    l, r = 1, 2
    mid = (1 + s) // 2
    while l < mid:
        add = sum(range(l, r+1))
        if add < s:
            r += 1
        elif add > s:
            l += 1
        else:
            l += 1
            print(list(range(1, r+1)))

有两点特别要注意：

  • 不要忘了 else 的时候也要加 1，要保持自动增长。
  • l < mid 即可（最远加到 mid）。

具体实现和测试代码可参考：57_02_ContinuousSquenceWithSum

面试题 58（一）：翻转单词顺序

题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串 “I am a student.”，则输出 “student. a am I”。

这个题目不难，以空格分开倒着组装就好了， 但如果从字符级别去翻转就会稍微麻烦些，思路和上面的题目有点类似，也就是维护两个指针右移，右边的指向空格时，将词放入 list，左边的移到右边位置，然后继续右移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def pythonic_reverse(string: str):
    return " ".join(reversed(string.split()))

def char_level_reverse(string: str):
    lens = len(string)
    l, r = 0, 1
    res = []
    while l < lens - 1 and r < lens:
        if string[l] == " ":
            l += 1
        elif string[r] == " ":
            res.insert(0, string[l:r])
            l = r
        r += 1
    res.insert(0, string[l:r])
    return " ".join(res)

具体实现和测试代码可参考：58_01_ReverseWordsInSentence

面试题 58（二）：左旋转字符串

题目：字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如输入字符串 “abcdefg” 和数字 2，该函数将返回左旋转 2 位得到的结果 “cdefgab”。

这个题不难，Python 可以直接用拼接，如果按字符级别处理，就先翻转前半部分，再翻转后半部分，拼接后再次翻转就得到了最终的结果。

1
2
3
4
5
6
7
def pythonic_reverse(string: str, index: int):
    return string[index:] + string[:index]

def char_level_reverse(string: str, index: int):
    return reverse(reverse(string[:index]) + reverse(string[index:]))
def reverse(string):
    return string[::-1]

后面这种多次翻转的思路比较新颖。

具体实现和测试代码可参考：58_02_LeftRotateString

面试题 59（一）：滑动窗口的最大值

题目：给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，它们的最大值分别为 {4, 4, 6, 6, 6, 5}，

Naive 的方法就是遍历 index 取窗口内最大值。

1
2
3
4
5
def max_num_in_slide_win(lst: list, win: int) -> int:
    result = []
    for i in range(len(lst)-win+1):
        result.append(max(lst[i:i+win]))
    return result

这种方法的时间复杂度是 O(nk)，其中 n 为列表元素数，k 为窗口大小。书中介绍了两种 O(n) 复杂度的算法，一种是将滑动窗口当做队列，并提前构建一个 O(1) 时间获取最大值的队列；另一种方法是将只可能成为最大值的值存入队列，具体就是额外维护一个队列，将第一个元素加入队列。然后开始遍历数组，如果后一个元素比前一个元素大，说明前一个元素一定不会是最大值，移除；反之，则加入队列。

1
2
3
4
5
6
7
8
9
10
11
def max_num_in_slide_win(lst: list, win: int) -> int:
    res, dq = [], [0]
    for i in range(1, len(lst)):
        res.append(lst[dq[0]])
        while dq and lst[i] >= lst[dq[-1]]:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - win: # 始终保持 win 窗口往前移
            dq.pop(0)
    res.append(lst[dq[0]])
    return res[win-1:]

特别注意两点：

  • 队列 dq 存 index，不要存值
  • 判断队列头 index 是否在窗口内（如果存的是值，这里就没法判断了）

具体实现和测试代码可参考：59_01_MaxInSlidingWindow

面试题 59（二）：队列的最大值

题目：请定义一个队列并实现函数 max 得到队列的最大值，要求函数 max，push_back，pop_front 的时间复杂度都是 O(1)。

这类题目是比较常见的，最主要的是维护一个 max 的存储，push 或 pop 后随时更新 max。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MaxQueue:
    def __init__(self):
        self.data = []
        self.maxes = []
    
    @property
    def max(self):
        if self.maxes:
            return self.maxes[0]
    
    def push_back(self, x):
        self.data.append(x)
        # 把比 x 小的都弹出去
        while self.maxes and x > self.maxes[-1]:
            self.maxes.pop()
        self.maxes.append(x)
    
    def pop_front(self):
        x = self.data.pop(0)
        # 如果正好把最大值弹出去了
        if self.maxes and x == self.maxes[0]:
            self.maxes.pop(0)
        return x

需要注意，queue 的特性是先进先出，所以如果后面进来的数字比之前的大的话，maxes 只要保留后面进来的数字即可，因为它肯定比之前的数字晚出去，也就是说在它出去之前它就是它之前数字中最大的。出去的时候，如果正好是那个最大的数字，就把它也弹出去即可。

具体实现和测试代码可参考：59_02_QueueWithMax

面试题 60：n 个骰子的点数

题目：把 n 个骰子扔在地上，所有骰子朝上一面的点数之和为 s。输入 n，打印出 s的所有可能的值出现的概率。

s 的范围是 n ~ 6n，一共有 6^n 种排列，每个点数的次数除以排列数就是概率。所以主要是找出每个值可能出现的次数。可以用递归的思路，将骰子分成两堆，一堆只有 1 个，另一堆 n-1 个，有 1 个时的点数是 1-6，计算 1-6 每种点数和剩下的 n-1 个骰子计算点数和；n-1 个又可以拆为 1 个和 n-2 个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def get_freq(n):
    freq = [0] * (6 * n - n + 1)
    for i in range(1, 7):
        # 点 i 和剩下的点加
        # 假设 i=1，剩下 1 个骰子，可能的值就是 234567
        freq = frequency(n, n, i, freq)
    return freq
def frequency(n: int, curr: int, sums: int, freq: list):
    if curr == 1:
        freq[sums-n] += 1
    else:
        for i in range(1, 7):
            frequency(n, curr-1, i+sums, freq)
    return freq

比如以 2 个骰子为例：

1
2
3
4
5
6
7
8
9
10
n = 2
list(range(n, 6*n+1, 1))
# 所有可能的值：[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
freq = [0] * (5*n + 1)
# 1 点和剩下的 1 个骰子求和情况
freq = probability(n=2, curr=1, i+1, freq) 
i = 1 # freq = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 表示和为 2 的结果加 1
i = 2 # freq = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 表示和为 3 的结果加 1
# ...
# 只要 n=2 时，`get_count` 的 else 调用时 curr 就会等于 1，此时返回结果，在对应的位置上加 1，也可以直接累加 freq

感觉递归的思路有点绕，书中还介绍了一种基于循环的方法，主要思路是利用两个数组存储骰子每个点数出现的次数，一轮循环中，数组 1 的第 n 个数表示骰子和为 n 出现的次数，下一轮加入一个新的骰子，此时和为 n 出现的次数应该等于上一轮结果中和为 n-1 ~ n-6 次数总和。这是因为新加入一个骰子的点数是 1~6，和为 n 的次数必然就是 n-1 ~ n-6 的次数和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def get_freq(n: int) -> int:
    # 加一个新骰子后，一个数组的第 n 项（和为 n 的次数）等于另一个数组的 n-1 ~ n-6 项之和
    freq1 = [0] + [1] * 6 + [0] * (6*(n-1))
    freq2 = [0] + [0] * (6*n)
    flag = 0
    for k in range(2, n+1):
        if not flag:
            for i in range(6*k+1):
                freq2[i] = 0
                for j in range(1, 6+1):
                    if j <= i:
                        freq2[i] += freq1[i-j]
            flag = 1
        else:
            for i in range(6*k+1):
                freq1[i] = 0
                for j in range(1, 6+1):
                    if j <= i:
                        freq1[i] += freq2[i-j]
            flag = 0
    freq = freq2[n:] if flag else freq1[n:]
    return freq

其实，这个题目还可以更简单，因为每个骰子的点数都是固定的（1-6），所以频率一定会呈现由低到高再到低的对称性，类似于杨辉三角。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def get_freq(n):
    init = [1] * 6
    if n == 1:
        return init
    length = 6 * n - n + 1
    for k in range(1, n):
        pad_len = length - len(init)
        base = init + [0] * pad_len
        for i in range(1, 6):
            update = [0] * i + init + [0] * (pad_len-i)
            base = list_add(base, update)
        init = base
    return base
def list_add(lst1, lst2):
    res = []
    for i in range(len(lst1)):
        add = lst1[i] + lst2[i]
        res.append(add)
    return res

这种思路有点取巧，但很容易理解且效率比较高，如果用 numpy 整体会更高效。

具体实现和测试代码可参考：60_DicesProbability

面试题 61：扑克牌的顺子

题目：从扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这 5 张牌是不是连续的。2～10 为数字本身，A 为 1，J 为 11，Q 为 12，K 为 13，而大、小王可以看成任意数字。

要判断是不是顺子，只需看数组是不是连续即可，也就是最大和最小值的差是否正好等于 5 且没有重复牌。考虑到大小王可以是任意数字，可以看排序后相邻两数之间的空缺（之差减一）总数，如果空缺总数小于或等于大小王的个数那就是连续的，否则不连续。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def dct_sort(lst: list):
    res = []
    dct = dict(zip(range(14), [0]*14))
    for i in lst:
        dct[i] += 1
    for k,v in dct.items():
        res.extend([k] * v)
    return res

def is_continus(lst: list):
    sorted_lst = dct_sort(lst)
    num_zero = 0
    num_gap = 0
    length = len(sorted_lst)
    for i in range(length-1):
        if sorted_lst[i] == 0:
            num_zero += 1
        else:
            if sorted_lst[i] == sorted_lst[i+1]:
                return False
            else:
                num_gap += sorted_lst[i+1] - sorted_lst[i] - 1
    return num_zero >= num_gap

具体实现和测试代码可参考：61_ContinousCards

面试题 62：圆圈中最后剩下的数字

题目：0, 1, …, n-1 这 n 个数字排成一个圆圈，从数字 0 开始每次从这个圆圈里删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。

这个题目是经典的约瑟夫环问题。可以用一个列表来模拟环型数据结构。

1
2
3
4
5
6
7
8
9
10
11
def josephuse(n: int, m: int) -> int:
    lst = list(range(n))
    index = 0
    while len(lst) > 1:
        index += m - 1
        # 当 index 比 n-1 大（大于最大的 index）时，按 n 缩放 index
        while index > n - 1:
            index -= n
        lst.pop(index)
        n -= 1
    return lst[0]

书中另外介绍了一种非常巧妙的思路，通过分析删除数字的规律，找出一个递归公式：

f(n,m)={0n=1[f(n−1,m)+m]%nn>1f(n, m)=\left\{\begin{array}{ll} 0 & n=1 \\ {[f(n-1, m)+m] \% n} & n>1 \end{array}\right.

根据公式很容易写出代码：

1
2
3
4
5
def josephuse(n: int, m: int) -> int:
    last = 0
    for i in range(2, n+1):
        last = (last + m) % i
    return last

具体实现和测试代码可参考：62_LastNumberInCircle☆

面试题 63：股票的最大利润

题目：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖交易该股票可能获得的利润是多少？例如一只股票在某些时间节点的价格为 {9, 11, 8, 5, 7, 12, 16, 14}。如果我们能在价格为 5 的时候买入并在价格为 16 时卖出，则能收获最大的利润 11。

最大利润就是数组中数对差的最大值。Naive 的方法就是遍历两遍数组，找到最大差。我们换个思路，要想让差值最大，其实就是让买价最小，所以我们可以随时更新这个 “最小” 买价和对应的利润（差值）。

1
2
3
4
5
6
7
8
9
10
def max_profit(lst: list) -> int:
    minp = lst[0]
    diff = lst[1] - lst[0]
    for i in range(2, len(lst)):
        if lst[i-1] < minp:
            minp = lst[i-1]
        new_diff = lst[i] - minp
        if new_diff > diff:
            diff = new_diff
    return diff

具体实现和测试代码可参考：63_MaximalProfit

面试题 64：求 1 到 n 之和

题目：求 1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句（A?B:C）。

这个题其实是针对 C++ 的，关键点是让代码用非循环的方式重复执行 n 次。Python 的 Naive 方法：

1
2
from functools import reduce
reduce(lambda x, y: x+y, range(1, n+1))

具体实现和测试代码可参考：64_Accumulate

面试题 65：不用加减乘除做加法

题目：写一个函数，求两个整数之和，要求在函数体内不得使用＋、－、×、÷ 四则运算符号。

这个题目主要是用位运算计算加法。思路是仿照十进制加法，可以分为三步：按位相加、进位、相加前两个结果。第一步，如果两者都为 0 或 1，结果为 0，否则结果为 1，这个和异或是一样的。第二步，只有 1 和 1 相加才会发生进位，这可以看作位与（只有 1 和 1 时结果为 1）运算然后左移 1 位。第三步就是重复前两步，直到不产生进位为止。

1
2
3
4
5
6
7
8
def add(a, b):
    sums = a ^ b
    while b:
        sums = a ^ b
        carry = (a & b) << 1
        a = sums
        b = carry
    return sums

一正一负和为正的情况需要特别注意，这里不再赘述，具体实现和测试代码可参考：65_AddTwoNumbers

书中另外提到了两种不使用新变量交换两个变量值的方法：

1
2
3
4
5
6
7
8
# 基于加减法
a = a + b
b = a - b
a = a - b
# 基于异或
a = a ^ b
b = a ^ b
a = a ^ b

面试题 66：构建乘积数组

题目：给定一个数组 A [0, 1, …, n-1]，请构建一个数组 B [0, 1, …, n-1]，其中 B 中的元素 B [i] =A [0]×A [1]×… ×A [i-1]×A [i+1]×…×A [n-1]。不能使用除法。

简单来说就是构造一个数组，每个元素为初始数组除开该位置的其他位置元素之积。比如给定 A 为 [2,3,4]，则对应的 B 为 [12, 8, 6]。另外，不能用除法。

Naive 的方法就是每个元素遍历一遍数组，时间复杂度是平方级，如何能缩短在线性时间内呢？书中介绍了一种很巧妙的思路：构造一个矩阵，让其对角线元素为 1，表示缺失的数字，这样每一行相乘就是对应位置元素的值。而每一行又可以分为左半部分和右半部分，两个部分可以单独计算：左边从上往下，右边从下往上。还拿上面的例子来说明，构造的矩阵如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
[
    1, 3, 4,
    2, 1, 4,
    2, 3, 1
]
# C[i] = A[0]*A[1]*...A[i-1] = C[i-1]*A[i-1]
# D[i] = A[i+1]*...*A[n-1]   = D[i+1]*A[i+1]
# 左边 [1, 2, 6]
# 右边 [12, 4, 1]
# 合并 [12, 8, 6]
def product_array(lst: list) -> list:
    length = len(lst)
    arr1 = [1] * length
    # 下三角 [1, 2, 6]
    for i in range(1, length):
        arr1[i] =  lst[i-1] * arr1[i-1]
    arr2 = [1] * length
    for i in range(length-2, -1, -1):
        arr2[i] = lst[i+1] * arr2[i+1]
    arr = [1] * length
    for i in range(length):
        arr[i] = arr1[i] * arr2[i]
    return arr

具体实现和测试代码可参考：66_ConstuctArray☆

面试案例

STAR 原则，即 Situation（情景）、Task（任务）、Action（行动）和 Result（结果）。

如果面试题很简单，保证代码完整性和鲁棒性：

  • 基本功能
  • 边界条件
  • 错误处理

如果面试题很难：

  • 画图让抽象问题形象化
  • 使用具体的例子分析隐含的规律
  • 把大问题分解成两个或多个小问题再递归地解决

很多面试题不止一种方案，可以从时间复杂度和空间复杂度两方面选择最优的解法。

除了编程能力，还可能会关注：沟通能力、学习能力、知识迁移能力、抽象建模能力和发散思维能力等。

面试题 67：把字符串转换成整数

题目：请你写一个函数 StrToInt，实现把字符串转换成整数这个功能。当然，不能使用 atoi 或者其他类似的库函数。

这个题是整本书最恶心的，没有之一，因为它要考虑的情况实在是太多了。从测试用例开始是个不错的习惯。

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
# 正常输入
assert str2int("123") == 123
assert str2int("+123") == 123
assert str2int("-123") == -123
assert str2int("++123") == 123
assert str2int("--123") == 123
assert str2int("-+--123") == -123
# 合法输入非法格式
assert str2int("++02") == 0
assert str2int("+02") == 0
assert str2int("-02") == 0
assert str2int("--02") == 0
assert str2int("001") == 0
# 0 输入
assert str2int("0") == 0
assert str2int("000") == 0
assert str2int("+0") == 0
assert str2int("++0") == 0
assert str2int("-0") == 0
assert str2int("--0") == 0
# 输入运算符
assert str2int("+") == 0
assert str2int("++") == 0
assert str2int("-") == 0
assert str2int("--") == 0
# 非法输入
assert str2int("1a2") == 0
assert str2int("") == 0
# 超出范围
assert str2int("+2147483648") == 0
assert str2int("-2147483649") == 0

简单而言就分为上面的几种情况，其实科学计数法也是一种情况，比如 1e2 = 100，不过这个其实是小数，这里就考虑它；另外，也不考虑运算的情况，比如 1*1=1。

然后考虑一下实现，首先需要关注一下正负值，也就是数字开始之前的 + 和 - 的数量，这决定了最终结果是正的还是负的，如果数字中间出现非 0~9 的均可以退出循环，返回 invalid；然后要考虑 + 和 - 之后数字第一个是 0 的情况，因为如果所有后面的都为 0，那最终的结果也为 0，否则是不合法的，当然如果 + 和 - 之后没有内容了，自然也是不合法的；最后就是考虑越界的情况。

具体实现起来，可以把整个过程分为两部分，即正负号之前的和正负号之后的。之前的正负号可以是 0 个或多个；之后的字符也可以是 0 个或多个，只不过要区分几种情况：

  • 0 开头的
  • 是否为空
  • 是否包含 0~9 之外的字符
  • 是否越界
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
38
def get_sign_num(s: str) -> int:
    signs = set(("+", "-"))
    length = len(s)
    i, k = 0, 0
    while i < length and s[i] in signs:
        if s[i] == "-":
            k += 1
        i += 1
    return i, k
def str2int(s: str) -> int:
    digits = set(map(str, range(10)))
    sign_num, minus_num = get_sign_num(s)
    s = s[sign_num:]
    if not s:
        print("invalid => with only + or -")
        return 0
    if s[0] == "0":
        for i in s[1:]:
            if i != "0":
                print("invalid => 0xx")
                return 0
    for i in s:
        if i not in digits:
            print("invalid => must be 0~9 or + -")
            return 0
    minus = True if minus_num % 2 == 1 else False
    return toint(s, minus)
def toint(s: str, minus: bool) -> int:
    length = len(s)
    num = 0
    for i in s:
        num += int(i) * 10 ** (length - 1)
        length -= 1
    if minus:
        num = -num
    if num > 0x7FFFFFFF or num < -0x80000000:
        return 0
    return num

具体实现和测试代码可参考：67_StringToInt

面试题 68：树中两个节点的最低公共祖先

题目：输入两个树节点，求它们的最低公共祖先。

相比题目，整个沟通过程感觉更加有意思。

如果是二叉搜索树，左子树节点都比父节点小，右子树节点都比父节点大，所以只要从当前节点开始和给定的两个节点比较：如果当前节点比两个节点值都大，最低的公共父节点一定在左子树；否则一定在右子树。当找到第一个在两个节点之间的节点就是要求的最低公共祖先。

如果是一棵普通的树，但是每个节点都有指向父节点的指针，问题可以转换为求两个链表的第一个公共节点。输入两个节点，它们分别对应一条到根节点的链表，它们的最低公共祖先正好是第一个公共节点。

如果节点没有指向父节点的指针，应聘者先想到的方法是判断两个节点是否在某个子树中，如果两个节点在某个节点的子树，同时不在该节点的子节点中，那这个节点就是要找的最低公共祖先。这一想法利用了 “有最低公共祖先，说明一定在一棵子树中” 的想法。

最终的方法是先找出两个节点的路径（链表），然后求两个路径的最后公共节点。这种方法需要占用 O(N) 的存储空间，时间复杂度为 O(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
29
30
31
32
33
class Node:
    def __init__(self, val):
        self.val = val
        self.children = []

def get_lowest_ancestor_of_two_nodes(tree, node1, node2):
    path1, path2 = [], []
    path1 = get_path_of_node(tree, node1, path1)
	path2 = get_path_of_node(tree, node2, path2)
    return get_last_common_node(path1, path2)

def get_path_of_node(tree, node, path):
    if tree.val == node.val:
        return True
    else:
        path.append(tree.val)
        found = False
    for i in range(len(tree.children)):
        if not found:
            found = get_path_of_node(tree.children[i], node, path)
    # 注意这一步，没找到要回退一步
    if not found:
        path.pop()
    return found
    
def get_last_common_node(path1, path2):
    i = 0
    last = None
    while i < len(path1) and i < len(path2):
        if path1[i] == path2[i]:
            last = path[i]
        i += 1
    return last

具体实现和测试代码可参考：68_CommonParentInTree

后记：

陆陆续续刷了 X 个月才刷完，重新整理又断断续续花了几个月，但是收获确实很多。书中的题目大多数都比较经典，作者很注意方法，这就意味着如果把这些内容都掌握了，很多题目其实做起来都差不多了。总之，是本很不错的书，非常感谢作者。

参考资料