剑指offer(1)-前20道面试题

本文为剑指offer中的所有面试题，参考了网上很多的代码，代码全部亲测有效。

所有的代码为python实现。

所有的题目都是按照剑指offer上的顺序。

github地址

面试题3:数组中重复的数字

题目一:找出数组中重复的数字

在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。

解法:因为列表总共有n个元素，所有元素可能取到的元素有0~n-1，共n种。如果不存在重复的数字，那么排序后数字i将会出现在下标为i的位置。现在让我们重新扫描数组，当扫描到下标为i的数字时，首先比较这个数字(记为m)与i是否相等： 如果是，继续扫描下一个元素，如果不是，则再拿它与第m个数字比较： 如果它和第m个数字相同，就找到了一个重复的元素；如果不同，就将m与第i个数字互换。接下来继续重头开始，重复换这个比较。

def findDuplicates(lisA): i = 0 while i < len(lisA) and lisA != []: m = lisA[i] if m == i: i += 1 else: if m == lisA[m]: print('找到一个重复的元素:%d' % m) break else: temp = lisA[i] lisA[i] = lisA[m] lisA[m] = temp i = 0 findDuplicates([2,3,1,0,2,5,3]) 找到一个重复的元素:2

题目二:不修改数组找出重复的数字

在一个长度为n+1的数组里的所有数字都在1~n范围内，所以数字中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或者3。

避免使用O(n)的辅助空间。我们把取值空间[1,n]从中间的数字m分为两部分，前面一部分为1_{m，后面一部分为m+1}n。如果数组中元素落在前面一部分的元素个数多于m个，那么数组中重复的元素一定落在前半区间；否则，数组中重复的元素一定落在后半区间。然后，我们可以继续将包含重复元素的区间一分为二，直到找到一个重复的元素。

def findDuplicates(lisA): # 找到重复元素，返回True；否则，返回False low = 1 high = len(lisA) - 1 while low <= high: mid = (low + high) // 2 #统计数组中落在前半部分区间中的元素的个数 count_low = 0 for i in lisA: if i in range(low, mid + 1): count_low += 1 #判断落在长度为1的区间中的数组元素个数 if high == low: if count_low > 1: #如果大于1，则找到重复的元素 return low else: break #比较前半部分区间长度与落在该区间内元素的个数，决定将前半部分/后半部分区间继续一分为二 if count_low > (mid - low + 1): high = mid else: low = mid + 1 return False findDuplicates([2,3,5,4,3,2,6,7]) 3

面试题4:二维数组中的查找

题目:在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样一个二维数组和一个整数，判断数组中是否含有该整数。

从右上开始查找：如果数组中的数比这个整数大，向左移动一位，如果数组中的数比这个数小，向下移动一位。

class Solution: # array 二维列表 def Find(self, target, array): if array == []: return False # 行数 num_row = len(array) # 列数 num_col = len(array[0]) # 从右上角开始，也就是从最后一列开始 i = num_col - 1 j = 0 while i >= 0 and j < num_row: # 删除整列 if array[j][i] > target: i -= 1 # 删除整行 elif array[j][i] < target: j += 1 else: return True so=Solution() lis=[[1,2,8,9], [2,4,9,12], [4,7,10,13], [6,8,11,15]] target=15 so.Find(target,lis) True

面试题5:替换空格

题目:请实现一个函数，把字符串中的每个空格替换成“%20”。例如，输入"We Are Happy."，则经过替换之后的字符串为"We%20Are%20Happy."

1.先计算最终需要给出的长度，然后建立两个指针p1,p2，p1指向原始字符串的末尾，p2指向替换后的字符串的末尾。同时移动p1,p2, 将p1指的内容逐个复制到p2, 当p1遇到空格时，在p2处插入 %20， p1向前移动一个位置，p2向前移动3个位置，当p1和p2位置重合时，全部替换完成。

2.python中可以利用append() [O(1)]，新建list，一次遍历，碰到空格就添加 %20，否则就添加原始字符串s内容。

