剑指offer（一）

这几天开始刷牛客网上剑指offer的编程题，下面一系列博客将用python实现里面的编程题，很多参考了大神的思路（C实现），然后用python实现的。

二维数组查找

题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
6 14 22 26
8 16 24 30
10 20 30 40
输入10 ，返回True

思路
观察数组规律，从左下角元素开始找，如果目标值比它大，就查找下一列，比它小，就查找上一行。

代码实现

class Solution:
    # array 二维列表
    def Find(self, target, array):
        rows=len(array)-1
        cols=len(array[0])-1
        i=rows
        j=0
        while (j<=cols and i>=0):     #从左下角元素开始寻找
            if(target<array[i][j]):   #比左下角元素小，查找上一行
                i=i-1
            elif(target>array[i][j]): #比左下角元素大，查找下一列
                j=j+1
            else:
                return True
        return False

替换空格

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

思路
这题很简单，一个循环遍历加替换就行了，需要注意的最后需要把列表中的值转换为字符串输出。

代码实现

class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        s1=list(s)                  #转换成列表处理
        for i in range(len(s1)):
            if(s1[i]==' '):
                s1[i]='%20'
        return ''.join(s1)        #将列表元素以字符串形式输出

从尾到头打印链表

题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

思路
利用一个列表，不断的取链表结点，通过insert方法将元素前插到列表。

代码实现

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        result=[]                       #存储从尾到头输出的元素
        head = listNode                 #链表头结点
        while (head is not None):
            result.insert(0,head.val)   #将从头部取出的结点前插到列表中
            head=head.next              #指向下一个结点
        return result

重建二叉树

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

思路
因为先序遍历中，根节点是第一个被访问的，所以先序序列中的第一个结点就是根节点，然后根据该结点值在中序遍历中的位置，可以将中序遍历划分为左子树、根节点、右子树。最后结合先序遍历和中序遍历序列中左右子树下标递归即可。

代码实现

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, preorder, inorder):
        if not preorder or not inorder:
            return
        root = TreeNode(preorder[0])   #前序序列中的第一个元素为根节点
        i=inorder.index(preorder[0])   #根节点元素在中序序列中的位置，从而划分得到左子树和右子树中的元素
        root.left=self.reConstructBinaryTree(preorder[1:i+1],inorder[:i])    #递归重建左子树
        root.right=self.reConstructBinaryTree(preorder[i+1:],inorder[i+1:])  #递归重建右子树
        return root

两个栈实现队列

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

思路
队列符合先进先出规则。栈符合先进后出规则。
入队时：直接将元素压入stack1
出队时：若stack2为空，先将stack1中的元素出栈压入栈2，栈2在出栈

代码实现

class Solution:
    def __init__(self):
        self.stack1=[]
        self.stack2=[]
    def push(self, node):
        self.stack1.append(node)        #入队时，直接将元素压入栈1
    def pop(self):
        if self.stack2==[]:             #出队时，若栈2为空，先将栈1中的元素出栈压入栈2，栈2再出栈
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()
        return self.stack2.pop()

用2个队列实现一个栈呢？

思路
所有元素进入q1，因为我们的目的是栈，也就是最先出c,儿队是从队头开始出，所有先把ab出q1并入q2,此时目标c跑到了队头，出q1。此时q1已经为空，下一个要出的是b,把a从q2出队并进q1,此时目标b在q2队头,出队……..
即：把非空队列的n-1个压人空对列，剩的第n个出队…即总有一个队列为空。

代码实现

class StackWithTwoQueues(object):
    #定义两个空队列
    def __init__(self):
        self.queue1 = []
        self.queue2 = []
    #入栈
    def push(self, item):
        self.queue1.append(item)
    #出栈
    def pop(self):
        if len(self.queue1) == 0:
            return(None)
        while(len(self.queue1) != 1):
            self.queue2.append(self.queue1.pop(0))
        self.queue1, self.queue2 = self.queue2, self.queue1
        return (self.queue2.pop())