最近想刷一下《剑指offer》，准备使用python语言完成【刚好巩固一下之前学过的python基础语法】
刷题的网站是牛客网，牛客的这个《剑指offer》的题库跟LeetCode的提交方式很像，跟之前刷过的PAT的提交方式有一定的差别
刚开始使用python，还需要很多学习的地方
暂时将题目与提交的代码记录在下：
二维数组中的查找
题目描述：
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
for i in range(len(array)):
for j in range(len(array[0])):
if array[i][j]==target:
return True
return False
这个题直接使用暴力遍历的方法就AC了，虽然时间复杂度很高，但是比较好写，正确的做法应该是从矩阵的右上角开始遍历，如果要查的数字比其大，删除其所在的行，下移，要是比其小，删除其所在的列，左移。
替换空格
题目描述：
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
class Solution:
def replaceSpace(self, s):
s=s.replace(" ","%20")##使用字符串的replace函数将旧的字符替换为新的字符
return s
直接使用replace函数即可
从尾到头打印链表
题目描述：
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
#从尾到头打印链表
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
def printListFromTailToHead(self, listNode):
ls=[]#定义一个反转后的链表
p=listNode#记录listNode的头指针
while(p):
ls.insert(0,p.val)
p=p.next
return ls
重建二叉树
题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if not pre or not tin:
return None
root=TreeNode(pre[0])#定义根节点
position=tin.index(root.val)#检索根节点在中序遍历里的位置
root.left=self.reConstructBinaryTree(pre[1:position+1],tin[0:position])
#左子树等于递归调用该函数，传入的参数为左子树的前序遍历与中序遍历
root.right=self.reConstructBinaryTree(pre[position+1:],tin[position+1:])
#右子树等于递归调用该函数，传入的参数为右子树的前序遍历与中序遍历
return root
#本题中掌握两个知识点，一个是序列类型的切片[i:j:k]返回的是从i开始，j结束（！不包含j），步长为k的子序列
#类中函数要调用自身的函数需要对self对象进行.fun()操作才能调用，self类似于C++中的this
树与图的很多操作都需要使用递归的函数思想，以后做题要常常学会写递归
用两个栈实现队列
题目描述：
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
# -*- coding:utf-8 -*-
class Solution:
#对该类进行初始化
def __init__(self):
self.stack1=[]
self.stack2=[]
#在这里对self的所有成员进行定义
#初始化函数不能return
def push(self, node):
# write code here
self.stack1.append(node)
def pop(self):
# return xx
if not self.stack1 and not self.stack2:#如果两个栈都为空，则返回空
return []
elif not self.stack2 :#如果仅仅第二个栈为空，将第一个栈的元素弹到第二个栈
while(self.stack1):
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
else:
return self.stack2.pop()
python写其实pop函数可以直接pop(0)弹出首位的元素，但是这样没法使用两个栈，不能达到考察要求