欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指Offer 67题总结(python版(持续更新))

程序员文章站 2022-06-14 23:01:18
...

1、二维数组的查找

思路:直接遍历所有的数。

    def Find(self, target, array):
        if not array:
            return
        row =len(array)
        col =len(array[0])
        for i in range(row):
            for j in range(col):
                if array[i][j]==target:
                    return True
        return False

2、替换空格

思路:使用一个新的字符串,遍历原字符串,如果遇到空格,替换成%20,如果不是,直接加入新字符串。

    def replaceSpace(self, s):
        # write code here
        res =''
        for i in s:
            if i==' ':
                res+='%20'
            else:
                res+=i
        return res

3、从头到尾打印链表

思路:将链表的每一个值插入到索引值为0的位置。

    def printListFromTailToHead(self, listNode):
        # write code here
        list = []
        while listNode:
            list.insert(0, listNode.val)
            listNode = listNode.next
        return list

4、重建二叉树

思路:考察的是二叉树的三种遍历方式,可以利用三种遍历方式的特点来缺点二叉树,前序遍历找根节点,中序找树的左右。

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

5、用两个栈实现队列

思路:利用栈后进先出的特点来实现队列的先进先出。可以将两个栈分为进栈和出栈,将进栈中要pop的数存到出栈中然后再由出栈模拟出列的操作。

    def __init__(self):
        self.stack1=[]
        self.stack2=[]
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        if self.stack2==[]:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

6、旋转数组的最小数字

思路:直接将剩下的数与第一个值做对比,找出最小值输出。

    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray)==0:
            return 0
        min_number = rotateArray[0]
        for i in range(1,len(rotateArray)):
            if rotateArray[i]<min_number:
                min_number = rotateArray[i]
        return min_number    

7、斐波那契数列

思路:这个题直接用递归会通过不了,因此可以使用动态规划来做。

    def Fibonacci(self, n):
        # write code here
        array = [0,1]
        while len(array)<=n:
            array.append(array[-1]+array[-2])
        return array[n]

8、跳台阶

思路:同第7题。

    def jumpFloor(self, number):
        # write code here
        if number==1:
            return 1
        if number==2:
            return 2
        array=[1,2]
        while len(array)<number:
            array.append(array[-1]+array[-2])
        return array[-1]

9、变态跳台阶

思路:递归

    def jumpFloorII(self, number):
        # write code here
        if number<2:
            return number
        else:
            return 2*self.jumpFloorII(number-1)

10、矩形覆盖

思路:同7、8。

class Solution:
    def rectCover(self, number):
        # write code here
        if number<=2:
            return number
        array = [1,2]
        while len(array)<number:
            array.append(array[-1]+array[-2])
        return array[-1]

马上要到秋招了,祝各位offer满满!!!