剑指offer(2)-第20-40道面试题

面试21:调整数组顺序使奇数位于偶数前面

题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分

class Solution: def reOrderArray(self, array): return sorted(array,key=lambda c:c%2,reverse=True) so=Solution() so.reOrderArray([1,2,3,4,5,6,7,8]) [1, 3, 5, 7, 2, 4, 6, 8]

采用两指针分别从首尾出发，当头指针遇到一个偶数，并且尾指针遇到一个奇数时，交换两指针的数字，直到两指针相遇。时间复杂度为 O(n)，(类似于快排)

class Solution: def reOrderArray(self, array): n = len(array) head = 0 tail = n - 1 while head < tail: while array[head] % 2 != 0: head += 1 while array[tail] % 2 == 0: tail -= 1 array[head], array[tail] = array[tail], array[head] head += 1 tail -= 1 so=Solution() array=[1,2,3,4,5,6,7,8] so.reOrderArray(array) array [1, 7, 3, 5, 4, 6, 2, 8]

面试22:链表中倒数第k个结点

题目：输入一个链表，输出该链表中倒数第k个结点。

class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def FindKthToTail(self, head, k): # write code here if head == None or k <= 0: return None pAhead = head pBhead = None for i in range(k-1): if pAhead.next != None: pAhead = pAhead.next else: return None pBhead = head while pAhead.next != None: pAhead = pAhead.next pBhead = pBhead.next return pBhead llist1 = ListNode(1) pnode = llist1 for i in range(2, 11): pnode.next = ListNode(i) pnode = pnode.next so=Solution() so.FindKthToTail(llist1,3).val 8

面试23:链表中环的入口结点

题目：一个链表中包含环，请找出该链表的环的入口结点。

class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def EntryNodeOfLoop(self, pHead): meetNode = self.MeetNode(pHead) if not meetNode: return None loop = 1 flag = meetNode while flag.next != meetNode: loop += 1 flag = flag.next fast = pHead for i in range(loop): fast = fast.next slow = pHead while fast != slow: fast = fast.next slow = slow.next return fast def MeetNode(self, head): if not head: return None slow = head.next if slow == None: return None fast = slow.next while fast: if slow == fast: return slow slow = slow.next fast = fast.next.next node1= ListNode(1) node2= ListNode(2) node3= ListNode(3) node4= ListNode(4) node5= ListNode(5) node1.next=node2 node2.next=node3 node3.next=node4 node4.next=node5 node5.next=node2 so=Solution() head=so.EntryNodeOfLoop(node1) print(head.val) 2

面试24:反转链表

题目：输入一个链表，输出反转后的链表。

class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: # 返回ListNode def ReverseList(self, pHead): # write code here pReversedHead = None pNode = pHead pPrev = None while pNode != None: pNext = pNode.next if pNext == None: pReversedHead = pNode pNode.next = pPrev pPrev = pNode pNode = pNext return pReversedHead llist1 = ListNode(1) pnode = llist1 for i in range(2, 11): pnode.next = ListNode(i) pnode = pnode.next so = Solution() head=so.ReverseList(llist1) while head: print(head.val) head=head.next 10 9 8 7 6 5 4 3 2 1

面试25:合并两个排序的链表

题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: # 返回合并后列表 def Merge(self, pHead1, pHead2): if pHead1 == None: return pHead2 if pHead2 == None: return pHead1 pMergeHead = None if pHead1.val < pHead2.val: pMergeHead = pHead1 pMergeHead.next = self.Merge(pHead1.next,pHead2) else: pMergeHead = pHead2 pMergeHead.next = self.Merge(pHead1,pHead2.next) return pMergeHead llist1 = ListNode(1) pnode1 = llist1 for i in range(2, 11): pnode1.next = ListNode(i) pnode1 = pnode1.next llist2 = ListNode(5) pnode2 = llist2 for i in range(6, 11): pnode2.next = ListNode(i) pnode2 = pnode2.next so=Solution() head=so.Merge(llist1,llist2) while head: print(head.val) head=head.next 1 2 3 4 5 5 6 6 7 7 8 8 9 9 10 10

面试26:树的子结构

