剑指Offer 67题总结(python版(持续更新))
程序员文章站
2022-06-14 23:01:18
...
剑指Offer 67题总结(python版 1-10 题)
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满满!!!
上一篇: activity window
下一篇: Windows 修改网卡 MTU