具体实现和测试代码 :
系列解析 (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) : 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: return dp(s, p[2 :]) or dp(s[1 :], p[2 :]) or dp(s[1 :], p) else : 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 :]) 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 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 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: if equal(tree.val, sub.val): 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