牛客网剑指offer编程实践1-10题
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
解答：
方法1：遍历整个二维数组，判断数组中是否含有该整数
方法2：从二维数组的左下角tag开始判断，如果目标整数大于tag，tag右移，如果目标整数小于tag，tag上移。如果相等返回True
class Solution: # array 二维列表 def Find(self, target, array): for i in array: if target in i: return True return False def Find(self, target, array): raw = len(array) col = len(array[0]) i = raw - 1 j = 0 while i >= 0 and j < col: if array[i][j] < target: j += 1 elif array[i][j] > target: i -= 1 else: return True return False请实现一个函数，将一个字符串中的每个空格替换成 。例如，当字符串为We Are Happy.则经过替换之后的字符串为We Are Happy。
解答：
方法1：将字符串s变换成list，将list中的空格替换成“ ”，然后将list转换成字符串输出。缺点：不是原来的字符串s
方法2：先遍历以便字符串s，判断有多少个空格，然后从后往前开始替换。
# -*- coding:utf-8 -*- class Solution: # s 源字符串 def replaceSpace(self, s): # write code here s = list(s) for i in range(len(s)): if s[i] == ' ': s[i] = ' ' return ''.join(s)输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。注意：自定义的listNode函数不能直接使用len()，使用while listNode:
解答：
方法1：使用一个栈，遍历链表进行进栈，然后出栈到ArrayList
方法2：遍历链表到list，然后利用list[::-1]进行输出
# -*- coding:utf-8 -*- # 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 listNode is None: return [] tmp = [] while listNode: tmp.append(listNode.val) listNode = listNode.next return tmp[::-1]输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
解答：
方法：根据前序遍历第一个元素找到根节点，然后在中序遍历中找到根节点的index，index左边的为根节点的左子树，index右边的为根节点的右子树。然后在两个遍历中截取两个子树进行迭代
注意：要返回二叉树，而不是数组，
# -*- 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): # write code here if len(pre) == 0: return None else: root = TreeNode(pre[0]) tag = tin.index(pre[0]) root.left = self.reConstructBinaryTree(pre[1:tag+1],tin[0:tag]) root.right = self.reConstructBinaryTree(pre[tag+1:],tin[tag+1:]) return root1、用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
解答：
方法：队列的Push操作就是一个栈A的进栈
队列的Pop操作，判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；如果不为空，栈B直接出栈。
# -*- coding:utf-8 -*- class Solution: def __init__(self): self.stack0 = [] self.stack1 = [] def push(self, node): # write code here return self.stack0.append(node) def pop(self): # return xx #出队：判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；如果不为空，栈B直接出栈。 if self.stack1 == []: while self.stack0: self.stack1.append(self.stack0.pop()) return self.stack1.pop()2、用两个队列实现一个栈的功能？要求给出算法和思路！
方法：
入栈：将元素进队列A
出栈：判断队列A中元素的个数是否为1，如果等于1，则出队列，否则将队列A中的元素以此出队列并放入队列B，直到队列A中的元素留下一个，然后队列A出队列，再把队列B中的元素出队列以此放入队列A中。
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
解答：
方法1：遍历整个数组找到最小的元素。
方法2：因为是非递减数组旋转，利用二分法进行判断，
如果array[mid] > array[0]，则最小元素在mid的右边。找到的第一个小于array[mid]的元素即最小元素
如果array[mid] < array[0]，则最小元素在mid的左边。找到的第一个大于array[mid]的元素，它的后一个元素即为最小元素
注意数组为0，返回0。
# -*- coding:utf-8 -*- class Solution: def minNumberInRotateArray(self, rotateArray): # write code here if len(rotateArray) == 0: return 0 tmp = rotateArray[0] for i in rotateArray: if i < tmp: tmp = i return tmp #时间复杂度为O(lgn)，二分法 def minNumberInRotateArray(self, rotateArray): # write code here if len(rotateArray) == 0: return 0 mid = int((len(rotateArray) - 1) / 2) if rotateArray[mid] >= rotateArray[0]: for i in rotateArray[mid:]: if i < rotateArray[mid]: return i else: for i in reversed(range(mid)): if rotateArray[i] > rotateArray[mid]: return rotateArray[i + 1]大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
解答：
方法：动态规划，一次的结果之和上两个数相关
# -*- coding:utf-8 -*- class Solution: def Fibonacci(self, n): # write code here if n == 0: return 0 elif n == 1: return 1 elif n == 2: return 1 else: tag = [] tag.append(1) tag.append(1) for i in range(2,n): tag.append(tag[i-1]+tag[i-2]) return tag[n-1] #从0开始，第0项为0，如果从第一项开始，则为while n > 1: def Fibonacci(self, n): f = 0 s = 1 while n: s = f + s f = s - f n -= 1 return f一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
解答：
方法：
a.如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);
b.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)
c.由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)
d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2
e.可以发现最终得出的是一个斐波那契数列：
# -*- coding:utf-8 -*- class Solution: def jumpFloor(self, number): # write code here if number == 1: return 1 elif number == 2: return 2 else: tag = [] tag.append(1) tag.append(2) for i in range(2, number): tag.append(tag[i - 1] + tag[i - 2]) return tag[number-1] def jumpFloor(self, number): f = 1 s = 2 while number > 1: s = f + s f = s - f number -= 1 return f一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解答：
方法1：f(1) = 1
f(2) = f(2-1) + f(2-2) f(2-2)表示一次跳2级台阶
f(3) = f(3-1) + f(3-2) +f(3-3)
f(n) = f(n-1) +…+ f(n-(n-1)) + f(n-n)
= f(0) + f(1) +…+f(n-1)
f(n-1) = f(0) + f(1) +…+f(n-2)
f(n) = 2*f(n-1)
方法2：每个台阶都有跳与不跳两种情况（除了最后一个台阶），最后一个台阶必须跳。所以共用2^(n-1)中情况
# -*- coding:utf-8 -*- class Solution: def jumpFloorII(self, number): # write code here return 2**(number-1) def jumpFloorII(self, number): if number <= 0: return -1 elif number == 1: return 1 return 2*self.jumpFloorII(number-1)我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
解答:
方法：同上面的斐波那契数列，只是f(1) = 1,f(2) = 2
# -*- coding:utf-8 -*- class Solution: def rectCover(self, number): # write code here if number == 0: return 0 if number == 1: return 1 elif number == 2: return 2 else: tag = [] tag.append(1) tag.append(2) for i in range(2, number): tag.append(tag[i - 1] + tag[i - 2]) return tag[-1] def rectCover(self, number): if number == 0: return 0 elif number == 1: return 1 elif number == 2: return 2 f = 1 s = 2 while number > 1: s = s + f f = s - f number -= 1 return f