记录剑指offer-python实现

4. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:     
        if len(matrix)==0 or len(matrix[0]) == 0 :
            return False
        rows = len(matrix)
        columns = len(matrix[0])  
        current_row = 0
        current_column = columns - 1
        while current_row < rows and current_column >= 0:
            current_num = matrix[current_row][current_column]
            if current_num == target:
                return True
            elif target < current_num:
                current_column -= 1
            elif target > current_num:
                current_row += 1
        return False

5. 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1：

输入：s = "We are happy."
输出："We%20are%20happy."

class Solution:
    def replaceSpace(self, s: str) -> str:
        result = []
        for i in s:
            if i == " ":
                result.append("%20")
            else:
                result.append(i)
        result = "".join(result)
        return result

6 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        stack = []
        while head:
            stack.append(head.val)
            head = head.next
        return stack[::-1]
        #stack.reverse()
        #return stack

07 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

# 第一种
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder, inorder):
        if inorder:
            ind = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[ind])
            root.left = self.buildTree(preorder, inorder[0:ind])
            root.right = self.buildTree(preorder, inorder[ind+1:])
            return root
# 第二种
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder, inorder):
        def foo(root, left, right):
            if left > right: return 
            node = TreeNode(preorder[root])
            i = m[preorder[root]]
            node.left = foo(root+1, left, i-1)
            node.right = foo(i-left+root+1, i+1, right)
            return node
        m = dict()
        for index, value in enumerate(inorder):
            m[value] = index
        return foo(0,0, len(preorder)-1)

09 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

class CQueue:

    def __init__(self):
        self.s1 = []
        self.s2 = []
        # append(), pop()

    def appendTail(self, value: int) -> None:
        self.s1.append(value)

    def deleteHead(self) -> int:
        if not self.s2:
            if not self.s1:
                return -1
            else:
                for _ in range(len(self.s1)):
                    self.s2.append(self.s1.pop())

        result = self.s2.pop()
        return result

# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()