剑指offer刷题（一）

1、二维数组的查找

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

思路一：从右上开始搜索，如果数组中的数比该数要大，那么想左移动一位，如果数组中的数比该数小，向下移动一位，因为数组本身是从左到右依次增大，从上到下依次增大。

class Solution:
    def Find(self,array, target):
        if array == []:
            return False

        row = 0
        col = len(array[0])-1
        while row < len(array) and col >=0:
            if array[row][col] == target:
                return True
            elif array[row][col] < target:
                row = row + 1
            else:
                col = col - 1
        return False

思路二：循环遍历查找（比较low）,是时间复杂度O^2

class Solution:
    def Find(self, target, array):
        # write code here
        if not array:
            return False
        row = 0
        col = len(array[0])-1
        while row < len(array) and col >=0:
            if array[row][col] == target:
                return True
            elif array[row][col] < target:
                row = row + 1
            else:
                col = col - 1
        return False

测试代码

array = [[1, 2, 8, 9],
         [2, 4, 9, 12],
         [4, 7, 10, 13],
         [6, 8, 11, 15]]

findtarget = Solution()
print(findtarget.Find(array, 10))
print(findtarget.Find(array, 30))
print(findtarget.Find(array, 13.0))

2、替换空格

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

思路一：使用replace方法。

运行时间：28ms 占用内存：5624k

class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        return s.replace(' ','%20')

思路二：创建新的字符串进行替换

在自己电脑上运行没问题，但是牛客网上说存在越界。。。

class Solution:
    def replaceSpace(self, s):
        tempstr = ''
        if type(s) != str:
            return
        for c in s:
            if c == ' ':
                tempstr += '%20'
            else:
                tempstr += c
        return tempstr

3、从尾到头打印链表

题目描述:输入一个链表，从尾到头打印链表每个节点的值。'''

思路：使用insert方法插入列表，返回从尾部到头部的列表值序列

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        if not ListNode:
            return []

        result = []
        head = listNode

        while head:
            result.insert(0, head.val)
            head = head.next

        return result

4、重建二叉树

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

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        if not pre or not tin:
            return None
        root = TreeNode(pre[0])

        if set(pre) != set(tin):
            return None
        i = tin.index(pre[0])
        root.left = self.reConstructBinaryTree(pre[1:i + 1], tin[:i])
        root.right = self.reConstructBinaryTree(pre[i + 1:], tin[i + 1:])
        return root