剑指 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++ 中这并不是有效的数字。但是 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