二维数组查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

重点：

  1. 数组为空
  2. 排好序
  3. 上面行的右边的数也可以比下面行左边的数大

顺序查找

    def Find(self, target, array):
        # write code here
        if len(array)==0 or len(array[0])==0:
            return 0
        l=0
        r=len(array[0])-1
        for i in range(len(array)):
            if array[i][0]<=target<=array[i][-1]:
                for j in range(len(array[i])):
                    if array[i][j]==target:
                        return True
        return False

二分查找

    def Find(self, target, array):
        # write code here
        if len(array)==0 or len(array[0])==0:
            return 0
       
        for i in range(len(array)):
            if array[i][0]<=target<=array[i][-1]:
                l=0
                r=len(array[0])-1
                while(l<=r):
                    mid=l+(r-l)//2
                    if array[i][mid]<target :
                        l=mid+1
                    elif array[i][mid]>target:
                        r=mid-1
                    else:
                        return True
                      
        return False

替换空格

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

直接替换

    def replaceSpace(self, s):
        # write code here
        return s.replace(" ","%20")

正则表达式

import re
class Solution:
    def replaceSpace(self, s):
        # write code here
        s=re.sub(r" ","%20",s)
        return s

从尾到头打印链表

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

简单列表保存

def printListFromTailToHead(self, listNode):
        # write code here
        res=[]
        while listNode:
            res.append(listNode.val)
            listNode=listNode.next
        return res[::-1]  #逆序打印

递归

    def printListFromTailToHead(self, listNode):
        res=[]
        def printListnode(listNode):
            # write code here
            if listNode:
                printListnode(listNode.next)#先递归到最后一层
                res.append(listNode.val)#添加值，退出函数，返回到上一层函数中的这行，继续添加值
        printListnode(listNode)
        return res

重建二叉树

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

思路：

递归并正确分割前序和中序序列
前序分割为左子树和右子树，左子树的开头是第二个数，中间包含节点的数量为中序从0到根节点的数量
所以是pre[1:tin.index(pre[0])+1]
右子树是剩下的部分

同理，中序左子树是从左边到根节点的部分，tin[:tin.index(pre[0])]

递归

     def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre)==0:
            return None
        if len(pre)==1:
            return TreeNode(pre[0])
        root=TreeNode(pre[0])
        tinL=tin[:tin.index(pre[0])]
        tinR=tin[tin.index(pre[0])+1:]
        root.left=self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tinL)
        root.right=self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tinR)
        return root

两个栈实现队列

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

思路：

一个栈入队列，一个栈出队列，当出队列为空时，将入队列栈全部压到出队列栈中

ps: 还得自己写构造函数

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1=[]
        self.stack2=[]
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        # return xx
        if self.stack2 ==[]:
            if not self.stack1:
                return None
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()
        return self.stack2.pop()