剑指offer编程题(python版)

校招准备ing

二维数组中的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：
数组特点，从左到右，从上到下均为递增，所以从最右上方第一个开始比较，如果大于这个数，数组下移，因为该行没有比目标值更大的数。从最左下方开始，思路一样。
代码：

class Solution:
    # array 二维列表
    def Find(self, target, array):
        rowcount = len(array)  # 获取行数
        colcount = len(array[0]) # 获取列数
        if colcount == 0:#这里要考虑到二维数组为空的情况，如[[]]
            return False
        for i in range(colcount-1,-1,-1): #起始为colcount-1行，末尾行为第0行，步长为-1
            if target > array[0][i]: #要查找的数字大于右上角的数字
                for j in range(rowcount): #下移比较
                    if target == array[j][i]: #找到，返回True
                        return True
            elif target == array[0][i]: #要查找的数字等于右上角的数字，返回True
                return True
            #否则上移
        return False

替换空格

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路：
考察字符串替换问题，如果是11替换就可以直接遍历，但是题目要求是13替换，即将” “替换为3个字符，那么字符串长度会发生变化。最好的办法是从字符串最末端进行替换。
代码：

## 第一次实现代码，不是最佳👌
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        old_s_list = list(s)
        new_s_list = []
        for i in old_s_list:
            if i == " ":
                new_s_list.append("%20")
            else: 
                new_s_list.append(i)
        return "".join(new_s_list)

从头到尾打印链表

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
思路：
将链表中的值记录到list之中，然后利用list语句[::-1]或者list(reversed(new_list) 翻转list
代码：

# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        new_list=[]
        while listNode:
            new_list.append(listNode.val)
            listNode=listNode.next
        return new_list[::-1]

重建二叉树

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

```

#### 用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
**思路：**
**代码：**