剑指Offer 1-22题(Python版)
题目： 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：遍历每一行，查找该元素是否在该行之中。
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
for line in array:
if target in line:
return True
return False
if __name__=='__main__':
target=2
array=[[1,2,3,4],[2,3,4,5],[3,4,5,6],[4,5,6,7]]
solution=Solution()
ans=solution.Find(target,array)
print(ans)2.替换空格
题目： 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路：利用字符串中的replace直接替换即可。
# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
temp = s.replace(" ", "%20")
return temp
if __name__=='__main__':
s='We Are Happy'
solution=Solution()
ans=solution.replaceSpace(s)
print(ans)3.从尾到头打印链表
题目：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
思路：将链表中的值记录到list之中，然后进行翻转list。
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
l=[]
while listNode:
l.append(listNode.val)
listNode=listNode.next
return l[::-1]
if __name__=='__main__':
A1 = ListNode(1)
A2 = ListNode(2)
A3 = ListNode(3)
A4 = ListNode(4)
A5 = ListNode(5)
A1.next=A2
A2.next=A3
A3.next=A4
A4.next=A5
solution=Solution()
ans=solution.printListFromTailToHead(A1)
print(ans)4.重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
题解：首先前序遍历的第一个元素为二叉树的根结点，那么便能够在中序遍历之中找到根节点，那么在根结点左侧则是左子树，假设长度为M.在根结点右侧，便是右子树,假设长度为N。然后在前序遍历根节点后面M长度的便是左子树的前序遍历序列，再后面的N个长度便是右子树的后序遍历的长度。
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if len(pre)==0:
return None
if len(pre)==1:
return TreeNode(pre[0])
else:
flag=TreeNode(pre[0])
flag.left=self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[:tin.index(pre[0])])
flag.right=self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1:])
return flag
if __name__=='__main__':
solution=Solution()
pre=list(map(int,input().split(',')))
tin=list(map(int,input().split(',')))
ans=solution.reConstructBinaryTree(pre,tin)
print(ans.val)5.用两个栈实现队列
题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
题解：申请两个栈Stack1和Stack2，Stack1当作输入，Stack2当作pop。当Stack2空的时候，将Stack1进行反转，并且输入到Stack2。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.Stack1=[]
self.Stack2=[]
def push(self, node):
# write code here
self.Stack1.append(node)
def pop(self):
# return xx
if self.Stack2==[]:
while self.Stack1:
self.Stack2.append(self.Stack1.pop())
return self.Stack2.pop()
return self.Stack2.pop()
if __name__=='__main__':
solution = Solution()
solution.push(1)
solution.push(2)
solution.push(3)
print(solution.pop())6.旋转数组的最小数字
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
题解：遍历数组寻找数组最小值。
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
minnum=999999
for i in range(0,len(rotateArray)):
if minnum>rotateArray[i]:
minnum=rotateArray[i]
if minnum:
return minnum
else:
return 0
if __name__=='__main__':
solution=Solution()
rotateArray=list(map(int,input().split(',')))
ans=solution.minNumberInRotateArray(rotateArray)
print(ans)7.斐波那契数列
题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39。
题解：递归和非递归方法。
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
if n==0:
return 0
if n==1:
return 1
Fib=[0 for i in range(0,n+1)]
Fib[0],Fib[1]=0,1
for i in range(2,n+1):
Fib[i]=Fib[i-1]+Fib[i-2]
return Fib[n]
def Fibonacci1(self,n):
if n==0:
return 0
if n==1 or n==2:
return 1
else:
return self.Fibonacci1(n-1)+self.Fibonacci1(n-2)
if __name__=='__main__':
solution=Solution()
n=int(input())
ans=solution.Fibonacci1(n)
print(ans)8.跳台阶
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
题解：ans[n]=ans[n-1]+ans[n-2]
class Solution:
def jumpFloor(self, number):
# write code here
if number==0:
return 0
if number==1:
return 1
if number==2:
return 2
ans=[0 for i in range(0,number+1)]
ans[1],ans[2]=1,2
for i in range(3,number+1):
ans[i]=ans[i-1]+ans[i-2]
return ans[number]
if __name__ == '__main__':
solution = Solution()
n=int(input())
ans=solution.jumpFloor(n)
print(ans)9.变态跳台阶
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
题解：ans[n]=ans[n-1]+ans[n-2]+ans[n-3]+...+ans[n-n]，ans[n-1]=ans[n-2]+ans[n-3]+...+ans[n-n]，ans[n]=2*ans[n-1]。
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
if number==1:
return 1
if number==2:
return 2
return 2*self.jumpFloorII(number-1)
if __name__=='__main__':
solution=Solution()
n=int(input())
ans=solution.jumpFloorII(n)
print(ans)10.矩形覆盖
题目：我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
题解：新增加的小矩阵竖着放，则方法与n-1时相同，新增加的小矩阵横着放，则方法与n-2时相同，于是f(n)=f(n-1)+f(n-2)。
# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number==0:
return 0
if number==1:
return 1
Fib=[0 for i in range(0,number+1)]
Fib[1],Fib[2]=1,2
for i in range(3,number+1):
Fib[i]=Fib[i-1]+Fib[i-2]
return Fib[number]
if __name__=='__main__':
solution=Solution()
n=int(input())
ans=solution.rectCover(n)
print(ans)11.二进制中1的个数
题目：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
题解：每次进行左移一位，然后与1进行相与，如果是1则进行加1。
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
# write code here
count = 0
for i in range(32):
count += (n >> i) & 1
return count
if __name__=='__main__':
solution=Solution()
n=int(input())
ans=solution.NumberOf1(n)
print(ans)12.数值的整次方
题目：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
# write code here
ans=1
for i in range(0,abs(exponent)):
ans=ans*base
if exponent>0:
return ans
else:
return 1/ans
if __name__=='__main__':
solution=Solution()
base=float(input())
exponent=int(input())
ans=solution.Power(base,exponent)
print(ans)13.调整数组顺序使奇数位于偶数前面
题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
题解：申请奇数数组和偶数数组，分别存放奇数值和偶数值，数组相加便为结果。
# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self, array):
# write code here
array1=[]#奇数
array2=[]#偶数
for i in range(0,len(array)):
if array[i]%2!=0:
array1.append(array[i])
else:
array2.append(array[i])
ans=array1+array2
return ans
if __name__=='__main__':
solution=Solution()
array=list(map(int,input().split(',')))
ans=solution.reOrderArray(array)
print(ans)14.链表中倒数第K个节点
题目：输入一个链表，输出该链表中倒数第k个结点。
题解：反转链表，寻找第K个节点。
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def FindKthToTail(self, head, k):
# write code here
#反转链表
if head is None or head.next is None:
return head
pre=None #指向上一个节点
while head:
#先用temp保存当前节点的下一个节点信息
temp=head.next
#保存好next之后，便可以指向上一个节点
head.next=pre
#让pre,head指向下一个移动的节点
pre=head
head=temp
# 寻找第K个元素的位置
for i in range(1,k):
pre=pre.next
temp=pre
return temp
if __name__=='__main__':
solution=Solution()
k=3
p1=ListNode(1)
p2=ListNode(2)
p3=ListNode(3)
p4=ListNode(4)
p1.next=p2
p2.next=p3
p3.next=p4
ans=solution.FindKthToTail(p1,k)
print(ans.val)15.反转链表
题目：输入一个链表，反转链表后，输出新链表的表头。
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
if pHead is None or pHead.next is None:
return pHead
pre=None
while pHead:
#暂存当前节点的下一个节点信息
temp=pHead.next
#反转节点
pHead.next=pre
#进行下一个节点
pre = pHead
pHead=temp
return pre
if __name__=='__main__':
solution=Solution()
p1=ListNode(1)
p2=ListNode(2)
p3=ListNode(3)
p1.next=p2
p2.next=p3
ans=solution.ReverseList(p1)
print(ans.val)16.合并两个排序的列表
题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
题解：将两个链表之中的数值转换到列表之中，并进行排序，将排序后的列表构造成链表。
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
# 返回合并后列表
def Merge(self,pHead1,pHead2):
# write code here
if pHead1 is None and pHead2 is None:
return None
num1,num2=[],[]
while pHead1:
num1.append(pHead1.val)
pHead1=pHead1.next
while pHead2:
num2.append(pHead2.val)
pHead2=pHead2.next
ans=num1+num2
ans.sort()
head=ListNode(ans[0])
pre=head
for i in range(1,len(ans)):
node=ListNode(ans[i])
pre.next=node
pre=pre.next
return head
if __name__=='__main__':
solution=Solution()
pHead1_1 = ListNode(1)
pHead1_2 = ListNode(3)
pHead1_3 = ListNode(5)
pHead1_1.next=pHead1_2
pHead1_2.next=pHead1_3
pHead2_1 = ListNode(2)
pHead2_2 = ListNode(4)
pHead2_3 = ListNode(6)
pHead2_1.next=pHead2_2
pHead2_2.next=pHead2_3
ans=solution.Merge(pHead1_1,pHead2_1)
print(ans)17.树的子结构
题目：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）。
题解：将树转变为中序序列，然后转变为str类型，最后判断是否包含。
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
# write code here
if pRoot1 is None or pRoot2 is None:
return False
pRoot1_result,pRoot2_result=[],[]
self.order_traversal(pRoot1,pRoot1_result)
self.order_traversal(pRoot2,pRoot2_result)
str1=''.join(str(i) for i in pRoot1_result)
str2=''.join(str(i) for i in pRoot2_result)
print(str1,str2)
if str2 in str1:
return True
else:
return False
def order_traversal(self,root,result):
if not root:
return
self.order_traversal(root.left,result)
result.append(root.val)
self.order_traversal(root.right,result)
if __name__=='__main__':
solution=Solution()
pRootA1 = TreeNode(1)
pRootA2 = TreeNode(2)
pRootA3 = TreeNode(3)
pRootA4 = TreeNode(4)
pRootA5 = TreeNode(5)
pRootA1.left=pRootA2
pRootA1.right=pRootA3
pRootA2.left=pRootA4
pRootA2.right=pRootA5
pRootB2 = TreeNode(2)
pRootB4 = TreeNode(4)
pRootB5 = TreeNode(5)
pRootB2.left=pRootB4
pRootB2.right = pRootB5
ans=solution.HasSubtree(pRootA1,pRootB2)
print(ans)18.二叉树的镜像
题目： 操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述：
源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5
思路：递归实现反转每个子节点
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回镜像树的根节点
def Mirror(self, root):
# write code here
# A1_order_result=[]
# self.order_traversal(A1,A1_order_result)
if root is None:
return
if root.left is None and root.right is None:
return
temp=root.left
root.left=root.right
root.right=temp
if root is not None:
self.Mirror(root.left)
if root is not None:
self.Mirror(root.right)
def order_traversal(self,root,result):
if not root:
return
self.order_traversal(root.left,result)
result.append(root.val)
self.order_traversal(root.right,result)
if __name__=='__main__':
A1 = TreeNode(8)
A2 = TreeNode(6)
A3 = TreeNode(10)
A4 = TreeNode(5)
A5 = TreeNode(7)
A6 = TreeNode(9)
A7 = TreeNode(11)
A1.left=A2
A1.right=A3
A2.left=A4
A2.right=A5
A3.left=A6
A3.right=A7
temp1=[]
solution=Solution()
solution.order_traversal(A1,temp1)
print(temp1)
solution.Mirror(A1)
solution.order_traversal(A1,temp1)
print(temp1)19.顺时针打印矩阵
题目：
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，
例如，如果输入如下矩阵：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
则依次打印出数字
1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.思路：每次打印圈，但要判断最后一次是打印横还是竖，另外判断数据是否已存在。
# -*- coding:utf-8 -*-
class Solution:
# matrix类型为二维列表，需要返回列表
def printMatrix(self, matrix):
# write code here
m,n=len(matrix),len(matrix[0])
res = []
if n==1 and m==1:
res.append(matrix[0][0])
return res
for k in range(0,(min(m,n)+1)//2):
[res.append(matrix[k][i]) for i in range(k, n - k)]
[res.append(matrix[j][n-k-1]) for j in range(k,m-k) if matrix[j][n-k-1] not in res]
[res.append(matrix[m-k-1][j]) for j in range(n-k-1,k-1,-1) if matrix[m-k-1][j] not in res]
[res.append(matrix[j][k]) for j in range(m-1-k,k-1,-1) if matrix[j][k] not in res]
return res
if __name__=='__main__':
solution=Solution()
m,n=1,5
matrix=[]
for i in range(0,m):
matrix.append(list(map(int,input().split(' '))))
print(matrix)
ans=solution.printMatrix(matrix)
print(ans)20.包含Min函数的栈
题目：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.num=[]
def push(self, node):
# write code here
self.num.append(node)
def pop(self):
# write code here
self.num.pop()
def top(self):
# write code here
numlen = len(self.num)
return self.num[numlen-1]
def min(self):
# write code here
return min(self.num)
if __name__=='__main__':
solution = Solution()
solution.push(1)
solution.push(2)
solution.push(3)
solution.push(4)
solution.pop()
print(solution.top())
print(solution.min())21.栈的压入弹出序列
题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）。
题解：新构建一个中间栈，来模拟栈的输入和栈的输出，比对输入结果和输出结果是否相等。
# -*- coding:utf-8 -*-
class Solution:
def IsPopOrder(self, pushV, popV):
# write code here
if len(pushV)==1 and len(popV)==1 and pushV[0]!=popV[0]:
return False
helpV=[]
pushV.reverse()
popV.reverse()
#模拟给定栈的压入和压出
helpV.append(pushV[len(pushV)-1])
pushV.pop()
while True:
if helpV[len(helpV)-1]!=popV[len(popV)-1]:
helpV.append(pushV[len(pushV)-1])
pushV.pop()
if helpV[len(helpV)-1]==popV[len(popV)-1]:
helpV.pop()
popV.pop()
if pushV==[] and popV==[] and helpV==[]:
return True
if pushV==[] and popV[len(popV)-1]!=helpV[len(helpV)-1]:
return False
if __name__=='__main__':
solution=Solution()
push=list(map(int,input().split(' ')))
pop=list(map(int,input().split(' ')))
ans=solution.IsPopOrder(push,pop)
print(ans)22.从上往下打印二叉树
题目：从上往下打印出二叉树的每个节点，同层节点从左至右打印。
思路：递归，每次将左子树结果和右子树结果存到结果集之中。
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回从上到下每个节点值列表，例：[1,2,3]
def PrintFromTopToBottom(self, root):
# write code here
if root is None:
return []
ans=[]
ans.append(root.val)
self.orderans(root,ans)
return ans
def orderans(self,root,ans):
if not root:
return
if root.left:
ans.append(root.left.val)
if root.right:
ans.append(root.right.val)
self.orderans(root.left, ans)
self.orderans(root.right,ans)
if __name__=='__main__':
solution=Solution()
A1 = TreeNode(1)
A2 = TreeNode(2)
A3 = TreeNode(3)
A4 = TreeNode(4)
A5 = TreeNode(5)
A1.left=A2
A1.right=A3
A2.left=A4
A2.right=A5
ans=solution.PrintFromTopToBottom(A1)
print(ans)你看到的这篇文章来自于公众号「谓之小一」，欢迎关注我阅读更多文章。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-08-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录