# 实现的是1 # 时间复杂度o(n) class Solution: # s 源字符串 def replaceSpace(self, s): # 如果不是字符串或者为空串 if not isinstance(s, str) or len(s) <= 0 or s == None: return '' spaceNum = 0 for i in s: if i == " ": spaceNum += 1 print("空格的个数", spaceNum) # 总共的长度 newStrLen = len(s) + spaceNum * 2 # 新串的列表 newStr = newStrLen * [None] indexOfOriginal, indexOfNew = len(s) - 1, newStrLen - 1 while indexOfNew >= 0 and indexOfOriginal <= indexOfNew: if s[indexOfOriginal] == ' ': newStr[indexOfNew - 2:indexOfNew + 1] = ['%', '2', '0'] indexOfNew -= 3 indexOfOriginal -= 1 else: newStr[indexOfNew] = s[indexOfOriginal] indexOfNew -= 1 indexOfOriginal -= 1 return ''.join(newStr) so=Solution() so.replaceSpace("We are happy.") 空格的个数 2 'We%20are%20happy.'

面试题6:从尾到头打印链表

题目:输入一个链表的头结点，从尾到头反过来打印每个节点的值。

从头到尾遍历链表，并用一个栈存储每个节点的值，之后出栈输出，用insert()，一直在index=0的位置插入遍历的值。

class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: # 返回从尾部到头部的列表值序列，例如[1,2,3] def printListFromTailToHead(self, listNode): # write code here if not listNode: return [] result = [] while listNode: # 也可以把它放入栈中 result.insert(0, listNode.val) listNode = listNode.next return result llist1 = ListNode(1) pnode = llist1 for i in range(2, 11): pnode.next = ListNode(i) pnode = pnode.next so = Solution() so.printListFromTailToHead(llist1) [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] # 使用递归的方法 result = [] def printListFromTailToHead1(head): if head is None: return printListFromTailToHead1(head.next) result.append(head.val) return result printListFromTailToHead1(llist1) [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

题目7:重建二叉树

题目:输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

利用二叉树前序遍历和中序遍历的特点，前序遍历的第一个值一定为根节点，对应于中序遍历中间的一个点，在中序遍历中，该点左侧的值为根节点的左子树，右侧的值为根节点的右子树。这时可以利用递归，取前序遍历的[1:i+1]和中序遍历的[:i]作为对应的左子树继续上一个过程，取前序遍历的[i+1:]和中序遍历的[i+1:]对应与右子树继续上一个过程，重建二叉树。

class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: # 返回构造的TreeNode根节点 def reConstructBinaryTree(self, pre, tin): if not pre and not tin: return None root = TreeNode(pre[0]) if set(pre) != set(tin): return None i = tin.index(pre[0]) root.left = self.reConstructBinaryTree(pre[1:i + 1], tin[:i]) root.right = self.reConstructBinaryTree(pre[i + 1:], tin[i + 1:]) return root # 按行打印二叉树 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 so = Solution() root = so.reConstructBinaryTree([1, 2, 4, 7, 3, 5, 6, 8], [4, 7, 2, 1, 5, 3, 8, 6]) so.Print(root) [[1], [2, 3], [4, 5, 6], [7, 8]]

面试题8:二叉树的下一个结点

题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None self.next = None class Solution: def GetNext(self, pNode): if pNode is None: return pNext = None if pNode.right: pNode = pNode.right while pNode.left: pNode = pNode.left pNext = pNode else: if pNode.next and pNode.next.left == pNode: pNext = pNode.next elif pNode.next and pNode.next.right == pNode: pNode = pNode.next while pNode.next and pNode.next.right == pNode: pNode = pNode.next # 遍历终止时当前节点有父节点, 说明当前节点是父节点的左子节点, 输入节点的下一个结点为当前节点的父节点 # 反之终止时当前节点没有父节点, 说明当前节点在位于根节点的右子树, 没有下一个结点 if pNode.next: pNext = pNode.next return pNext pNode1 = TreeNode(8) pNode2 = TreeNode(6) pNode3 = TreeNode(10) pNode4 = TreeNode(5) pNode5 = TreeNode(7) pNode6 = TreeNode(9) pNode7 = TreeNode(11) pNode1.left = pNode2 pNode1.right = pNode3 pNode2.left = pNode4 pNode2.right = pNode5 pNode3.left = pNode6 pNode3.right = pNode7 so=Solution() pNext=so.GetNext(pNode2) pNext.val 7

