剑指offer 66编程题Python.pdf-资料库

剑指 offer 编程 66 题 Python 代码 1 题目描述：在一个二维数组中（每个一维数组的长度相同），每一行都按照从到右递增的顺序排列，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。解析：由于每行从左到右递增，每列从上到下递增，因此每列的最后一个元素最大；函数可以从每行的最后一个元素 A 开始判断，如果目标 B 大于 A，则从下一行最后一个元素开始判断，如果 B 小于 A，则往前移一列，从新列开始判断代码如下： class Solution: # array 二维列表 def Find(self, target, array): # write code here row = len(array) col = len(array[0]) j=0 i= col‐1 while j < row and i > ‐1: if array[j][i] > target: i‐=1 elif array[j][i] < targrt: j+=1 else: return 'ture' return 'false' 2 题目描述：请实现一个函数，将一个字符串中的每个空格替换成”%20”。例如，当字符串为 We Are Happy 则经过替换之后的字符串为 We%20Are%20Happy。解析：Python 中提供字符串替换函数 replace()函数，replace()方法的语法：str.replace(old, new[, max])，old 将被替换的子字符串， new 新字符串，用于替换 old 子字符串，max 可选字符串，替换不超过 max 次代码如下： class Solution: # s 源字符串 def replaceSpace(self, s): return s.replace(' ', '%20') # write code here 3 题目描述：输入一个链表，按链表值从尾到头的顺序返回一个 ArrayList。解析：将链表的每个值取出来然后存放到一个列表 ArrayList 中，对于 ArrayList 列表可以将其反置(Python 中提供 reverse()方法，用法是 List.reverse()，但该方法不返回值)；此外 Python 中还提供列表的插入函数 insert()函数，用法是 list.insert(index, obj)， index—对象 obj 需要插入的索引位置，同样该方法没有返回值，但会在列表指定位置插入对象。代码如下：(采用 insert()方法) # class ListNode: # def __init__(self, x):

# self.val = x # self.next = None class Solution: # 返回从尾部到头部的列表值序列，例如[1,2,3] def printListFromTailToHead(self, listNode): midArrayList = [] while listNode: midArrayList.insert(0, listNode.val) listNode = listNode.next return midArrayList # write code here 4 题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不包含重复的数字。例如输入前序遍历序列{1, 2, 4, 7, 3, 5, 6,8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，则重建二叉树并返回。解析：对于前序序列，第一个元素(如果存在)为根节点(1)，由于元素各不相同，则根据中序序列，可以判断出根节点的左子树的中序序列(4, 7,2)和右子树的中序序列(5, 3, 8, 6)，同时可以判断出根节点的左子树的前序序列(2, 4, 7) 和右子树的前序序列(3, 5, 6, 8)。因此可以根据递归重建该二叉树代码如下： # ‐*‐ coding:utf‐8 ‐*‐ # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # 返回构造的 TreeNode 根节点 def reConstructBinaryTree(self, pre, tin): if len(pre) == 0: return None elif len(pre) == 1: return TreeNode(pre[0]) else: treeNode = TreeNode(pre[0]) treeNode.left = self. reConstructBinaryTree(pre[1:tin.index(pre[0])+1], tin[:tin.index(pre[0])]) treeNode.right = self. reConstructBinaryTree(pre[tin.index(pre[0])+1:], tin[tin.index(pre[0])+1:]) return treeNode #write code here 5 题目描述：用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。队列中的元素为 int 类型。解析：栈 A 用来做入队列，栈 B 用来做出队列，当栈 B 为空时，栈 A 全部出栈到栈 B，栈

B 再出栈(即出队列) 代码如下： class Solution: def __init__(self): self.stackA = [] self.stackB = [] def push(self, node): self.stackA.append(node) def pop(self): if self.stackB: return self.stackB.pop() else: while self.stackA: self.stackB.append(self.stackA.pop()) return self.stackB.pop() 6.题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为 1。NOTE: 给出的所有元素都大于 0，若数组大小为 0，请返回 0. 解析：由于数组是两段不减的，因此，可以找出数组中第一个最小的值，将该值前面的所有元素移到数组的末尾即可。代码如下： class Solution: def minNumberInRotateArray(self, rotateArray): if len(rotateArray) == 0: return 0 else: min_value = min(rotateArray) min_index = rotateArray.index(min_value) newArray = rotateArray[min_index:] + rotateArray[:min_index] return newArray[0] # write code here 7.题目描述：大家都知道斐波那契数列，现在要求输入一个整数 n，请你输出斐波那契数列的第 n 项(从 0 开始，第 0 项为 0). n<=39 解析：斐波那契数列有一个很重要的性质，后面一项是前两项的和(n>=3),前两项都是 1，很容易想到用递归求解第 n 项的值，但是递归需要消耗更多的内存，因此可以使用动态规划，用两个变量分别保持上次的计算结果和上上次的计算结果代码如下： class Solution: def Fibonacci(self, n): a = 0 b = 1 if n <= 0:

