剑指Offer 一

二维数组中的查找

class Solution(object):
    def findNumberIn2DArray(self, matrix, target):
        col = len(matrix)
        if col == 0:
            return False
        row = len(matrix[0])
        m=col-1
        n=0
        while m>=0 and n < row:
            num = matrix[m][n]
            if target > num:
                n += 1
            if target < num:
                m -= 1
            if target == num:
                return True
        return False

替换空格

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

从尾到头打印链表

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

python中数组可以直接通过+添加

重建二叉树

class Solution(object):
    def buildTree(self, preorder, inorder):
        if not preorder:
            return None     
        root = TreeNode(preorder[0])
        index = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:index+1], inorder[: index])
        root.right = self.buildTree(preorder[index+1:],inorder[index+1:])
        return root

用两个栈实现队列

class CQueue(object):

    def __init__(self):
        self.data = []
        self.redata = []

    def appendTail(self, value):
        """
        :type value: int
        :rtype: None
        """
        self.data.append(value)
        

    def deleteHead(self):
        """
        :rtype: int
        """
        if not self.redata:
            while self.data:
                self.redata.append(self.data.pop())
        if not self.redata:
            return -1
        return self.redata.pop()

斐波那契数列

class Solution(object):
    def fib(self, n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        dp = [0,1]
        for i in range(2,n+1):
            dp.append(dp[i-1]+dp[i-2])
        return dp[-1]%1000000007

旋转数组的最小数字

class Solution(object):
    def minArray(self, numbers):
        """
        :type numbers: List[int]
        :rtype: int
        """
        start,last = 0,len(numbers)-1
        while start < last:
            mid = (start + last)/2
            if numbers[mid] < numbers[last]:
                last = mid
            elif numbers[mid] > numbers[last]:
                start = mid+1
            else:
                last -= 1
        return numbers[start]

删除链表的节点

class Solution(object):
    def deleteNode(self, head, val):
        dummy = ListNode(0)
        dummy.next = head

        if head.val == val: return head.next
        while head and head.next:
            if head.next.val == val:
                head.next = head.next.next
            head = head.next
        return dummy.next

链表倒数第K个节点

class Solution(object):
    def getKthFromEnd(self, head, k):
        left ,right = head, head
        for i in range(k):
            right = right.next
        while right:
            left = left.next
            right = right.next
        return left