面试题9:用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

class Solution: def __init__(self): self.stack1 = [] self.stack2 = [] def push(self, node): self.stack1.append(node) def pop(self): if len(self.stack1) == 0 and len(self.stack2) == 0: return elif len(self.stack2) == 0: while len(self.stack1) > 0: self.stack2.append(self.stack1.pop()) return self.stack2.pop() so=Solution() so.push(122) so.push(300) so.push(400) so.pop() 122 so.pop() 300 so.pop() 400

面试题10:斐波那契数列

题目一：求斐波那契数列的第n项

class Solution: def Fibonacci(self, n): tempArray = [0,1] if n >= 2: for i in range(2, n+1): tempArray[i%2] = tempArray[0] + tempArray[1] return tempArray[n%2] so=Solution() so.Fibonacci(4) 3

题目二：青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法？

class Solution: def jumpFloor(self,number): tempArray=[1,2] if number >=3: for i in range(3,number+1): tempArray[(i+1)%2]=tempArray[0]+tempArray[1] return tempArray[(number+1)%2] so=Solution() so.jumpFloor(4) 5

面试11:旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

class Solution: def minNumberInRotateArray(self, rotateArray): if len(rotateArray) == 0: return 0 front = 0 rear = len(rotateArray) - 1 minVal = rotateArray[0] if rotateArray[front] < rotateArray[rear]: return rotateArray[front] else: while (rear - front) > 1: mid = (front + rear) // 2 if rotateArray[mid] >= rotateArray[front]: front = mid elif rotateArray[mid] <= rotateArray[rear]: rear = mid elif rotateArray[front] == rotateArray[rear] == rotateArray[mid]: for i in range(1, len(rotateArray)): if rotateArray[i] < minVal: minVal = rotateArray[i] rear = i minVal = rotateArray[rear] return minVal so=Solution() so.minNumberInRotateArray([3,4,5,1,2]) 1 so.minNumberInRotateArray([3,4,5,1,2,2,2,2,2,2]) 1 so.minNumberInRotateArray([3,4]) 3 so.minNumberInRotateArray([1,1,1,0,0,0,1,1,1,1,1]) 0 so.minNumberInRotateArray([1,1,1,3,1,1,1,1]) 1

面试12:矩阵中的路径

题目:请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

class Solution: def hasPath(self, matrix, rows, cols, path): assistMatrix = [True] * rows * cols for i in range(rows): for j in range(cols): if (self.hasPathAtAStartPoint(matrix, rows, cols, i, j, path, assistMatrix)): return True return False def hasPathAtAStartPoint(self, matrix, rows, cols, i, j, path, assistMatrix): if not path: return True index = i * cols + j if i < 0 or i >= rows or j < 0 or j >= cols or matrix[index] != path[ 0] or assistMatrix[index] == False: return False assistMatrix[index] = False if (self.hasPathAtAStartPoint(matrix, rows, cols, i + 1, j, path[1:], assistMatrix) or self.hasPathAtAStartPoint(matrix, rows, cols, i - 1, j, path[1:], assistMatrix) or self.hasPathAtAStartPoint(matrix, rows, cols, i, j - 1, path[1:], assistMatrix) or self.hasPathAtAStartPoint(matrix, rows, cols, i, j + 1, path[1:], assistMatrix)): return True assistMatrix[index] = True return False matrix="abtgcfcsjdeh" path="bfce" so=Solution() so.hasPath(matrix,3,4,path) True

面试13:机器人的运动范围

题目:地上有一个m行和n列的方格。一个机器人从坐标(0,0)的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