题目：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def HasSubtree(self, pRoot1, pRoot2): result = False if pRoot1 != None and pRoot2 != None: if pRoot1.val == pRoot2.val: result = self.DoesTree1haveTree2(pRoot1,pRoot2) if not result: result = self.HasSubtree(pRoot1.left,pRoot2) if not result: result = self.HasSubtree(pRoot1.right,pRoot2) return result def DoesTree1haveTree2(self,pRoot1,pRoot2): if pRoot2 == None: return True if pRoot1 == None: return False if pRoot1.val != pRoot2.val: return False return self.DoesTree1haveTree2(pRoot1.left, pRoot2.left) and self.DoesTree1haveTree2(pRoot1.right, pRoot2.right) Root = TreeNode(5) Root.left = TreeNode(3) Root.left.left = TreeNode(2) Root.left.right = TreeNode(4) Root.right = TreeNode(7) Root.right.left = TreeNode(6) Root.right.right = TreeNode(8) so=Solution() so.HasSubtree(Root,Root.right) True

面试27:二叉树的镜像

题目:操作给定的二叉树，将其变换为源二叉树的镜像。

class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: # 返回镜像树的根节点 def Mirror(self, root): if root == None: return if root.left == None and root.right == None: return root ptemp = root.left root.left = root.right root.right = ptemp self.Mirror(root.left) self.Mirror(root.right) # 按行打印二叉树 def Print(self, pRoot): if pRoot is None: return [] nodes, res = [pRoot], [] while nodes: curStack, nextStack = [], [] for node in nodes: curStack.append(node.val) if node.left: nextStack.append(node.left) if node.right: nextStack.append(node.right) res.append(curStack) nodes = nextStack return res Root = TreeNode(5) Root.left = TreeNode(3) Root.left.left = TreeNode(2) Root.left.right = TreeNode(4) Root.right = TreeNode(7) Root.right.left = TreeNode(6) Root.right.right = TreeNode(8) so=Solution() print(so.Print(Root)) so.Mirror(Root) so.Print(Root) [[5], [3, 7], [2, 4, 6, 8]] [[5], [7, 3], [8, 6, 4, 2]]

面试28:对称的二叉树

题目：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def isSymmetrical(self, pRoot): return self.selfIsSym(pRoot,pRoot) def selfIsSym(self,root1,root2): if root1 == root2 and root2 == None: return True if root1 == None or root2 == None: return False if root1.val != root2.val: return False return self.selfIsSym(root1.left, root2.right) and self.selfIsSym(root1.right,root2.left) Root = TreeNode(5) Root.left = TreeNode(3) Root.left.left = TreeNode(2) Root.left.right = TreeNode(4) Root.right = TreeNode(3) Root.right.left = TreeNode(4) Root.right.right = TreeNode(2) so=Solution() so.isSymmetrical(Root) True

面试29:顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

class Solution: # matrix类型为二维列表，需要返回列表 def printMatrix(self, matrix): if not matrix: return [] rows = len(matrix) columns = len(matrix[0]) start = 0 result = [] while rows > start * 2 and columns > start * 2: self.PrintMatrixInCircle(matrix, columns, rows, start,result) start += 1 return result def PrintMatrixInCircle(self, matrix, columns, rows,start,result): endX = columns - 1 - start endY = rows - 1 - start # 从左到右打印一行 for i in range(start, endX+1): #number = matrix[start][i] result.append(matrix[start][i]) # 从上到下打印一行 if start < endY: for i in range(start+1, endY+1): #number = matrix[i][endX] result.append(matrix[i][endX]) # 从右到左打印一行 if start < endX and start < endY: for i in range(endX-1, start-1, -1): #number = matrix[endY][i] result.append(matrix[endY][i]) # 从下到上打印一行 if start < endX and start < endY-1: for i in range(endY-1, start, -1): #number = matrix[i][start] result.append(matrix[i][start]) so=Solution() so.printMatrix([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]) [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]

面试30:包含main函数的栈

题目:定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

class Solution: def __init__(self): self.stack = [] self.minStack = [] def push(self, node): # write code here self.stack.append(node) if self.minStack == [] or node < self.min(): self.minStack.append(node) else: temp = self.min() self.minStack.append(temp) def pop(self): # write code here if self.stack == None or self.minStack == None: return None self.minStack.pop() self.stack.pop() def top(self): # write code here return self.stack[-1] def min(self): # write code here return self.minStack[-1] so=Solution() so.push(5) so.min() 5 so.push(1) so.min() 1

面试31:栈的压入、弹出序列

题目:输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 {1, 2, 3, 4, 5} 是某栈的压入序列，序列 {4, 5, 3, 2, 1} 是该压栈序列对应的一个弹出序列，但 {4, 3, 5, 1, 2} 就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

class Solution: def IsPopOrder(self, pushV, popV): # write code here if pushV == [] or popV == []: return False stack = [] for i in pushV: stack.append(i) while len(stack) and stack[-1] == popV[0]: stack.pop() popV.pop(0) if len(stack): return False else: return True so=Solution() so.IsPopOrder([1,2,3,4,5],[4,3,5,1,2]) False so.IsPopOrder([1,2,3,4,5],[4,5,3,2,1]) True