return 0 else: for i in range(n): a, b = b, a + b return a # write code here 8. 题目描述：一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法(先后次序不同算不同的结果) 解析：由于青蛙一次只能跳一个台阶或者跳两个台阶，因此，我们可以考虑青蛙最后通过跳一步或者跳两步到最后的台阶，假设青蛙一步跳到最后的台阶，那么 f(n)和 f(n‐1)的跳法是一样多的；假如青蛙两步跳到最后的台阶，那么 f(n)和 f(n‐2)的跳法是一样的，故可以知道： f(n)=f(n‐1)+f(n‐2)的递推公式。代码如下： class Solution: def jumpFloor(self, number): a = 0 b = 1 if number == 0: return 0 else: for i in range(number): a, b = b, a + b return b # write code here 9 题目描述：一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级......它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。解析：考虑这样的一种情况，青蛙最后一跳跳到最后台阶，这样的每一跳都是一种独立的方法，因此，青蛙可以从 n‐1 台阶跳一次，也可以从 n‐2 台阶跳两次，依次类推，则每次跳的方案有 f(n‐1), f(n‐2), ... f(1)种，此时 f(n) = f(n‐1)+ f(n‐2) + f(n‐3) + ... + f(1)，可以推出 f(n) = 2f(n‐1). 代码如下： class Solution: def jumpFloorII(self, number): count = 1 for i in range(number ‐ 1): count = count * 2 return count # write code here 10 题目描述：我们可以用 2 * 1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2 * 1 的小矩形无重叠地覆盖一个 2 * n 的大矩形，总共用多少种方法？分析：对于矩形的覆盖，可以考虑最后的覆盖是横着还是竖着的小矩形，如果是竖着(占一列)，则有 f(n‐1)种覆盖方法，如果是横着(占两行)，则有 f(n‐2) 种覆盖方法，因此一共有 f(n) = f(n‐1) + f(n‐2)种覆盖方法。代码如下：

class Solution: def rectCover(self, number): if number == 0: return 0 a = 1 b = 1 for i in range(number): a, b = b, a + b return a # write code here 11 题目描述：输入一个整数，输出该数二进制表示中 1 的个数。其中负数用补码表示。解析：在 Python 中 int 型整数是用 32 位二进制代码存储的，负数按照补码的形式存储的，因此可以将该整数的 32 位二进制代码，一位一位的与 1 做‘&’运算，运算结果的和便是 1 的个数代码如下： class Solution: def NumberOf1(self, n): count = 0 for i in range(32): count = count + ((n >> i) & 1) # ‘+’的运算级比’&’ 高，切记加上’()’ return count 12 题目描述：给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent。求 base 的 exponent 次方。解析：Python 中有计算次方的运算符 ’**’，因此直接使用即可。如果不使用’**’运算符，那么需要判断 exponent 正负以及是否为 0，对于 exponent 的正负，只需要是正的情况，记其结果为 result，负的情况直接 1.0/result 即可计算；此外还需要判断 base 是否为 0 代码如下： class Solution: def Power(self, base, exponent): result = 1 if base == 0: return 0 if exponent == 0: return 1 else: for i in range(abs(exponent)): result = base * result if exponent > 0: return result else: return 1.0/result # write code here 13 题目描述：输入一个整数数组，实现一个函数来调用该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶

数之间的相对位置不变。解析：可以遍历整个数组，将奇数和偶数分别放在不同的列表中，最后，再合并两个列表。代码如下： class Solution: def reOrderArray(self, array): odd_numbers = [] even_numbers = [] for i in array: if i % 2 == 1: odd_numbers.append(i) else: even_numbers.append(i) return odd_numbers + even_numbers # write code here 14 题目描述：输入一个链表，输出该链表中倒数第 k 个结点。解析：由于是链表，则可以将链表中的每一个元素保存到列表中，在列表中寻找倒数第 k 个元素。代码如下: class Solution: def FindKthToTail(self, head, k): t = [] while head: t.append(head) head = head.next if k > len(t) or k < 1: return None return t[‐k] 15 题目描述：输入一个链表，反转链表后，输出新链表的表头。解析：可以将链表的每一个结点取出来，插入到新的链表表头，同时要保存原链表的下一个结点。代码如下： # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回 ListNode last = None def ReverseList(self, pHead): if pHead == None: return pHead last = None while pHead: temp = pHead.next

pHead.next = last last = pHead pHead = temp return last 16 题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。解析：从头开始比较两个链表元素的大小，将元素小的结点插入到新的链表中，直到一个链表为空。这可以有两种方法，一种是递归实现，一种是非递归代码如下：递归： # 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 pMergedHead = None if pHead1.val < pHead2.val: pMergedHead = pHead1 pMergedHead.next = self.Merge(pHead1.next, pHead2) else: pMergedHead = pHead2 pMergedHead.next = self.Merge(pHead1, pHead2.next) return pMergedHead # write code here 非递归： # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回合并后列表 def Merge(self, pHead1, pHead2): # write code here mergeHead = ListNode(90) p = mergeHead while pHead1 and pHead2: if pHead1.val >= pHead2.val:

mergeHead.next = pHead2 pHead2 = pHead2.next else: mergeHead.next = pHead1 pHead1 = pHead1.next mergeHead = mergeHead.next if pHead1: mergeHead.next = pHead1 elif pHead2: mergeHead.next = pHead2 return p.next 17 题目描述：输入两颗二叉树 A，B，判断 B 是不是 A 的子结构(PS：我们约定空树不是任意一个树的子结构) 解析：从 A 的判断根节点(约定和 B 的根节点开始判断的 A 结点称为判断根节点)和 B 开始匹配，如果根节点一样，则分别判断左子树和右子树，重复上述过程，如果 B 为空则匹配，如果 A 为空，或者两者的值不相等，则匹配不成功。代码如下： # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def HasSubtree(self, pRoot1, pRoot2): if not pRoot1 or not pRoot2: return False return self.is_subtree(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2) def is_subtree(self, A, B): if not B: return True elif not A or A.val != B.val: return False else: return self.is_subtree(A.left,B.left) and self.is_subtree(A.right, B.right) # write code here 18 题目描述：操作给的定的二叉树，将其变换为源二叉树的镜像。

资料库

剑指offer 66编程题Python.pdf

相关推荐

课程资源

热门标签

最新资料