class Solution: def judge(self, threshold, i, j): if sum(map(int, str(i) + str(j))) <= threshold: return True else: return False def findgrid(self, threshold, rows, cols, matrix, i, j): count = 0 if i < rows and j < cols and i >= 0 and j >= 0 and self.judge( threshold, i, j) and matrix[i][j] == 0: matrix[i][j] = 1 count = 1 + self.findgrid(threshold, rows, cols, matrix, i, j+1) \ + self.findgrid(threshold, rows, cols, matrix, i, j-1) \ + self.findgrid(threshold, rows, cols, matrix, i+1, j) \ + self.findgrid(threshold, rows, cols, matrix, i-1, j) return count def movingCount(self, threshold, rows, cols): # write code here matrix = [[0 for i in range(cols)] for j in range(rows)] count = self.findgrid(threshold, rows, cols, matrix, 0, 0) print(matrix) return count so=Solution() so.movingCount(7,4,5) [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]] 20

面试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.

class Solution(): def maxProfuctAfterCutting(self,length): if length == 0: return 0 if length == 1: return 0 if length == 2: return 1 if length == 3: return 2 if length == 4: return 4 result = [0,1,2,3] for i in range(4,length+1): max = 0 for j in range(1,i//2+1): temp = result[j] * result[i-j] if temp > max: max = temp result.append(max) return result[length] so=Solution() so.maxProfuctAfterCutting(8) 18

面试15:二进制中1的个数

题目:输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

class Solution: def NumberOf1(self, n): count = 0 if n < 0: n = n & 0xffffffff while n != 0: count += 1 n = (n - 1) & n return count so=Solution() so.NumberOf1(9) 2

面试16:数值的整数次方

题目:给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。不考虑大数的情况

class Solution: def Power(self, base, exponent): try: ret = self.power_value(base, abs(exponent)) if exponent < 0: return 1.0 / ret except ZeroDivisionError: print('Error: base is zero') else: return ret def power_value(self,base, exponent): if exponent == 0: return 1 if exponent == 1: return base ret = self.power_value(base, exponent >> 1) ret *= ret if exponent & 1 == 1: ret *= base return ret so=Solution() so.Power(2,300) 2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397376

面试17:打印1到最大的n位数

题目:输入数字n，按顺序打印出从1最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数即999.

注：在Python中整数类型默认包含大整数，即无论输入多大整数，都能够自动进行相关加减乘除的运算

class Solution: def print1ToMaxN(self,n): if n <= 0: return number = ['0' for i in range(n)] for i in range(10): number[0] = str(i) self.print2ToMaxNrecursively(number, n, 0) def print2ToMaxNrecursively(self,number, length, index): if index == length - 1: self.printNumber(number) return for i in range(10): number[index + 1] = str(i) print2ToMaxNrecursively(number, length, index + 1) def printNumber(self,number) : begin = len(number) for i in range(len(number)): if number[i] != '0': begin = i break print(''.join(number[begin:])) so=Solution() so.print1ToMaxN(1) 1 2 3 4 5 6 7 8 9

面试18:删除链表的节点

题目一：在O(1)时间内删除链表结点

如果要删除的节点后面有节点，则将该节点内容复制到要删除的节点，并删除该节点。

如果要删除的节点在链表头部，直接删除该节点。

如果要删除的节点在链尾，遍历至该节点删除。

class ListNode: def __init__(self, x=None): self.val =x self.next = None class Solution: def delete_node(self, head, node_to_del): if head is None or node_to_del is None: return head if node_to_del.next is not None: next_node=node_to_del.next node_to_del.val=next_node.val node_to_del.next=next_node.next elif head==node_to_del: del (node_to_del) else: node=head while node is not None: if node.next==node_to_del: break node=node.next node.next=node_to_del.next del(node_to_del) node1= ListNode(1) node2= ListNode(2) node3= ListNode(3) node4= ListNode(4) node5= ListNode(5) node6= ListNode(6) node7= ListNode(7) node1.next=node2 node2.next=node3 node3.next=node4 node4.next=node5 node5.next=node6 node6.next=node7 so=Solution() so.delete_node(node1,node3) while node1: print(node1.val) node1=node1.next 1 2 4 5 6 7

题目二:删除链表中重复的结点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def deleteDuplication(self, pHead): if pHead is None or pHead.next is None: return pHead first = ListNode(-1) first.next = pHead last = first while pHead and pHead.next: if pHead.val == pHead.next.val: val = pHead.val while pHead and val == pHead.val: pHead = pHead.next last.next = pHead else: last = pHead pHead = pHead.next return first.next node1= ListNode(1) node2= ListNode(2) node3= ListNode(3) node4= ListNode(3) node5= ListNode(4) node6= ListNode(4) node7= ListNode(5) node1.next=node2 node2.next=node3 node3.next=node4 node4.next=node5 node5.next=node6 node6.next=node7 so=Solution() head=so.deleteDuplication(node1) while head: print(head.val) head=head.next 1 2 5

面试19:正则表达式匹配

题目：请实现一个函数用来匹配包括’.‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"aba"均不匹配

class Solution: # s, pattern都是字符串 def match(self, s, pattern): # 如果s与pattern都为空，则True if len(s) == 0 and len(pattern) == 0: return True # 如果s不为空，而pattern为空，则False elif len(s) != 0 and len(pattern) == 0: return False # 如果s为空，而pattern不为空，则需要判断 elif len(s) == 0 and len(pattern) != 0: # pattern中的第二个字符为*，则pattern后移两位继续比较 if len(pattern) > 1 and pattern[1] == '*': return self.match(s, pattern[2:]) else: return False # s与pattern都不为空的情况 else: # pattern的第二个字符为*的情况 if len(pattern) > 1 and pattern[1] == '*': # s与pattern的第一个元素不同，则s不变，pattern后移两位，相当于pattern前两位当成空 if s[0] != pattern[0] and pattern[0] != '.': return self.match(s, pattern[2:]) else: # 如果s[0]与pattern[0]相同，且pattern[1]为*，这个时候有三种情况 # pattern后移2个，s不变；相当于把pattern前两位当成空，匹配后面的 # pattern后移2个，s后移1个；相当于pattern前两位与s[0]匹配 # pattern不变，s后移1个；相当于pattern前两位，与s中的多位进行匹配，因为*可以匹配多位 return self.match(s, pattern[2:]) or self.match( s[1:], pattern[2:]) or self.match(s[1:], pattern) # pattern第二个字符不为*的情况 else: if s[0] == pattern[0] or pattern[0] == '.': return self.match(s[1:], pattern[1:]) else: return False so=Solution() so.match("aaa","a.a") True so.match("aaa","ab*ac*a") True so.match("aaa","aa.a") False

面试20:表示数值的字符串

题目:请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”±5”和”12e+4.3”都不是。

class Solution: # s字符串 def isNumeric(self, s): # write code here if len(s) <= 0: return False # 分别标记是否出现过正负号、小数点、e，因为这几个需要特殊考虑 has_sign = False has_point = False has_e = False for i in range(len(s)): # 对于e的情况 if s[i] == 'E' or s[i] == 'e': # 不同出现两个e if has_e: return False # e不能出现在最后面，因为e后面要接数字 else: has_e = True if i == len(s) - 1: return False # 对于符号位的情况 elif s[i] == '+' or s[i] == '-': # 如果前面已经出现过了符号位，那么这个符号位，必须是跟在e后面的 if has_sign: if s[i - 1] != 'e' and s[i - 1] != 'E': return False # 如果这是第一次出现符号位，而且出现的位置不是字符串第一个位置，那么就只能出现在e后面 else: has_sign = True if i > 0 and s[i - 1] != 'e' and s[i - 1] != 'E': return False # 对于小数点的情况 elif s[i] == '.': # 小数点不能出现两次；而且如果已经出现过e了，那么就不能再出现小数点，因为e后面只能是整数 if has_point or has_e: return False # 如果是第一次出现小数点，如果前面出现过e，那么还是不能出现小数点 else: has_point = True if i > 0 and (s[i - 1] == 'e' or s[i - 1] == 'E'): return False else: # 其他字符必须是‘0’到‘9’之间的 if s[i] < '0' or s[i] > '9': return False return True so=Solution() so.isNumeric("+10.9992") True so.isNumeric("+10e") False so.isNumeric("+10e6") True so.isNumeric("+10e-6") True so.isNumeric("0") True so.isNumeric("+10e-6.23") False

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