动机 个人觉得在准备找工作要刷题前，先刷一遍这本书的问题，再去刷LeetCode这类的OJ比较合适。难度循序渐进，亦有理论支撑。
阅读流程：按照目录去索引问题，找到问题后，先看问题描述 ，思考问题解决思路；然后看思路 ，获取提示；然后阅读优点 和复杂度 ，检查和自己想的是否一致。
用到的数据结构 数据结构定义：
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 """Self-defined data structures and some tool functions.""" from __future__ import print_functionfrom __future__ import absolute_importfrom __future__ import divisionclass ListNode : """List node.""" def __init__ (self, x ): self .val = x self .next = None class TreeNode : """Tree node.""" def __init__ (self, x ): self .val = x self .left = None self .right = None class RandomListNode : """List node with a random field.""" def __init__ (self, x ): self .val = x self .next = None self .random = None class TreeLinkNode : def __init__ (self, x ): self .val = x self .left = None self .right = None self .next = None def print_list (head_node ): """Traverse a list and print.""" vals = [] while head_node: vals.append(head_node.val) head_node = head_node.next if len (vals) > 0 : print (" " .join(map (str , vals))) else : print ("This node list is empty!" ) def print_random_list (head_node ): """Traverse a random list and print.""" while head_node: if head_node.next is not None : val_of_next = head_node.next .val else : val_of_next = None if head_node.random is not None : val_of_random = head_node.random.val else : val_of_random = None print ("val: {}, val of next: {}, val of random: {} " .format (head_node.val, val_of_next, val_of_random)) head_node = head_node.next def print_tree (root_node ): """Travers a tree by level and print.""" travers = [] queue = [root_node] while len (queue) > 0 : farther = queue.pop() travers.append(farther.val) if farther: if farther.left: queue.insert(0 , farther.left) if farther.right: queue.insert(0 , farther.right) print (" " .join(map (str , travers))) def init_nodes_by_list (l ): """Initialize a List nodes with a given list of values.""" head = last_node = ListNode(l[0 ]) for one in l[1 :]: node = ListNode(one) last_node.next = node last_node = node return head
NO.3 数组中重复的数字
问题描述 ：在一个长度是n的数组里的所有数字都在0～n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3.思路 ：如果先排序，则时间复杂度是$O(logn)$。注意到数字的范围，所以如果将每个检查到的数，换到以这个数为下标的位置，则数组不会溢出。而且在交换的过程中，可以很快地检查是否有重复。优点 ：时间复杂度低。时间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def isDuplicate (nums ): l = len (nums) for i in range (l): cur_val = nums[i] while cur_val != i: if nums[cur_val] == cur_val: return cur_val else : nums[cur_val], nums[i] = nums[i], nums[cur_val] return -1
1 2 test_nums = [2 , 3 , 1 , 0 , 2 , 5 , 3 ] isDuplicate(test_nums)
NO.4 二维数组的查找
问题描述 ：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。思路 ：从右上角开始判断，若小于则在左边，大于则在下面。直到找完。优点 ：区域不会重合时间复杂度 ：$O(m+n)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def Find (target, array ): m = len (array) n = len (array[0 ]) j = n-1 i = 0 while i < m and j >= 0 : if array[i][j] == target: return True elif array[i][j] < target: i += 1 else : j -= 1 return False
1 Find(7 , [[1 , 2 , 8 , 9 ], [2 , 4 , 9 , 12 ], [4 , 7 , 10 , 13 ], [6 , 8 , 11 , 15 ]])
NO.6 从尾到头打印链表
问题描述 ：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。思路 ：使用一个栈，保存正序遍历的值。空间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 10 def printListFromTailToHead (listNode ): values = [] stack = [] while listNode != None : stack.append(listNode.val) listNode = listNode.next for _ in range (len (stack)): values.append(stack.pop()) return values
1 2 3 4 5 6 l1 = ListNode(1 ) l2 = ListNode(2 ) l3 = ListNode(3 ) l1.next = l2 l2.next = l3 print (printListFromTailToHead(l1))
NO.7 重建二叉树
问题描述 ：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出二叉树并输出它的头结点。思路 ：根据中序遍历和前序遍历可以很快找到（左子树，根，右子树）的分割，用递归实现。优点 ：思路简单清晰。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def reConstructBinaryTree (preorder, inorder, length ): if not preorder or not inorder or length == 0 : return return constructCore(preorder, inorder, 0 , length-1 , 0 , length-1 ) def constructCore (preorder, inorder, p_s, p_e, i_s, i_e ): root_val = preorder[p_s] root = TreeNode(root_val) if p_s == p_e or i_s == i_e: return root root_ind = inorder.index(root_val) left_len = root_ind - i_s right_len = i_e - root_ind if left_len > 0 : root.left = constructCore(preorder, inorder, p_s+1 , p_s+left_len, i_s, root_ind-1 ) if right_len > 0 : root.right = constructCore(preorder, inorder, p_s+left_len+1 , p_e, root_ind+1 , i_e) return root
1 2 3 pre = [1 ,2 ,4 ,7 ,3 ,5 ,6 ,8 ] tin = [4 ,7 ,2 ,1 ,5 ,3 ,8 ,6 ] print_tree(reConstructBinaryTree(pre, tin, 8 ))
NO.8 二叉树的下一个节点
问题描述 ：给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。思路 ：优点 ：
NO.9 用两个栈实现队列
问题描述 ：用两个栈实现一个队列。请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。思路 ：一个栈负责入队，另一个栈负责出队。时间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class CQueue : def __init__ (self ): self .stack1 = [] self .stack2 = [] def appendTail (self, val ): self .stack1.append(val) def deleteHead (self ): if len (self .stack2) == 0 : for _ in range (len (self .stack1)): self .stack2.append(self .stack1.pop()) if len (self .stack2) == 0 : print ("Queue is empty!" ) return return self .stack2.pop()
1 2 3 4 5 6 7 8 cqueue = CQueue() cqueue.appendTail(1 ) cqueue.appendTail(2 ) cqueue.appendTail(3 ) print (cqueue.deleteHead())print (cqueue.deleteHead())print (cqueue.deleteHead())print (cqueue.deleteHead())
1 2 3 4 5 1 2 3 Queue is empty! None
NO.10 斐波那契数列
问题描述 ：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。思路 ：不用递归，用保存数组的方式。优点 ：时间复杂度比递归小。时间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 10 11 def Fibonacci (n ): if n < 2 : return 0 minus_one = 1 minus_two = 0 res = 0 for i in range (2 , n+1 ): res = minus_one + minus_two minus_two = minus_one minus_one = res return res
1 2 for i in range (10 ): print ((i, Fibonacci(i)), end=" " )
1 (0, 0) (1, 0) (2, 1) (3, 2) (4, 3) (5, 5) (6, 8) (7, 13) (8, 21) (9, 34)
快速排序 快排的整体思想就是每次执行一次partition，然后根据partition返回的位置将数组分成两段，再递归地对这两段子序列进行快排。
partition: 将当前第一个元素作为pivot，小的元素往前移到pivot的前面，大的元素往后移到pivot的后面。
1 2 3 4 5 6 7 8 9 def quickSort (data, l, s, e ): if s == e: return pivot_index = partition(data, l, s, e) if pivot_index > s: quickSort(data, l, s, pivot_index - 1 ) if pivot_index < e: quickSort(data, l, pivot_index + 1 , e)
不同的快排实现差别主要在partition的实现上。下面是《Problem Solving with Algorithms and Data Structures》上的解法。
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
《剑指offer》的写法，倾向用这种。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def partition (data, l, s, e ): """记录一个small指针和当前指针""" if s == e: return s small = s pivot_index = s pivot_value = data[pivot_index] for i in range (s, e): if data[i] < pivot_value: small += 1 data[i], data[small] = data[small], data[i] data[small], data[s] = data[s], data[small] return small
1 2 3 test_data = [11 , 8 , 15 , 3 , 2 , 4 , 6 , 9 , 7 , 22 ] quickSort(test_data, 10 , 0 , 9 ) print (test_data)
1 [2, 3, 6, 4, 7, 8, 9, 11, 15, 22]
NO.11 旋转数组的最小数字
问题描述 ：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。思路 ：注意到最小的元素刚好是这两个子数组的分界线，用二分查找法的思路来寻找这个最小的元素。提示：１．第一个元素应该是大于或者等于最后一个元素的。２．前面子序列的元素都大于或者等于后面的子序列的元素。优点 ：时间复杂度低。时间复杂度 ：$O(logn)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def findRotateMin1 (data ): """使用二分查找寻找最小值，初版""" l = len (data) if l == 0 : print ("Data is empty." ) return s = 0 e = l - 1 while s < e: if e - s == 1 : mid = e break mid = (s + e) // 2 if data[mid] < data[s]: e = mid else : s = mid return data[mid]
1 findRotateMin1([3 ,4 ,5 ,1 ,2 ])
正确
1 findRotateMin1([1 ,0 ,1 ,1 ,1 ])
错误。
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 def minInOrder (data, s, e ): """顺序查找""" res = data[s] for i in range (s + 1 , e + 1 ): if res > data[i]: res = data[i] return res def findRotateMin2 (data ): """使用二分查找寻找最小值，完整版""" l = len (data) if l == 0 : print ("Data is empty." ) return s = 0 e = l - 1 while s < e: if e - s == 1 : mid = e break mid = (s + e) // 2 if data[mid] == data[s] and data[mid] == data[e]: return minInOrder(data, s, e) if data[mid] < data[s]: e = mid else : s = mid return data[mid]
1 findRotateMin2([3 ,4 ,5 ,1 ,2 ])
1 findRotateMin2([1 ,0 ,1 ,1 ,1 ])
都正确。
回溯 回溯法可以看成是蛮力法的升级版，它从解决问题每一步的所有可能选项里面系统地选择出一个可行的解决方案。回溯法非常适合由多个步骤 组成，并且每个步骤都有多个选项。
下面两道题涉及回溯的思想，在解决回溯类的问题时，脑海中要想象一棵搜索树 ，树的每一层对应着一个步骤的搜索空间，如果在某层搜索失败，则需要回溯 到上一步骤。
NO.12 矩阵中的路径
问题描述 ：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如[["a", "b", "t", "g"], ["c", "f", "c", "s",], ["j", "d", "e", "h"]]矩阵中包含一条字符串”bfce”的路径，但是矩阵中不包含”abfb”路径，因为字符串的第一个字符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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 def hasPath (matrix, rows, columns, target_path ): if len (target_path) == 0 : return True first_candidates = [] for i in range (rows): for j in range (columns): if matrix[i][j] == target_path[0 ]: first_candidates.append((i, j)) if len (first_candidates) == 0 : return False for r, c in first_candidates: if hasPathCore(matrix, rows, columns, target_path, [(r, c)]): return True return False def hasPathCore (matrix, rows, columns, target_path, cur_path ): if len (target_path) == len (cur_path): return True target_char = target_path[len (cur_path)] possible_points = [] cur_point = cur_path[-1 ] if cur_point[0 ] > 0 : possible_point = (cur_point[0 ] - 1 , cur_point[1 ]) if possible_point not in cur_path: possible_points.append(possible_point) if cur_point[1 ] > 0 : possible_point = (cur_point[0 ], cur_point[1 ] - 1 ) if possible_point not in cur_path: possible_points.append(possible_point) if cur_point[0 ] < rows - 1 : possible_point = (cur_point[0 ] + 1 , cur_point[1 ]) if possible_point not in cur_path: possible_points.append(possible_point) if cur_point[1 ] < columns - 1 : possible_point = (cur_point[0 ], cur_point[1 ] + 1 ) if possible_point not in cur_path: possible_points.append(possible_point) if len (possible_points) == 0 : return False for possible_point in possible_points: if matrix[possible_point[0 ]][possible_point[1 ]] == target_char: if hasPathCore(matrix, rows, columns, target_path, cur_path + [possible_point]): return True return False
1 2 3 test_matrix = [["a" , "b" , "t" , "g" ], ["c" , "f" , "c" , "s" ,], ["j" , "d" , "e" , "h" ]] print (hasPath(test_matrix, 3 , 4 , "bfce" ))print (hasPath(test_matrix, 3 , 4 , "abfb" ))
NO.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 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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 def movingCount (threshold, rows, cols ): if rows <=0 or cols <= 0 : return 0 reach_matrix = [[0 for j in range (cols)] for i in range (rows)] movingCountCore(reach_matrix, threshold, rows, cols, (0 , 0 )) count = 0 for i in range (rows): for j in range (cols): if reach_matrix[i][j] == 1 : count += 1 print ("reach_matrix:" , reach_matrix) return count def movingCountCore (reach_matrix, threshold, rows, cols, cur_point ): possible_next_points = getPossibleNextPoints(reach_matrix, rows, cols, cur_point) if len (possible_next_points) == 0 : return for point in possible_next_points: if checkIsLegal(threshold, point): reach_matrix[point[0 ]][point[1 ]] = 1 movingCountCore(reach_matrix, threshold, rows, cols, point) else : reach_matrix[point[0 ]][point[1 ]] = -1 def getPossibleNextPoints (reach_matrix, rows, cols, cur_point ): r = cur_point[0 ] c = cur_point[1 ] possible_next_points = [] if r > 0 and reach_matrix[r - 1 ][c] == 0 : possible_next_points.append((r - 1 , c)) if c > 0 and reach_matrix[r][c - 1 ] == 0 : possible_next_points.append((r, c - 1 )) if r < rows - 1 and reach_matrix[r + 1 ][c] == 0 : possible_next_points.append((r + 1 , c)) if c < cols - 1 and reach_matrix[r][c + 1 ] == 0 : possible_next_points.append((r, c + 1 )) return possible_next_points def checkIsLegal (threshold, point ): r = point[0 ] c = point[1 ] return getDigitSum(r) + getDigitSum(c) <= threshold def getDigitSum (num ): res = num % 10 while num // 10 != 0 : num = num // 10 res += num % 10 return res
1 2 3 reach_matrix: [[1, 1, 1], [1, 1, -1], [1, -1, 0]] 6
动态规划 使用动态规划的问题的三个特点 ：
1.问题本身是求解一个最优解。
2.这个最优解依赖于各个子问题的最优解。
3.大问题可以分解成若干小问题，小问题之间还有相互重叠的更小的子问题。
贪婪算法 贪婪算法解决问题：每一步都可以做出一个贪婪 的选择，基于这个选择，我们确定能够得到最优解。与此同时，我们必须要用数学方式证明贪婪选择是正确的。
NO.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。思路 ：动态规划。时间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 def maxProductAfterCuttingDP (length ): max_product = list (range (length + 1 )) for i in range (1 , length + 1 ): for j in range (i): candidate = max_product[j] * max_product[i - j] if candidate > max_product[i]: max_product[i] = candidate print ("max_product: " , max_product) return max_product[-1 ]
1 maxProductAfterCuttingDP(8 )
1 2 3 max_product: [0, 1, 2, 3, 4, 6, 9, 12, 18] 18
贪婪算法解法
思路 ：贪婪算法。时间复杂度 ：$O(1)$ 策略：当$n\geq5$时，尽可能多地将剪绳子成长度为3；当剩下的绳子长度是4时，把绳子剪成两段长度是2的绳子。
证明：当$n\geq 5$时，$2(n-2)\geq n$，$3(n-3)\geq n$且$3(n-3)\geq 2(n-2)$。但如果长度剪成其他大于3的长度，则一定可以用剪成两段2或者更多的3来替代。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def maxProductAfterCuttingGreedy (length ): if length < 2 : return 0 if length == 2 : return 1 if length == 3 : return 2 times_of_3 = length // 3 if length - times_of_3 * 3 == 1 : times_of_3 -= 1 times_of_2 = (length - times_of_3 * 3 ) // 2 print ("times_of_3: " , times_of_3, "times_of_2: " , times_of_2) return pow (3 , times_of_3) * pow (2 , times_of_2)
1 maxProductAfterCuttingGreedy(8 )
1 2 3 times_of_3: 2 times_of_2: 1 18
NO.15 二进制中1的个数
问题描述 ：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001，有2位是1。因此如果输入9，该函数输出2。思路 ：设置一个对比的数，flag，从1开始，每次右移一位，每次与原数字做与运算。优点 ：简单，且能解决负数的情况。
1 2 3 4 5 6 7 8 9 10 11 def NumberOfOne (n ): count = 0 flag = 1 i = 0 while flag and i < 32 : if n & flag: count += 1 flag = flag << 1 i += 1 return count
NO.16 数值的整数次方
问题描述 ：实现函数double Power（double base, int exponent），求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。思路 ：当$n$为奇数：$x^n=(x^2)^{n/2}×x$；当$n$为偶数：$x^n=(x^2)^{n/2}$优点 ：节省乘法的次数。时间复杂度 ：$O(logn)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def Power (x, n ): """x^n""" if x == 0 and n < 0 : return 0 abs_n = abs (n) res = PowerWithAbsExponent(x, abs_n) if n < 0 : res = 1.0 /res return res def PowerWithAbsExponent (x, abs_n ): if abs_n == 0 : return 1 if abs_n == 1 : return x res = PowerWithAbsExponent(x, abs_n>>1 ) res *= res if abs_n & 1 == 1 : res *= x return res
NO.17 打印1到最大的n位数
问题描述 ：输入数字n，按顺序打印出从1最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数即999。陷阱 ：这个问题属于大数类 的问题，即给定n过大，n位的整数肯定不能用长整型保存。
1 2 3 4 5 6 def Print1ToMaxOfNDigitsWrong (n ): end = pow (10 , n) print (end)
1 Print1ToMaxOfNDigitsWrong(100 )
1 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
但是这种题好像对python没有影响。。。
思路 ：转换成全排列 问题，使用递归 完美解决。(有点像深度优先遍历)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 def Print1ToMaxOfNDigits (n ): if n <= 0 : return number = ["0" for _ in range (n)] for i in range (10 ): number[0 ] = str (i) Print1ToMaxOfNDigitsRecursively(number, n, 0 ) def Print1ToMaxOfNDigitsRecursively (number, l, index ): if index == l - 1 : printNumber(number) return for i in range (10 ): number[index + 1 ] = str (i) Print1ToMaxOfNDigitsRecursively(number, l, index + 1 ) def printNumber (number ): done = False while number[0 ] == "0" and len (number) > 1 : number = number[1 :] print ("" .join(number), end=" " )
1 0 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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
NO.18 在O（1）时间删除链表结点
问题描述 ：给定单向链表的头指针和一个结点指针，定义一个函数在$O(1)$时间删除该结点思路 ：普通思路：从头遍历，找到当前节点的前一个节点，将这个节点指向当前节点的下一个节点，时间复杂度$O(n)$。优秀思路：将当前节点的写一个节点的值拷贝到当前节点，删除下一个节点。陷阱 ：如果要删除的是最后一个节点，解决方案需要调整。优点 ：时间复杂度低。缺点 ：这种方式采用拷贝的形式，改变了之前节点的对象。时间复杂度 ：$O(1)$
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 deleteNode (list_head, node_to_delete ): """删除链表中的指定节点。 注意，这里判断两个节点是否相同的方式仅仅是判断两个节点的值是否相同。""" if list_head is None or node_to_delete is None : return list_head if node_to_delete.next is None : if node_to_delete.val == list_head.val: del node_to_delete, list_head list_head = None return list_head cur_node = list_head while cur_node.next is not None and cur_node.next .val != node_to_delete.val: cur_node = cur_node.next if cur_node.next is not None and cur_node.next .val == node_to_delete.val: cur_node.next = None del node_to_delete return list_head else : next_node = node_to_delete.next node_to_delete.next = next_node.next node_to_delete.val = next_node.val del next_node return list_head
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 n1 = ListNode(1 ) new_head = deleteNode(n1, n1) print_list(new_head) n1 = ListNode(1 ) n2 = ListNode(2 ) n3 = ListNode(3 ) n4 = ListNode(4 ) n5 = ListNode(5 ) n1.next = n2 n2.next = n3 n3.next = n4 n4.next = n5 new_head = deleteNode(n1, n3) print_list(new_head) new_head = deleteNode(new_head, n5) print_list(new_head)
1 2 3 This node list is empty! 1 2 4 5 1 2 4
1 2 3 new_node = ListNode(3 ) new_node.next = n3.next new_node == n3
NO.19 正则表达式匹配
问题描述 ：请实现一个函数用来匹配包括.和*的正则表达式。模式中的字符.表示任意一个字符，而*表示它前面的字符可以出现任意次（包含0次） 。在本题中，匹配是指字符串的所有字符匹配整个模式 。例如，字符串”aaa”与模式a.a和ab*ac*a匹配，但是与aa.a和ab*a均不匹配。思路 ：递归、非确定有限状态机。优点 ：思路清晰。
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 39 40 41 42 43 def match (string, pattern ): if len (string) == 0 or len (pattern) == 0 : return False return matchCore(string, pattern) def matchCore (string, pattern ): if len (string) == 0 and len (pattern) == 0 : return True if len (string) != 0 and len (pattern) == 0 : return False if len (string) == 0 : if pattern[-1 ] != "*" or len (pattern) % 2 != 0 : return False if len (pattern) == 2 : return True return matchCore(string, pattern[2 :]) if len (pattern) < 2 or pattern[1 ] != "*" : if pattern[0 ] == string[0 ] or pattern[0 ] == "." : return matchCore(string[1 :], pattern[1 :]) else : return False else : if pattern[0 ] == string[0 ] or (pattern[0 ] == "." and len (string) > 0 ): if matchCore(string[1 :], pattern[2 :]): return True if matchCore(string, pattern[2 :]): return True if matchCore(string[1 :], pattern): return True return False else : return matchCore(string, pattern[2 :])
1 2 3 4 5 print (match ("aaa" , "a.a" ))print (match ("aaa" , "ab*ac*a" ))print (match ("aaa" , "aa.a" ))print (match ("aaa" , "ab*a" ))print (match ("a" , "ab*a*" ))
1 2 3 4 5 True True False False True
NO.20 表示数值的字符串
问题描述 ：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。思路 ：表示数字的字符串遵循模式A[.[B]][e|EC]或者.B[e|EC]，其中A为数值的整数部分，B紧跟着小数点为数值的小数部分，C紧跟e或者E是数值的指数部分。
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 39 40 41 42 43 def scanUnsignedInteger (string ): if len (string) == 0 : return False , 0 i = 0 while i < len (string) and string[i].isdigit(): i += 1 return i > 0 , i def scanInteger (string ): if len (string) == 0 : return False , 0 if string[0 ] == "-" or string[0 ] == "+" : found, index = scanUnsignedInteger(string[1 :]) return found, index + 1 else : return scanUnsignedInteger(string) def isNumeric (string ): if len (string) == 0 : return False found_1 = found_2 = found_3 = False found_1, index = scanInteger(string) string = string[index:] is_numeric = found_1 if len (string) > 0 and string[0 ] == "." : string = string[1 :] found_2, index = scanUnsignedInteger(string) string = string[index:] is_numeric = found_2 or is_numeric if len (string) > 0 and (string[0 ] == 'e' or string[0 ] == 'E' ): string = string[1 :] found_3, index = scanInteger(string) string = string[index:] is_numeric = found_3 and is_numeric return is_numeric and len (string) == 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 print (isNumeric("+100" ))print (isNumeric("123" ))print (isNumeric("5e2" ))print (isNumeric("-123" ))print (isNumeric("3.1416" ))print (isNumeric("-1E-16" ))print ()print (isNumeric("12e" ))print (isNumeric("1a3.14" ))print (isNumeric("1.2.3" ))print (isNumeric("+-5" ))print (isNumeric("12e+4.3" ))
1 2 3 4 5 6 7 8 9 10 11 12 True True True True True True False False False False False
NO.21 调整数组顺序使奇数位于偶数前面
问题描述 ：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。思路 ：看到这题想到了快排的partition，只不过一个标准是小的在前，大的在后面。提示：双指针。优点 ：可扩展性高。时间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def Reorder (data, reorder_func ): l = len (data) if l == 0 or reorder_func is None : return s = 0 e = l - 1 while s < e: while s < e and not reorder_func(data[s]): s += 1 while s < e and reorder_func(data[e]): e -= 1 if s < e: data[s], data[e] = data[e], data[s] def isEven (n ): return (n % 2 ) == 0 def ReorderOddEven (data ): Reorder(data, isEven)
1 2 3 test_data = [1 ,2 ,3 ,4 ,5 ] ReorderOddEven(test_data) print (test_data)
NO.22 链表中倒数第k个节点
问题描述 ：输入一个链表，输出该链表中倒数第k个结点。为符合计数习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。如：一个链表有6个节点，从头节点开始，它们的值一次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。思路 ：两个指针。陷阱 ：如果链表长度小于k会不会有问题？时间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def findKthToTail (head_node, k ): if head_node is None or k <= 0 : return False , -1 ahead = head_node behind = head_node for i in range (k - 1 ): if ahead.next != None : ahead = ahead.next else : return False , -1 while ahead.next is not None : ahead = ahead.next behind = behind.next return True , behind.val
1 2 3 4 5 6 7 8 9 10 11 12 13 14 n1 = ListNode(1 ) n2 = ListNode(2 ) n3 = ListNode(3 ) n4 = ListNode(4 ) n5 = ListNode(5 ) n6 = ListNode(6 ) n1.next = n2 n2.next = n3 n3.next = n4 n4.next = n5 n5.next = n6 print (findKthToTail(n1, 3 ))print (findKthToTail(n1, 0 ))print (findKthToTail(n1, 7 ))
1 2 3 (True, 4) (False, -1) (False, -1)
NO.23 链表中环的入口节点
问题描述 ：如果一个链表中包含环，请找出该链表的环的入口结点。如：在1->2->3->4->5->6->3的链表中，包含一个环，环的入口节点是3。思路 ：先确定环的长度$n$，再确定入口位置（用$k$表示从起点到入口的距离）。1：使用两个速度不一样的指针取遍历，当二者相遇时，说明被套圈了 。套圈说明差距是$n$的整数倍，不能保证一定是$n$；但套圈还说明了相遇的点一定在环中 ，在这个节点上重新开始遍历，回到本身时，遍历次数即是长度。2：使用同样速度一前一后的两个指针，前面的指针先走$n$步，然后后面的指针和前面的指针一起走，当二者第一次相遇时，慢指针正好走了$k$步，快指针走了$n+k$步，都在环入口处。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def meetingNode (headNode ): """在存在环的前提下，找到一快一慢两个指针相遇的节点。""" if headNode is None : return slow = headNode.next if slow is None : return fast = slow.next while fast is not None and slow is not None : if fast == slow: return fast slow = slow.next fast = fast.next if fast is not None : fast = fast.next return
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 def entryNodeOfLoop (headNode ): meeting_node = MeetingNode(headNode) if meeting_node is None : return n = 1 node = meeting_node while node.next != meeting_node: node = node.next n += 1 ahead = headNode for i in range (n): ahead = ahead.next behind = headNode while ahead != behind: ahead = ahead.next behind = behind.next return ahead
1 2 3 4 5 6 7 8 9 10 11 12 13 14 n1 = ListNode(1 ) n2 = ListNode(2 ) n3 = ListNode(3 ) n4 = ListNode(4 ) n5 = ListNode(5 ) n6 = ListNode(6 ) n1.next = n2 n2.next = n3 n3.next = n4 n4.next = n5 n5.next = n6 n6.next = n3 entry = entryNodeOfLoop(n1) print (entry.val)
NO.24 反转链表
问题描述 ：输入一个链表的头节点，反转链表并输出反转链表的头节点。思路 ：递归。优点 ：思路简单。时间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 def reverseListRecursive (headNode ): if headNode is None : return None , None if headNode.next is None : return headNode, headNode new_tail, new_head = reverseListRecursive(headNode.next ) new_tail.next = headNode headNode.next = None return headNode, new_head
1 2 3 4 5 6 7 8 9 10 11 12 13 n1 = ListNode(1 ) n2 = ListNode(2 ) n3 = ListNode(3 ) n4 = ListNode(4 ) n5 = ListNode(5 ) n6 = ListNode(6 ) n1.next = n2 n2.next = n3 n3.next = n4 n4.next = n5 n5.next = n6 new_tail, new_head = reverseListRecursive(n1) print_list(new_head)
思路 ：也可以直接正向遍历。优点 ：运行开销没有递归大。时间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def reverseList (headNode ): if headNode is None : return if headNode.next is None : return headNode prevNode = headNode node = headNode.next headNode.next = None while node.next != None : nextNode = node.next node.next = prevNode prevNode = node node = nextNode node.next = prevNode return node
1 2 3 4 5 6 7 8 9 10 11 12 13 n1 = ListNode(1 ) n2 = ListNode(2 ) n3 = ListNode(3 ) n4 = ListNode(4 ) n5 = ListNode(5 ) n6 = ListNode(6 ) n1.next = n2 n2.next = n3 n3.next = n4 n4.next = n5 n5.next = n6 new_head = reverseList(n1) print_list(new_head)
NO.25 合并两个排序的链表
问题描述 ：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调递增规则。如：链表1：1->3->5；链表2：2->4->6；合并后为：1->2->3->4->5->6。思路 ：递归。优点 ：思路清晰。时间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 10 11 12 13 def mergeList (head1, head2 ): if head1 is None : return head2 if head2 is None : return head1 if head1.val < head2.val: new_head = mergeList(head1.next , head2) head1.next = new_head return head1 else : new_head = mergeList(head1, head2.next ) head2.next = new_head return head2
1 2 3 4 5 6 7 8 9 10 11 12 n1 = ListNode(1 ) n2 = ListNode(2 ) n3 = ListNode(3 ) n4 = ListNode(4 ) n5 = ListNode(5 ) n6 = ListNode(6 ) n1.next = n3 n3.next = n5 n2.next = n4 n4.next = n6 new_head = mergeList(n1, n2) print_list(new_head)
NO.26 树的子结构
问题描述 ：输入两棵二叉树A和B，判断B是不是A的子结构。思路 ：分成两步：1.在A中找到和B的根节点的值一样的节点R；2.判断A中以R为根节点的子树是不是包含和B一样的结构。时间复杂度 ：$O(n×m)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 def hasSubtree (root1, root2 ): res = False if root1 is not None and root2 is not None : if root1.val == root2.val: res = doesTree1HasTree2(root1, root2) if not res: res = hasSubtree(root1.left, root2) if not res: res = hasSubtree(root1.right, root2) return res def doesTree1HasTree2 (root1, root2 ): if root2 is None : return True if root1 is None : return False if root1.val != root2.val: return False return doesTree1HasTree2(root1.left, root2.left) and doesTree1HasTree2(root1.right, root2.right)
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 n1 = TreeNode(8 ) n2 = TreeNode(8 ) n3 = TreeNode(7 ) n4 = TreeNode(9 ) n5 = TreeNode(2 ) n6 = TreeNode(4 ) n7 = TreeNode(7 ) n8 = TreeNode(8 ) n9 = TreeNode(9 ) n10 = TreeNode(2 ) n1.left = n2 n1.right = n3 n2.left = n4 n2.right = n5 n5.left = n6 n6.right = n7 print_tree(n1) n8.left = n9 n8.right = n10 print_tree(n8) hasSubtree(n1, n8)
1 2 3 4 8 8 7 9 2 4 7 8 9 2 True
NO.27 二叉树的镜像
问题描述 ：输入一棵二叉树，输出它的镜像。思路 ：递归。优点 ：思路清晰。时间复杂度 ：$O(n)$
1 2 3 4 5 6 def mirrorRecursively (root ): if root is None : return root.right, root.left = root.left, root.right mirrorRecursively(root.right) mirrorRecursively(root.left)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 n1 = TreeNode(8 ) n2 = TreeNode(6 ) n3 = TreeNode(10 ) n4 = TreeNode(5 ) n5 = TreeNode(7 ) n6 = TreeNode(9 ) n7 = TreeNode(11 ) n1.left = n2 n1.right = n3 n2.left = n4 n2.right = n5 n3.left = n6 n3.right = n7 print_tree(n1) mirrorRecursively(n1) print_tree(n1)
1 2 8 6 10 5 7 9 11 8 10 6 11 9 7 5
NO.28 对称的二叉树
问题描述 ：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。思路 ：递归。优点 ：思路清晰。时间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 10 11 def isTreeSymmetrical (root ): return isTwoTreeSymmetrical(root, root) def isTwoTreeSymmetrical (root1, root2 ): if root1 is None and root2 is None : return True if root1 is None or root2 is None : return False if root1.val != root2.val: return False return isTwoTreeSymmetrical(root1.left, root2.right) and isTwoTreeSymmetrical(root1.right, root2.left)
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 n1 = TreeNode(8 ) n2 = TreeNode(6 ) n3 = TreeNode(6 ) n4 = TreeNode(5 ) n5 = TreeNode(7 ) n6 = TreeNode(7 ) n7 = TreeNode(5 ) n1.left = n2 n1.right = n3 n2.left = n4 n2.right = n5 n3.left = n6 n3.right = n7 print_tree(n1) print (isTreeSymmetrical(n1))n3.val = 9 print_tree(n1) print (isTreeSymmetrical(n1))n3.val = 6 n3.right = None print_tree(n1) print (isTreeSymmetrical(n1))
1 2 3 4 5 6 8 6 6 5 7 7 5 True 8 6 9 5 7 7 5 False 8 6 6 5 7 7 False
NO.29 顺时针打印矩阵
问题描述 ：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。思路 ：此题没有复杂的思路，只需需注意每一步的条件判断，简单但易错。
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 def PrintMatrixClockwisely (numbers, columns, rows ): if not numbers or columns <= 0 or rows <= 0 : return start = 0 while columns > start * 2 and rows > start * 2 : PrintMatrixInCircle(numbers, columns, rows, start); start += 1 def PrintMatrixInCircle (numbers, columns, rows, start ): endX = columns - 1 - start endY = rows - 1 - start for i in range (start, endX+1 ): number = numbers[start][i] print (number, end=" " ) if start < endY: for i in range (start+1 , endY+1 ): number = numbers[i][endX] print (number, end=" " ) if start < endX and start < endY: for i in range (endX-1 , start-1 , -1 ): number = numbers[endY][i] print (number, end=" " ) if start < endX and start < endY - 1 : for i in range (endY-1 , start, -1 ): number = numbers[i][start] print (number, end=" " )
1 2 3 numbers = [[1 ,2 ,3 ,4 ],[5 ,6 ,7 ,8 ],[9 ,10 ,11 ,12 ],[13 ,14 ,15 ,16 ]] c = r = 4 PrintMatrixClockwisely(numbers, c, r)
1 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
NO.30 包含min函数的栈
问题描述 ：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O（1）。思路 ：设置辅助栈，和当前栈保持一致的形状，保存栈在某状态下的最小值。优点 ：空间换时间。时间复杂度 ：$O(1)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class MinStack : def __init__ (self ): self .min_stack = [] self .data_stack = [] def push (self, value ): if len (self .min_stack) == 0 or self .min_stack[-1 ] > value: self .min_stack.append(value) else : self .min_stack.append(self .min_stack[-1 ]) self .data_stack.append(value) def pop (self ): assert len (self .min_stack) > 0 and len (self .data_stack) > 0 self .min_stack.pop() return self .data_stack.pop() def min_val (self ): assert len (self .min_stack) > 0 and len (self .data_stack) > 0 return self .min_stack[-1 ]
1 2 3 4 5 6 7 ms = MinStack() ms.push(3 ) ms.push(2 ) ms.push(1 ) print (ms.min_val())ms.pop() print (ms.min_val())
NO.31 栈的压入、弹出序列
问题描述 ：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）思路 ：使用一个栈模拟压入和弹出的过程。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def IsPopOrder (pushV, popV ): stack = [] i = 0 for one_pop in popV: if len (stack) >0 and stack[-1 ] == one_pop: stack.pop() else : while i < len (pushV) and one_pop != pushV[i]: stack.append(pushV[i]) i += 1 if i >= len (pushV): return False i += 1 return True
1 2 3 4 5 pushV = [1 ,2 ,3 ,4 ,5 ] popV = [4 ,3 ,5 ,1 ,2 ] IsPopOrder(pushV, popV)
NO.32 从上到下打印二叉树
问题描述 ：从上倒下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。思路 ：使用一个队列。扩展 ：广度优先遍历一个有向图也是基于队列实现，但广度优先遍历一般必须要查重，树则没有这个问题。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def printFromTopToBottom (root ): traverse = [] if root is None : print ("This is an empty tree!" ) return queue = [root] while len (queue) > 0 : node = queue.pop() traverse.append(node.val) if node.left: queue.insert(0 , node.left) if node.right: queue.insert(0 , node.right) print (" " .join([str (one) for one in traverse]))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 n1 = TreeNode(8 ) n2 = TreeNode(6 ) n3 = TreeNode(10 ) n4 = TreeNode(5 ) n5 = TreeNode(7 ) n6 = TreeNode(9 ) n7 = TreeNode(11 ) n1.left = n2 n1.right = n3 n2.left = n4 n2.right = n5 n3.left = n6 n3.right = n7 printFromTopToBottom(n1)
变体 ：分行从上到下打印二叉树问题描述 ：从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。思路 ：增加一个行结束的标识符。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def printFromTopToBottomByLine (root ): traverse = [] line_end_token = "<END>" if root is None : print ("This is an empty tree!" ) return queue = [line_end_token, root] while len (queue) > 0 : node = queue.pop() if node == line_end_token: print (" " .join([str (one) for one in traverse])) traverse = [] continue traverse.append(node.val) if node.left: queue.insert(0 , node.left) if node.right: queue.insert(0 , node.right) if len (queue) > 0 and queue[-1 ] == line_end_token: queue.insert(0 , line_end_token)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 n1 = TreeNode(8 ) n2 = TreeNode(6 ) n3 = TreeNode(10 ) n4 = TreeNode(5 ) n5 = TreeNode(7 ) n6 = TreeNode(9 ) n7 = TreeNode(11 ) n1.left = n2 n1.right = n3 n2.left = n4 n2.right = n5 n3.left = n6 n3.right = n7 printFromTopToBottomByLine(n1)
变体 ：之字形 打印二叉树问题描述 ：请实现一个函数按照之字形顺序打印二叉树。即第一行按照从左到右的顺序打印，第二行按照从右到左的顺序打印，第三行按照从左到右的顺序打印，以此类推。思路 ：用两个栈实现。
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 printFromTopToBottomByLineWithZHI (root ): """用两个栈实现之字形层次遍历""" traverse = [] if root is None : print ("This is an empty tree!" ) return cur_stack, son_stack = [root], [] is_left_to_right = True while len (cur_stack) > 0 : node = cur_stack.pop() traverse.append(node.val) if is_left_to_right: if node.left: son_stack.append(node.left) if node.right: son_stack.append(node.right) else : if node.right: son_stack.append(node.right) if node.left: son_stack.append(node.left) if len (cur_stack) == 0 : print (" " .join([str (one) for one in traverse])) traverse = [] cur_stack, son_stack = son_stack, [] is_left_to_right = not is_left_to_right
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 n1 = TreeNode(8 ) n2 = TreeNode(6 ) n3 = TreeNode(10 ) n4 = TreeNode(5 ) n5 = TreeNode(7 ) n6 = TreeNode(9 ) n7 = TreeNode(11 ) n1.left = n2 n1.right = n3 n2.left = n4 n2.right = n5 n3.left = n6 n3.right = n7 printFromTopToBottomByLineWithZHI(n1)
NO.33 二叉搜索树的后序遍历序列
问题描述 ：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。思路 ：后序遍历即左右根，搜索树满足：左<根<右。递归地判断是否满足条件。
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 VarifySequenceOfBST (seq ): return vs_core(seq, 0 , len (seq) - 1 ) def vs_core (seq, s, e ): if len (seq) == 0 : return False if len (seq) == 1 : return True root = seq[e] i = s while i < e and seq[i] < root: i += 1 if i == e: return True left_e = i - 1 while i < e: if seq[i] < root: return False i += 1 is_left = True is_right = True if left_e >= s: is_left = vs_core(seq, s, left_e) if left_e + 1 < e: is_right = vs_core(seq, left_e+1 , e-1 ) return is_left and is_right
1 2 3 seq = [7 ,4 ,6 ,5 ] VarifySequenceOfBST(seq)
NO.34 二叉树中和为某一值的路径
问题描述 ：输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。思路 ：这道题是树状搜索最基础的原型。也可以理解成是回溯法 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def FindPath (root, exp_sum ): if not root: return path = [] cur_sum = 0 FindPathCore(root, exp_sum, path, cur_sum) def FindPathCore (root, exp_sum, path, cur_sum ): cur_sum += root.val path.append(root.val) is_leaf = root.left is None and root.right is None if cur_sum == exp_sum and is_leaf: print (" " .join(map (str , path))) if root.left is not None : FindPathCore(root.left, exp_sum, path, cur_sum) if root.right is not None : FindPathCore(root.right, exp_sum, path, cur_sum) path.pop()
1 2 3 4 5 6 7 8 9 10 n1 = TreeNode(10 ) n2 = TreeNode(5 ) n3 = TreeNode(12 ) n4 = TreeNode(4 ) n5 = TreeNode(7 ) n1.left = n2 n1.right = n3 n2.left = n4 n2.right = n5 FindPath(n1, 22 )
NO.35 复杂链表的复制
问题描述 ：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空。节点使用RandomListNode类）思路 ：普通：如果一个一个取复制，那么特殊指针必须遍历到才能复制，因此时间复杂度太高，是$O(n^2)$。优秀：1.将链表复制为AA’BB’这种形式；2.将A’B’之间的链接从AB的链表上复制过来；3.再将两个链表分离。优点 ：时间复杂度低。时间复杂度 ：$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 34 35 36 def cloneCompleteNodes (headNode ): cloneNodes(headNode) connectSiblingNodes(headNode) return reconnectNodes(headNode) def cloneNodes (headNode ): """将链表复制为AA'BB'这种形式""" curNode = headNode while curNode is not None : copyNode = RandomListNode(curNode.val) copyNode.next = curNode.next curNode.next = copyNode curNode = copyNode.next def connectSiblingNodes (headNode ): """将A'B'之间的链接从AB的链表上复制过来""" curNode = headNode while curNode is not None : copyNode = curNode.next if curNode.random is not None : copyNode.random = curNode.random.next curNode = copyNode.next def reconnectNodes (headNode ): """再将两个链表分离""" curNode = headNode if curNode is not None : cloneHead = copyNode = curNode.next curNode.next = copyNode.next curNode = curNode.next while curNode is not None : copyNode.next = curNode.next copyNode = copyNode.next curNode.next = copyNode.next curNode = curNode.next return cloneHead
1 2 3 4 5 6 7 8 9 10 11 12 n1 = RandomListNode(1 ) n2 = RandomListNode(2 ) n3 = RandomListNode(3 ) n1.next = n2 n2.next = n3 n1.random = n3 n2.random = n1 print_random_list(n1) n4 = cloneCompleteNodes(n1) print_random_list(n4)
1 2 3 4 5 6 val: 1, val of next: 2, val of random: 3 val: 2, val of next: 3, val of random: 1 val: 3, val of next: None, val of random: None val: 1, val of next: 2, val of random: 3 val: 2, val of next: 3, val of random: 1 val: 3, val of next: None, val of random: None
NO.36 二叉搜索树与双向链表
问题描述 ：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。思路 ：二叉搜索树有一个特性：中序遍历二叉搜索树是排序好的数据。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 def Convert (root ): last_node_in_list = [None ] ConvertNode(root, last_node_in_list) head_node_in_list = last_node_in_list[0 ] while head_node_in_list is not None and head_node_in_list.left is not None : head_node_in_list = head_node_in_list.left return head_node_in_list def ConvertNode (root, last_node_in_list ): if root is None : return cur = root if cur.left is not None : ConvertNode(cur.left, last_node_in_list) cur.left = last_node_in_list[0 ] if last_node_in_list[0 ] is not None : last_node_in_list[0 ].right = cur last_node_in_list[0 ] = cur if cur.right is not None : ConvertNode(cur.right, last_node_in_list)
1 2 3 4 5 6 7 8 9 10 11 12 13 n1 = TreeNode(10 ) n2 = TreeNode(5 ) n3 = TreeNode(12 ) n4 = TreeNode(4 ) n5 = TreeNode(7 ) n1.left = n2 n1.right = n3 n2.left = n4 n2.right = n5 head = Convert(n1) while head: print (head.val, end=" " ) head = head.right
.output n 1 2 3 4 5 6 7 [ { "name": "stdout", "output_type": "stream", "text": "4 5 7 10 12 " } ]
NO.37 序列化二叉树
问题描述 ：请实现两个函数，分别用来序列化和反序列化二叉树。思路 ：序列化：用前序遍历的顺序表示，并用一个特殊的符号如$表示空指针。
1 2 3 4 5 6 7 def serialize (root, s ): if root is None : return s + "$," s = s + str (root.val) + "," s = serialize(root.left, s) s = serialize(root.right, s) return s
1 2 3 4 5 6 7 8 9 10 11 12 13 14 n1 = TreeNode(1 ) n2 = TreeNode(2 ) n3 = TreeNode(3 ) n4 = TreeNode(4 ) n5 = TreeNode(5 ) n6 = TreeNode(6 ) n1.left = n2 n1.right = n3 n2.left = n4 n3.left = n5 n3.right = n6 print (serialize(n1, "" ))
1 1,2,4,$,$,$,3,5,$,$,6,$,$,
1 2 3 4 5 6 7 8 9 10 11 12 13 def deserialize (s ): return deserialize_core(s.split("," )) def deserialize_core (s ): if len (s) == 0 : return None , "" if s[0 ] == "$" : return None , s[1 :] node = TreeNode(s[0 ]) node.left, s = deserialize_core(s[1 :]) node.right, s = deserialize_core(s) return node, s
1 2 3 4 test_str = "1,2,4,$,$,$,3,5,$,$,6,$,$," root, s = deserialize(test_str) print (s)print_tree(root)
NO.38 字符串的排列
问题描述 ：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。思路 ：固定第一个，递归地求后面所有组合，然后将第一个字符和后面的元素互换，再做递归。空间复杂度 ：没有额外的浪费。
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 Permutation (ss ): res = [] if not ss or len (ss) == 0 : return res set_ = set () ss = list (ss) fun(set_, ss, 0 ) for one in set_: res.append(one) res = sorted (res) return re def fun (set_, ss, k ): if k == len (ss): set_.add('' .join(ss)) return for i in range (k, len (ss)): swap(ss, i, k) fun(set_, ss, k + 1 ) swap(ss, i, k) def swap (ss, i, j ): if i != j: t = ss[i] ss[i] = ss[j] ss[j] = t
1 ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
1 2 3 4 5 6 7 8 9 10 11 12 13 def Permutation2 (s ): """回溯""" space = list (s) res = [] PermutationCore("" , space, res) return res def PermutationCore (cur_str, space, res ): for one_char in space: next_space = [one for one in space if one != one_char ] if len (next_space) == 0 : res.append(cur_str + one_char) PermutationCore(cur_str + one_char, next_space, res)
1 ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
NO.39 数组中出现次数超过一半的数字
问题描述 ：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。思路 ：在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，并把次数设为1。优点 ：先排序的时间复杂度是$O(nlogn)$；这种方法的时间复杂度是$O(n)$，不需要改变原数组，额外的空间复杂度也是常数。时间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def MoreThanHalfNum1 (numbers, length ): result = numbers[0 ] times = 1 for i in range (length): if times == 0 : result = numbers[i] times = 1 elif numbers[i] == result: times += 1 else : times -= 1 return result;
1 2 l = [5 ,2 ,1 ,5 ,5 ,3 ,5 ,4 ,5 ] MoreThanHalfNum1(l, 9 )
思路 ：先做一个转化：数组中有一个数字出现的次数超过一半，那么排序之后，位于中间的数字，一定是这个数字，也就是中位数 。考虑到快排的partition 会返回调整完顺序后pivot的下标，如果返回的下标等于$n/2$，则说明是中位数就是这个数优点 ：利用了partition 函数的一个特性：返回的piviot的下标和最终排序好的数组中的下标是一样的。所以如果partion返回$n/2$，那么这个数一定是中位数。时间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def partition (data, s, e ): if s >= e: return small = s - 1 pivot_index = e pivot_value = data[pivot_index] for i in range (s, e): if data[i] < pivot_value: small += 1 if small != i: data[small], data[i] = data[i], data[small] small += 1 if small != e: data[small], data[e] = data[e], data[small] return small
1 2 3 data = [2 , 4 , 5 , 1 , 9 , 3 ] print (partition(data, 0 , 5 ))print (data)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def MoreThanHalfNum2 (numbers, length ): mid = length // 2 s = 0 e = length - 1 index = partrition(numbers, s, e) while index != mid: if index > mid: e = index - 1 index = partition(numbers, s, e) else : s = index + 1 index = partition(numbers, s, e) res = numbers[mid] return res
1 2 l = [5 ,2 ,1 ,5 ,5 ,3 ,5 ,4 ,5 ] MoreThanHalfNum2(l, 9 )
NO.40 最小的k个数
问题描述 ：输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。思路 ：类似上一题，使用partition 函数，直到返回的下标是k为止。优点 ：如果先排序，时间复杂度是$nlog(n)$，这里时间复杂度是$O(n)$。时间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def getLeastNumbers1 (data, k ): if len (data) <= k: return data s = 0 e = len (data) - 1 index = partition(data, s, e) while index != k - 1 : if index > k - 1 : e = index - 1 index = partition(data, s, e) else : s = index + 1 index = partition(data, s, e) return data[:k]
1 2 data = [10 , 8 , 2 , 3 , 4 , 5 , 7 , 1 , 6 ] getLeastNumbers1(data, 4 )
思路 ：使用一个数据结构（这里选择大顶堆），在遍历数据的时候保留最小的k个数。每次要获取k个数中最大的数，所以用大顶堆。大顶堆在插入和删除数据时的时间复杂度都是$O(logk)$。优点 ：更能应对海量数据的情况。时间复杂度 ：$O(nlogk)$
python自带heapq支持小顶堆。
核心文档，摘自https://docs.python.org/3.6/library/heapq.html
1 2 3 4 5 6 7 8 9 10 11 12 13 To create a heap, use a list initialized to [], or you can transform a populated list into a heap via function heapify(). The following functions are provided: heapq.heappush(heap, item) Push the value item onto the heap, maintaining the heap invariant. heapq.heappop(heap) Pop and return the smallest item from the heap, maintaining the heap invariant. If the heap is empty, IndexError is raised. To access the smallest item without popping it, use heap[0].
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import heapqdef getLeastNumbers2 (data, k ): h = [] for one in data: if len (h) < k: heapq.heappush(h, -one) else : v = heapq.heappop(h) if -one > v: heapq.heappush(h, -one) else : heapq.heappush(h, v) return [-one for one in h]
1 2 data = [10 , 8 , 2 , 3 , 4 , 5 , 7 , 1 , 6 ] getLeastNumbers2(data, 4 )
NO.41 数据流中的中位数
问题描述 ：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。思路 ：数据流意味着需要考虑新的数据进入时，数据结构的插入 的操作。
数据结构
插入的时间复杂度
得到中位数的时间复杂度
得到中位数的思路
没有排序的数组
$O(1)$
$O(n)$
参考no.39题，使用partition
排序的数组
$O(n)$
$O(1)$
直接通过下标获取
排序的链表
$O(n)$
$O(1)$
定义指向中位数的指针
二叉搜索树
平均$O(logn)$，最差$O(n)$
平均$O(logn)$，最差$O(n)$
节点中添加一个表示子树节点个数的字段
平衡二叉搜索树AVL
平均$O(logn)$
$O(1)$
将平衡因子从左右子树的高度差修改成左右子树的节点数目差
最大堆
$O(logn)$
$O(1)$
用一个最大堆和一个最小堆实现
详细 ：保证数据平均分配到两个堆中，二者数目差不能超过1。在总数是偶数时，插入最小堆，否则插入最大堆。另外需要保证最大堆中的所有数据都小于 最小堆中的数据。
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 import heapqclass DynamicArray : def __init__ (self ): self .max_heap = [] self .min_heap = [] def insert (self, val ): if (len (self .max_heap) + len (self .min_heap)) % 2 == 0 : heapq.heappush(self .min_heap, val) self .check() else : heapq.heappush(self .max_heap, -val) self .check() def check (self ): if len (self .min_heap) > 0 and len (self .max_heap) > 0 and self .min_heap[0 ] < -self .max_heap[0 ]: min_one = heapq.heappop(self .min_heap) max_one = -heapq.heappop(self .max_heap) heapq.heappush(self .min_heap, max_one) heapq.heappush(self .max_heap, -min_one) def get_median (self ): size = len (self .max_heap) + len (self .min_heap) if size == 0 : print ("No numbers are available!" ) exit(-1 ) median = 0 if size % 2 == 1 : median = self .min_heap[0 ] else : median = (self .min_heap[0 ] + (-self .max_heap[0 ])) / 2 return median
1 2 3 4 5 da = DynamicArray() data = [3 , 2 , 1 , 5 , 7 , 8 , 9 , 10 ] for i, one in enumerate (data): da.insert(one) print (data[:i+1 ], da.get_median())
1 2 3 4 5 6 7 8 [3] 3 [3, 2] 2.5 [3, 2, 1] 2 [3, 2, 1, 5] 2.5 [3, 2, 1, 5, 7] 3 [3, 2, 1, 5, 7, 8] 4.0 [3, 2, 1, 5, 7, 8, 9] 5 [3, 2, 1, 5, 7, 8, 9, 10] 6.0
NO.42 连续子数组的最大和
问题描述 ：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O（n）。思路 ：$$f(i) = \left{\begin{matrix}优点 ：时间复杂度低。时间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def findGreatestSumOfSubArray (data ): if len (data) == 0 : print ("Data is empty!!!" ) exit(-1 ) if len (data) == 1 : return data[0 ] max_sum_end_with_i = [0 for _ in range (len (data))] max_sum_end_with_i[0 ] = data[0 ] for i in range (1 , len (data)): if max_sum_end_with_i[i - 1 ] <= 0 : max_sum_end_with_i[i] = data[i] else : max_sum_end_with_i[i] = data[i] + max_sum_end_with_i[i-1 ] print (max_sum_end_with_i) return max (max_sum_end_with_i)
1 2 test_data = [1 , -2 , 3 , 10 , -4 , 7 , 2 , -5 ] print (findGreatestSumOfSubArray(test_data))
1 2 [1, -1, 3, 13, 9, 16, 18, 13] 18
NO.43 从1到n整数中1出现的次数
问题描述 ：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1思路 ：简单的可以计算每一个数中1出现的个数，再累加，这种方案的时间复杂度是$nlog(n)$。较优方案：从最高位开始统计1的个数，再递归。具体 ：将这个问题分解成3部分：1.最高位中1出现的次数；2.除了最高位以后，其他位中1出现的个数。这部分又分成两部分：2.1.最高位是小于当前最高位的时候，其他位数中，1的个数（排列组合）；2.2.最高位是当前最高位时，其他位数中1的个数（递归）。举例 ：求1到21345中1出现的次数。1.最高位中1出现了10000次；2.最高位是0或者1时，其他位中1出现的次数。选择后四位中其中一位是1，其他三位任意，是$2×(5-1)×10^3=1000$；3.2000021345除第一位之外的数位中1的数目，等同于11345中1的数目，使用递归。优点 ：递归的次数和位数相同，时间复杂度是$log(n)$。时间复杂度 ：$log(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 34 def numberOf1Between1AndN (n ): if n <= 0 : return 0 return numberOf1(str (n)) def numberOf1 (str_n ): if len (str_n) <= 0 or not str_n[0 ].isdigit(): return 0 first = int (str_n[0 ]) l = len (str_n) if l == 1 and first == 0 : return 0 if l == 1 and first > 0 : return 1 num_first_digit = 0 if first > 1 : num_first_digit = powerBase10(l - 1 ) elif first == 1 : num_first_digit = int (str_n[1 :]) + 1 num_other_digit = first * (l - 1 ) * powerBase10(l - 2 ) numRecursive = numberOf1(str_n[1 :]) return num_first_digit + num_other_digit + numRecursive def powerBase10 (n ): res = 1 for i in range (n): res *= 10 return res
1 numberOf1Between1AndN(12 )
NO.44 数字序列中某一位的数字
问题描述 ：数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。思路 ：简单思路：从1开始构建字符串，设置一个简单变量k保存当前的长度，直到k==n，停止遍历。计算m位数最多能到达的边界，确定第n位对应的数字是多少位，再确定n是什么数字。优点 ：时间复杂度是$log(n)$。时间复杂度 ：$log(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 def digitAtIndex (index ): if index < 0 : return -1 digits = 1 while True : numbers = countOfIntegers(digits) if index < numbers * digits: return digitAtIndexWithMDigits(index, digits) index -= numbers * digits digits += 1 def countOfIntegers (digits ): """输入1，返回0-9的个数10；输入2，返回10-99的个数90；输入3，返回100-999的个数900""" if digits == 1 : return 10 count = 9 * pow (10 , digits - 1 ) return count def digitAtIndexWithMDigits (index, digits ): """在直到index指向的数是m位数的前提下，返回index指向的数字""" number = beginNumber(digits) + index // digits indexFromRight = digits - index % digits for i in range (1 , indexFromRight): number = number // 10 return number % 10 def beginNumber (digits ): """返回m位数的第一个数""" if digits == 1 : return 0 return pow (10 , digits - 1 )
1 2 3 print (digitAtIndex(5 ))print (digitAtIndex(13 ))print (digitAtIndex(19 ))
NO.45 把数组排成最小的数
问题描述 ：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。思路 ：这道题可以看做是一种特殊的排序 ，核心在于如何实现比较 。给定数字m和n，比较函数需要确定m和n谁排在前面。根据题目要求，如果$mn<nm$，则应该是m排在n前面，也就是说m“小于”n。优点 ：时间复杂度跟排序一样。时间复杂度 ：采样快排，则为$nlog(n)$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def printMinNumber (numbers ): l = len (numbers) if l == 0 : return sorted_numbers = sorted (map (my_int, numbers)) return "" .join(map (str , sorted_numbers)) class my_int (int ): """Refer to https://softwareengineering.stackexchange.com/questions/151069/sorting-using-a-custom-definition-of-and-in-python""" def __lt__ (n, m ): return str (n) + str (m) < str (m) + str (n)
1 printMinNumber([3 , 32 , 321 ])
NO.46 把数字翻译成字符串
问题描述 ：给定一个数字，按照如下规则翻译成字符串：0翻译成“a”，1翻译成“b”…25翻译成“z”。一个数字有多种翻译可能，例如12258一共有5种，分别是bccfi，bwfi，bczi，mcfi，mzi。实现一个函数，用来计算一个数字有多少种不同的翻译方法。思路1 ：使用递归：定义$f(i)$表示从第i位数字开始的不同翻译的数目，$g(i,特点 ：思路清晰，但式子中的$f(i+1)$和$f(i+2)$明显有重复计算的部分。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def getTranslationCount1 (num_s ): count = 0 if len (num_s) == 0 : return 0 if len (num_s) == 1 : return 1 if num_s[0 ] == "1" or (num_s[0 ] == "2" and int (num_s[1 ]) < 6 ): if len (num_s) > 2 : return getTranslationCount1(num_s[1 :]) + getTranslationCount1(num_s[2 :]) else : return 2 else : return getTranslationCount1(num_s[1 :])
第一个测试样例：
第二个测试样例：
1 22 5 8 -> bwfi
1 2 25 8 -> bczi
12 2 5 8 -> mcfi
12 25 8 -> mzi
1 2 print (getTranslationCount1("22" )) print (getTranslationCount1("12258" ))
思路2 ：考虑从最小的问题自下而上地解决问题，类似动态规划思路。优点 ：避免思路1中大量的重复计算。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def getTranslationCount2 (num_s ): l = len (num_s) counts = [0 for _ in range (l)] for i in range (l - 1 , -1 , -1 ): count = 0 if i < l - 1 : count = counts[i+1 ] else : count = 1 if i < l - 1 : digit_1 = int (num_s[i]) digit_2 = int (num_s[i+1 ]) converted = digit_1 * 10 + digit_2 if converted >= 10 and converted <= 25 : if i < l - 2 : count += counts[i+2 ] else : count += 1 counts[i] = count return counts[0 ]
1 2 print (getTranslationCount2("22" )) print (getTranslationCount2("12258" ))
NO.47 礼物的最大价值
问题描述 ：在一个m*n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向左或者向下移动一格，知道到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计算你最多能拿多少价值的礼物？思路 ：这是一个典型的用动态规划 解决的问题。定义$f(i,j)$表示到达坐标$(i,j)$的格子能拿到的礼物的最大值。很明显：$f(i,j) = max(f(i,j-1), f(i-1, j)) + gift[i,j]$优点 ：思路清晰。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def getMaxValue1 (values, rows, cols ): if values is None or rows <= 0 or cols <= 0 : return 0 max_values = [[0 for _ in range (cols)] for _ in range (rows)] for i in range (rows): for j in range (cols): up = 0 left = 0 if i > 0 : up = max_values[i-1 ][j] if j > 0 : left = max_values[i][j-1 ] max_values[i][j] = values[i][j] + max (up, left) return max_values[rows-1 ][cols-1 ]
1 2 3 4 5 6 values = [[1 , 10 , 3 , 8 ], [12 , 2 , 9 , 6 ], [5 , 7 , 4 , 11 ], [3 , 7 , 16 , 5 ]] getMaxValue1(values, 4 , 4 )
思路 ：继续优化：每次计算$(i,j)$时只依赖$(i-1,j)$和$(i, j-1)$两个格子，因此第$i-2$行和更上面的所有格子的最优结果无需保存。因此可以用一个一维数组 来取代二维数组。在判断位置$(i,j)$时，一维数组前j个数字分别是$f(i,0),f(i,1),…,f(i, j-1)$（当前行已经更新的最佳结果），后面的数字是$f(i-1, j), f(i-1, j+1), …, f(i-1,cols-1)$（上一行的最佳结果）。优点 ：空间复杂度相对减少。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def getMaxValue2 (values, rows, cols ): if values is None or rows <= 0 or cols <= 0 : return 0 max_values = [0 for _ in range (cols)] for i in range (rows): for j in range (cols): up = 0 left = 0 if i > 0 : up = max_values[j] if j > 0 : left = max_values[j-1 ] max_values[j] = values[i][j] + max (up, left) return max_values[cols-1 ]
1 2 3 4 5 6 values = [[1 , 10 , 3 , 8 ], [12 , 2 , 9 , 6 ], [5 , 7 , 4 , 11 ], [3 , 7 , 16 , 5 ]] getMaxValue2(values, 4 , 4 )
NO.48 最长不含重复字符的子字符串
问题描述 ：请从字符串中找出一个最长的不包含重复字符串的子字符串，计算该最长子字符串的长度。假设字符串中只包含‘a’~‘z’的字符。例如，在字符串“arabcacfr”中，最长的不含重复字符的子字符串是“acfr”，长度是4。思路 ：动态规划，定义函数$f(i)$表示第$i$个字符为结尾的不包含重复子字符串的最长长度。如果第$i$个字符之前没有出现过，那么$f(i) = f(i-1) + 1$。如果出现过，则分为两种情况：记录$d$为第$i$个字符和它上次出现的位置之间的距离，如果$d\leq f(i-1)$，则$f(i)=d$；反之，仍有$f(i) = f(i-1) + 1$。优点 ：时间复杂度是$O(n)$，暴力法是$O(n^3)$。时间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def longestSubstringWithoutDuplication (string ): cur_len = 0 max_len = 0 position = [-1 for _ in range (26 )] for i in range (len (string)): prev_index = position[ord (string[i]) - ord ("a" )] if prev_index < 0 or i - prev_index > cur_len: cur_len += 1 else : if cur_len > max_len: max_len = cur_len cur_len = i - prev_index position[ord (string[i]) - ord ("a" )] = i if cur_len > max_len: max_len = cur_len return max_len
1 longestSubstringWithoutDuplication("arabcacfr" )
NO.49 丑数
问题描述 ：把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到大的顺序的第1500个丑数。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。思路1 ：逐个判断每个整数是不是丑数。优点 ：直观但不够高效。需要判断每个不是丑数的数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 def isUgly (number ): while number % 2 == 0 : number /= 2 while number % 3 == 0 : number /= 3 while number % 5 == 0 : number /= 5 return number == 1 def getUglyNumber1 (n ): if n <= 0 : return 0 number = 0 uglyFound = 0 while uglyFound < n: number += 1 if isUgly(number): uglyFound += 1 return number
1 2 3 4 import times = time.time() print (getUglyNumber1(500 ))print ("Time cost: " , time.time() - s)
1 2 937500 Time cost: 0.5277576446533203
思路2 ：创建数组保存已经找到的丑数，用空间换时间。假设已经有若干个排好序的丑数数组，并且最大的丑数记做$M$，下一个丑数必然是前面其中某一个丑数乘以2、3或者5的结果。第一个乘以2大于$M$的记为$M_2$，第一个乘以3大于$M$的记为$M_3$，第一个乘以5大于$M$的记为$M_5$。优点 ：不用计算不是丑数的数，用空间换时间。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 def getUglyNumber2 (n ): if n <= 0 : return 0 ugly_numbers = [0 for _ in range (n)] ugly_numbers[0 ] = 1 next_ugly_index = 1 mutiply_2_index = 0 mutiply_3_index = 0 mutiply_5_index = 0 while next_ugly_index < n: min_one = min (ugly_numbers[mutiply_2_index] * 2 , ugly_numbers[mutiply_3_index] * 3 , ugly_numbers[mutiply_5_index] * 5 ) ugly_numbers[next_ugly_index] = min_one while ugly_numbers[mutiply_2_index] * 2 <= min_one: mutiply_2_index += 1 while ugly_numbers[mutiply_3_index] * 3 <= min_one: mutiply_3_index += 1 while ugly_numbers[mutiply_5_index] * 5 <= min_one: mutiply_5_index += 1 next_ugly_index += 1 return ugly_numbers[-1 ]
1 2 3 4 import times = time.time() print (getUglyNumber2(500 ))print ("Time cost: " , time.time() - s)
1 2 937500 Time cost: 0.0006611347198486328
可以明显看到思路2的速度快很多，而且n越大，时间差距越明显。
NO.50 第一个只出现一次的字符
问题描述 ：在字符串中找出第一个只出现一次的字符。如输入“abaccdeff”，则输出‘b’。思路 ：优点 ：时间复杂度 ：
NO.51 数组中的逆序对
问题描述 ：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007。思路 ：优点 ：时间复杂度 ：
NO.52 两个链表的第一个公共节点
问题描述 ：输入两个链表，找出它们的第一个公共结点。思路 ：遍历两个链表，确定长度m和n，假设m>n，先走m-n步，再一起走，直到碰头。优点 ：时间复杂度低。时间复杂度 ：$O(m+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 def findFirstCommonNode (head1, head2 ): l1 = getListLength(head1) l2 = getListLength(head2) head_long = head1 if l1 > l2 else head2 head_short = head2 if l1 > l2 else head1 l_diff = l1 - l2 if l1 > l2 else l2 - l1 for i in range (l_diff): head_long = head_long.next while head_long is not None and head_short is not None and head_long != head_short: head_long = head_long.next head_short = head_short.next firstCommonNode = head_long return firstCommonNode def getListLength (head ): l = 0 while head is not None : l += 1 head = head.next return l
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 n1 = ListNode(1 ) n2 = ListNode(2 ) n3 = ListNode(3 ) n4 = ListNode(4 ) n5 = ListNode(5 ) n6 = ListNode(6 ) n7 = ListNode(7 ) n1.next = n2 n2.next = n3 n4.next = n5 n3.next = n6 n5.next = n6 n6.next = n7 print (findFirstCommonNode(n1, n4).val)
NO.53 在排序数组中查找数字
问题描述 ：统计一个数字在排序数组中出现的次数。如，输入排序数组{1,2,3,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4。思路 ：优点 ：时间复杂度 ：
NO.54 二叉搜索树的第k大节点
问题描述 ：给定一颗二叉搜索树，请找出其中的第k大的结点。思路 ：优点 ：时间复杂度 ：
NO.55 二叉树的深度
问题描述 ：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。思路 ：递归：一棵树的长度 = 1 (根节点) + max(左子树长度, 右子树长度)优点 ：简单清晰。
1 2 3 4 5 6 def treeDepth (root ): if root is None : return 0 n_left = treeDepth(root.left) n_right = treeDepth(root.right) return n_left + 1 if n_left > n_right else n_right + 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 n1 = TreeNode(8 ) n2 = TreeNode(6 ) n3 = TreeNode(10 ) n4 = TreeNode(5 ) n5 = TreeNode(7 ) n6 = TreeNode(9 ) n7 = TreeNode(11 ) n1.left = n2 n1.right = n3 n2.left = n4 n2.right = n5 n3.left = n6 n3.right = n7 print_tree(n1) print (treeDepth(n1))
相关：平衡二叉树
问题描述 ：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中的任意节点的左、右子树的深度相差不超过1，那么它就是一棵平衡二叉树。思路1 ：递归：使用上面的求深度函数，对每个节点的左右子树检查。优点 ：思路简单，但时间复杂度较高。
1 2 3 4 5 6 def isBalanced1 (root ): if root is None : return True n_left = treeDepth(root.left) n_right = treeDepth(root.right) return n_left - n_right <= 1 and n_left - n_right >= -1 and isBalanced1(root.left) and isBalanced1(root.right)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 n1 = TreeNode(8 ) n2 = TreeNode(6 ) n3 = TreeNode(10 ) n4 = TreeNode(5 ) n5 = TreeNode(7 ) n6 = TreeNode(9 ) n7 = TreeNode(11 ) n1.left = n2 n1.right = n3 n2.left = n4 n2.right = n5 n3.left = n6 n3.right = n7 print_tree(n1) isBalanced1(n1)
思路2 ：使用后续遍历 ，“左右根”的遍历方式可以确保在遍历到一个节点时，其左右子树都是遍历过的。这样只需在遍历的时候记录下当前检查节点的深度并返回即可。优点 ：只用遍历一次。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def isBalancedCore2 (root, depth_s ): if root is None : depth_s[0 ] = 0 return True left_ds = [0 ] right_ds = [0 ] if isBalancedCore2(root.left, left_ds) and isBalancedCore2(root.right, right_ds): diff = left_ds[0 ] - right_ds[0 ] if diff <= 1 and diff >= -1 : depth_s[0 ] = 1 + left_ds[0 ] if left_ds[0 ] > right_ds[0 ] else 1 + right_ds[0 ] return True return False def isBalanced2 (root ): return isBalancedCore2(root, [0 ])
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 n1 = TreeNode(8 ) n2 = TreeNode(6 ) n3 = TreeNode(10 ) n4 = TreeNode(5 ) n5 = TreeNode(7 ) n6 = TreeNode(9 ) n7 = TreeNode(11 ) n1.left = n2 n1.right = n3 n2.left = n4 n2.right = n5 n3.left = n6 n3.right = n7 print_tree(n1) isBalanced2(n1)
NO.56 数组中数字出现的次数
问题描述 ：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度$O(n)$，空间复杂度$O(1)$。思路 ：优点 ：时间复杂度 ：
NO.57 和为s的数字
问题描述 ：输入一个递增排序的数组和一个数字，在数组中查找两个数，使得他们的和正好是s，如果有多对数字的和等于s，则输出任意一对即可。思路 ：优点 ：时间复杂度 ：
NO.58 翻转字符串
问题描述 ：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。如，输入字符串“I am a student.”，则输出“student. a am I”。思路 ：优点 ：时间复杂度 ：
NO.59 队列的最大值
问题描述 ：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}，{2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}，{2,3,4,2,6,[2,5,1]}。思路 ：优点 ：时间复杂度 ：
NO.60 n个骰子的点数
问题描述 ：把n个骰子扔在地上，所有骰子朝上的一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。思路 ：优点 ：时间复杂度 ：
NO.61 扑克牌中的顺子
问题描述 ：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2~10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。思路 ：优点 ：时间复杂度 ：
NO.62 圆圈中最后剩下的数字
问题描述 ：题目： 0、1…n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。如0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。思路 ：优点 ：时间复杂度 ：
NO.63 股票的最大利润
问题描述 ：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可获得的最大利润是多少？例如，一只股票在某些时间节点的价格为{9,11,8,5,7,12,16,14}。如果我们能在价格为5的时候买入并在价格为16时卖出，则能获得最大的利润为11.思路 ：定义$diff(i)$代表卖出价是数组中第i个数字时，能获得的最大利润，那么最终的结果就是$\underset{i}{max} ;diff(i)$。而由于$diff(i)$可以在遍历时直接计算获得，所以不需要一个长度是n的数组保存所有的$diff(i)$，只需保存之前最大的$diff(i)$即可。优点 ：时间复杂度和空间复杂度都低。时间复杂度 ：$O(n)$
1 2 3 4 5 6 7 8 9 10 11 12 def maxDiff (numbers ): l = len (numbers) if l == 0 : return -1 max_diff = -99999999 min_buy = numbers[0 ] for i in range (1 , l): if numbers[i] - min_buy > max_diff: max_diff = numbers[i] - min_buy if numbers[i] < min_buy: min_buy = numbers[i] return max_diff
1 maxDiff([9 ,11 ,8 ,5 ,7 ,12 ,16 ,14 ])
NO.64 求1+2+…+n
问题描述 ：求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。思路 ：优点 ：时间复杂度 ：
NO.65 不用加减乘除做加法
问题描述 ：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。思路 ：优点 ：时间复杂度 ：
NO.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]。不能使用除法。思路 ：优点 ：时间复杂度 ：
NO.67 把字符串转换成整数
问题描述 ：将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0思路 ：优点 ：时间复杂度 ：
NO.68 树中两个结点的最低公共祖先
问题描述 ：输入两个树节点，求他们的最低公共祖先。
二叉树（二叉搜索树）：二叉搜索树是排序的，如果当前节点大于两个节点的值，去左子树中寻找；如果当前节点小于两个节点的值，去右子树中寻找；如果当前节点位于两个节点值之间，则该节点就是要寻找的最低公共祖先。
普通树（存在指向父节点的指针）：从给定节点出发，由父节点指针回到到根结点，形成链表。从而将问题转化为求两个链表的第一个公共节点的问题。
普通树（不存在指向父节点的指针）：利用两个辅助链表通过递归遍历的方法找到两条到达给定节点的路径，寻找两个链表最后一个公共节点，就是最低公共祖先。
思路 ：优点 ：时间复杂度 ：