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

具体实现和测试代码：

系列解析（TBD）：

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

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

第三章：高质量的代码

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

面试题 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++ 中这并不是有效的数字。但是 0000 和 0001.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