面试32:从上往下打印二叉树

题目一：不分行从上到下打印二叉树

class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: # 返回从上到下每个节点值列表，例：[1,2,3] def PrintFromTopToBottom(self, root): # write code here if root is None: return [] queue = [] result = [] queue.append(root) while len(queue) > 0: currentRoot = queue.pop(0) result.append(currentRoot.val) if currentRoot.left: queue.append(currentRoot.left) if currentRoot.right: queue.append(currentRoot.right) return result Root = TreeNode(5) Root.left = TreeNode(3) Root.left.left = TreeNode(2) Root.left.right = TreeNode(4) Root.right = TreeNode(7) Root.right.left = TreeNode(6) Root.right.right = TreeNode(8) so=Solution() so.PrintFromTopToBottom(Root) [5, 3, 7, 2, 4, 6, 8]

题目二：分行上到下打印二叉树

class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def Print(self, pRoot): # write code here if pRoot is None: return [] nodes,res = [pRoot],[] while nodes: curStack, nextStack = [],[] for node in nodes: curStack.append(node.val) if node.left: nextStack.append(node.left) if node.right: nextStack.append(node.right) res.append(curStack) nodes = nextStack return res Root = TreeNode(5) Root.left = TreeNode(3) Root.left.left = TreeNode(2) Root.left.right = TreeNode(4) Root.right = TreeNode(7) Root.right.left = TreeNode(6) Root.right.right = TreeNode(8) so=Solution() so.Print(Root) [[5], [3, 7], [2, 4, 6, 8]]

题目三：按之字形顺序打印二叉树

class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def Print(self, pRoot): # write code here if not pRoot: return [] result,nodes = [],[pRoot] right = True while nodes: curStack, nextStack = [],[] if right: for node in nodes: curStack.append(node.val) if node.left: nextStack.append(node.left) if node.right: nextStack.append(node.right) else: for node in nodes: curStack.append(node.val) if node.right: nextStack.append(node.right) if node.left: nextStack.append(node.left) nextStack.reverse() right = not right result.append(curStack) nodes = nextStack return result Root = TreeNode(5) Root.left = TreeNode(3) Root.left.left = TreeNode(2) Root.left.right = TreeNode(4) Root.right = TreeNode(7) Root.right.left = TreeNode(6) Root.right.right = TreeNode(8) so=Solution() so.Print(Root) [[5], [7, 3], [2, 4, 6, 8]]

面试33:二叉搜索树的后序遍历序列

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

class Solution: def VerifySquenceOfBST(self, sequence): # write code here if sequence == []: return False length = len(sequence) root = sequence[-1] for i in range(length): if sequence[i] > root: break for j in range(i, length): if sequence[j] < root: return False left = True if i > 0: left = self.VerifySquenceOfBST(sequence[:i]) right = True if j < length - 1: right = self.VerifySquenceOfBST(sequence[i:length-1]) return left and right so=Solution() so.VerifySquenceOfBST([5,7,6,9,11,10,8]) True

面试34:二叉树中和为某一值的路径

题目:输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: # 返回二维列表，内部每个列表表示找到的路径 def FindPath(self, root, expectNumber): # write code here if not root or root.val > expectNumber: return [] if not root.left and not root.right and root.val == expectNumber: return [[root.val]] else: expectNumber -= root.val left = self.FindPath(root.left,expectNumber) right = self.FindPath(root.right,expectNumber) result = [[root.val]+i for i in left] for i in right: result.append([root.val]+i) return sorted(result, key=lambda x:-len(x)) Root = TreeNode(5) Root.left = TreeNode(3) Root.left.left = TreeNode(2) Root.left.right = TreeNode(4) Root.right = TreeNode(7) Root.right.left = TreeNode(6) Root.right.right = TreeNode(8) so=Solution() so.FindPath(Root,10) [[5, 3, 2]]

面试35:复杂链表的复制

题目：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

class RandomListNode: def __init__(self, x): self.label = x self.next = None self.random = None class Solution: # 返回 RandomListNode def Clone(self, pHead): # write code here if not pHead: return None pNode = pHead while pNode: pClone = RandomListNode(pNode.label) pClone.next = pNode.next pNode.next = pClone pNode = pClone.next pNode = pHead while pNode: pClone = pNode.next if pNode.random != None: pClone.random = pNode.random.next pNode = pClone.next pNode = pHead pCloneHead = pCloneNode = pNode.next pNode.next = pCloneHead.next pNode = pNode.next while pNode: pCloneNode.next = pNode.next pCloneNode = pCloneNode.next pNode.next = pCloneNode.next pNode = pNode.next return pCloneHead

面试题36:二叉搜索树与双向链表

题目:输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def Convert(self, pRootOfTree): if not pRootOfTree: return None if not pRootOfTree.left and not pRootOfTree.right: return pRootOfTree self.Convert(pRootOfTree.left) left = pRootOfTree.left if left: while left.right: left = left.right pRootOfTree.left = left left.right = pRootOfTree self.Convert(pRootOfTree.right) right = pRootOfTree.right if right: while right.left: right = right.left pRootOfTree.right = right right.left = pRootOfTree while pRootOfTree.left: pRootOfTree = pRootOfTree.left return pRootOfTree Root = TreeNode(5) Root.left = TreeNode(3) Root.left.left = TreeNode(2) Root.left.right = TreeNode(4) Root.right = TreeNode(7) Root.right.left = TreeNode(6) Root.right.right = TreeNode(8) so=Solution() head=so.Convert(Root) while head: print(head.val) head=head.right 2 3 4 5 6 7 8

面试题37:序列化二叉树

题目:请实现两个函数，分别用来序列化和反序列化二叉树。

序列化二叉树：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串。需要注意的是，序列化二叉树的过程中，如果遇到空节点，需要以某种符号（这里用#）表示。以下图二叉树为例，序列化二叉树时，需要将空节点也存入字符串中。

反序列化二叉树：根据某种遍历顺序得到的序列化字符串，重构二叉树。具体思路是按前序遍历“根左右”的顺序，根节点位于其左右子节点的前面，即非空（#）的第一个节点是某子树的根节点，左右子节点在该根节点后，以空节点#为分隔符。

class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def __init__(self): self.flag = -1 def Serialize(self, root): if not root: return '#,' return str(root.val)+','+self.Serialize(root.left)+self.Serialize(root.right) def Deserialize(self, s): # write code here self.flag += 1 l = s.split(',') if self.flag >= len(s): return None root = None if l[self.flag] != '#': root = TreeNode(int(l[self.flag])) root.left = self.Deserialize(s) root.right = self.Deserialize(s) return root Root = TreeNode(5) Root.left = TreeNode(3) Root.left.left = TreeNode(2) Root.left.right = TreeNode(4) Root.right = TreeNode(7) Root.right.left = TreeNode(6) Root.right.right = TreeNode(8) so=Solution() s=so.Serialize(Root) print(s) so.Deserialize(s).val 5,3,2,#,#,4,#,#,7,6,#,#,8,#,#, 5

面试题38:字符串的排列

题目:输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

class Solution: def Permutation(self, ss): # write code here if not ss: return [] if len(ss) == 1: return list(ss) charList = list(ss) charList.sort() pStr = [] for i in range(0, len(charList)): if i > 0 and charList[i] == charList[i - 1]: continue temp = self.Permutation(''.join(charList[:i]) + ''.join(charList[i + 1:])) for j in temp: pStr.append(charList[i] + j) return pStr so=Solution() so.Permutation("abc") ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

面试题39:数组中出现次数超过一半的数字

题目:数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

class Solution: def MoreThanHalfNum_Solution(self, numbers): # write code here length = len(numbers) if not numbers: return 0 result = numbers[0] times = 1 for i in range(1, length): if times == 0: result = numbers[i] times = 1 elif numbers[i] == result: times += 1 else: times -= 1 if not self.CheckNoreThanHalf(numbers, length, result): return 0 return result def CheckNoreThanHalf(self, numbers, length, number): times = 0 for i in range(length): if numbers[i] == number: times += 1 if times * 2 <= length: return False return True so=Solution() so.MoreThanHalfNum_Solution([1,2,3,2,2,2,5,4,2]) 2

面试题40:最小的k个数

题目:输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

class Solution: def GetLeastNumbers_Solution(self, tinput, k): # write code here if not tinput or k > len(tinput): return [] tinput = self.quick_sort(tinput) return tinput[:k] def quick_sort(self, lst): if not lst: return [] pivot = lst[0] left = self.quick_sort([x for x in lst[1:] if x < pivot]) right = self.quick_sort([x for x in lst[1:] if x >= pivot]) return left + [pivot] + right so=Solution() so.GetLeastNumbers_Solution([4,5,1,6,2,7,3,8],4) [1, 2, 3, 4]

剑指offer(3)-第41-68道面试题