# 剑指Offer 23-44题(Python版)

```# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
if not sequence:
return False
if len(sequence)==1:
return True
i=0
while sequence[i]<sequence[-1]:
i=i+1
k=i
for j in range(i,len(sequence)-1):
if sequence[j]<sequence[-1]:
return False

leftsequence=sequence[:k]
rightsequence=sequence[k:len(sequence)-1]

leftans=True
rightans=True

if len(leftsequence)>0:
self.VerifySquenceOfBST(leftsequence)
if len(rightsequence)>0:
self.VerifySquenceOfBST(rightsequence)

return leftans and rightans

if __name__=='__main__':
solution=Solution()
num=list(map(int,input().split(' ')))
ans=solution.VerifySquenceOfBST(num)
print(ans)```

### 24.二叉树中和为某一值的路径

```# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
# write code here
if not root:
return []
ans=[]
path=[]
self.dfs(root,expectNumber,ans,path)
ans.sort()
return ans

def dfs(self,root,target,ans,path):
if not root:
return

path.append(root.val)
if root.left is None and root.right is None and target==root.val:
ans.append(path[:])

if root.left:
self.dfs(root.left,target-root.val,ans,path)
if root.right:
self.dfs(root.right,target-root.val,ans,path)

path.pop()

if __name__=='__main__':
A1=TreeNode(10)
A2=TreeNode(8)
A3=TreeNode(12)
A4=TreeNode(4)
A5=TreeNode(2)
A6=TreeNode(2)

A1.left=A2
A1.right=A3
A2.left=A4
A2.right=A5
A5.left=A6

expectNumber=22
solution=Solution()
ans=solution.FindPath(A1,expectNumber)
print(ans)```

### 25.复杂链表的复制

```# -*- coding:utf-8 -*-
class RandomListNode:
def __init__(self, x):
self.label = x
self.next = None
self.random = None

class Solution:
# 返回 RandomListNode
# write code here
# 复制头部节点
return None

# 递归其他节点

if __name__=='__main__':
A1=RandomListNode(2)
A2=RandomListNode(3)
A3=RandomListNode(4)
A4=RandomListNode(5)
A5=RandomListNode(6)

A1.next=A2
A1.random=A3

A2.next=A3
A2.random=A4

A3.next=A4
A3.random=A5

A4.next=A5
A4.random=A3

solution=Solution()
ans=solution.Clone(A1)```

### 26.二叉搜索树与双向列表

```# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def Convert(self, pRootOfTree):
# write code here
if pRootOfTree is None:
return pRootOfTree
if pRootOfTree.left is None and pRootOfTree.right is None:
return pRootOfTree

#处理左子树
self.Convert(pRootOfTree.left)
left=pRootOfTree.left

if left:
while left.right:
left=left.right
pRootOfTree.left,left.right=left,pRootOfTree

#处理右子树
self.Convert(pRootOfTree.right)
right=pRootOfTree.right

if right:
while right.left:
right=right.left
pRootOfTree.right,right.left=right,pRootOfTree

while pRootOfTree.left:
pRootOfTree=pRootOfTree.left
return pRootOfTree

if __name__=='__main__':
A1 = TreeNode(7)
A2 = TreeNode(5)
A3 = TreeNode(15)
A4 = TreeNode(2)
A5 = TreeNode(6)
A6 = TreeNode(8)
A7 = TreeNode(19)
A8 = TreeNode(24)

A1.left=A2
A1.right=A3
A2.left=A4
A2.right=A5
A3.left=A6
A3.right=A7
A7.right=A8

solution=Solution()
solution.Convert(A1)```

### 27.字符串的排列

```# -*- coding:utf-8 -*-
class Solution:
def Permutation(self, ss):
# write code here
if not ss:
return []
res=[]
self.helper(ss,res,'')
return sorted(list(set(res)))

def helper(self,ss,res,path):
if not ss:
res.append(path)
else:
for i in range(0,len(ss)):
self.helper(ss[:i]+ss[i+1:],res,path+ss[i])

if __name__=='__main__':
str='abbcDeefg'
str1='abbc'
solution=Solution()
ans=solution.Permutation(str1)
print(ans)```

### 28.数组中出现次数超过一般的数字

```# -*- coding:utf-8 -*-
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
numlen=len(numbers)
halflen=numlen//2
maxans=0
ans=[0 for i in range(0,1000)]
for i in range(0,len(numbers)):
ans[numbers[i]]=ans[numbers[i]]+1
if ans[numbers[i]]>maxans:
maxans=numbers[i]
ans.sort()
ans.reverse()
res=ans[0]
if res>halflen:
return maxans
else:
return 0

if __name__=='__main__':
num=list(map(int,input().split(',')))
solution=Solution()
ans=solution.MoreThanHalfNum_Solution(num)
print(ans)```

### 29.最小的K个数

```# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if k>len(tinput):
return []
tinput.sort()
return tinput[:k]

if __name__=='__main__':
num=list(map(int,input().split(',')))
k=int(input())
solution=Solution()
ans=solution.GetLeastNumbers_Solution(num,k)
print(ans)```

### 30.连续子数组的最大和

```# -*- coding:utf-8 -*-
class Solution:
def FindGreatestSumOfSubArray(self, array):
# write code here
maxsum,tempsum=array[0],array[0]
for i in range(1,len(array)):
if tempsum<0:
tempsum=array[i]
else:
tempsum = tempsum + array[i]
if tempsum>maxsum:
maxsum=tempsum
return maxsum

if __name__=='__main__':
array=list(map(int,input().split(',')))
solution=Solution()
ans=solution.FindGreatestSumOfSubArray(array)
print(ans)```

### 31.整数中1出现的次数

```# -*- coding:utf-8 -*-
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
# write code here
ans=0
for i in range(1,n+1):
tempans=0
while i!=0:
eachnum=i%10
i=i//10
if eachnum==1:
tempans=tempans+1
ans=ans+tempans
return ans

if __name__=='__main__':
n=130
solution=Solution()
ans=solution.NumberOf1Between1AndN_Solution(n)
print(ans)```

### 32.把数组排成最小的数

```# -*- coding:utf-8 -*-
class Solution:
def PrintMinNumber(self, numbers):
# write code here
if not numbers:
return ""
num = map(str, numbers)
for i in range(0,len(numbers)):
for j in range(i,len(numbers)):
if int(str(numbers[i])+str(numbers[j]))>int(str(numbers[j])+str(numbers[i])):
numbers[i],numbers[j]=numbers[j],numbers[i]
ans=''
for i in range(0,len(numbers)):
ans=ans+str(numbers[i])
return ans

if __name__=='__main__':
numbers=[3,32,321]
solution=Solution()
ans=solution.PrintMinNumber(numbers)
print(ans)```

### 33.丑数

```# -*- coding:utf-8 -*-
class Solution:
def GetUglyNumber_Solution(self, index):
# write code here
if (index <= 0):
return 0
uglyList = [1]
indexTwo = 0
indexThree = 0
indexFive = 0
for i in range(index-1):
newUgly = min(uglyList[indexTwo]*2, uglyList[indexThree]*3, uglyList[indexFive]*5)
uglyList.append(newUgly)
if (newUgly % 2 == 0):
indexTwo += 1
if (newUgly % 3 == 0):
indexThree += 1
if (newUgly % 5 == 0):
indexFive += 1
return uglyList[-1]

if __name__=='__main__':
solution=Solution()
index=200
ans=solution.GetUglyNumber_Solution(index)
print(ans)```

### 34.第一个只出现一次的字符

```# -*- coding:utf-8 -*-
class Solution:
def FirstNotRepeatingChar(self, s):
# write code here
if not s:
return -1
sset=set(s)
dict={}
for c in sset:
dict[c]=0
for i in range(0,len(s)):
dict[s[i]]=dict[s[i]]+1
onetime=[]
for c in dict:
if dict[c]==1:
onetime.append(c)

if onetime is None:
return -1
else:
index=0
for i in range(0,len(s)):
if s[i] in onetime:
index=i
break
return index

if __name__=='__main__':
s='abbddebbac'
solution=Solution()
ans=solution.FirstNotRepeatingChar(s)
print(ans)```

### 35.数组中的逆序对

```# -*- coding:utf-8 -*-
class Solution:
def InversePairs(self, data):
# write code here
global count
count = 0

def A(array):
global count
if len(array) <= 1:
return array
k = int(len(array) / 2)
left = A(array[:k])
right = A(array[k:])
l = 0
r = 0
result = []
while l < len(left) and r < len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
count += len(left) - l
result += left[l:]
result += right[r:]
return result

A(data)
return count % 1000000007

if __name__=='__main__':
data=[1,2,3,4,5,6,7,0]
solution=Solution()
ans=solution.InversePairs(data)
print(ans)```

### 36.两个链表的第一个公共节点

```# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
# write code here
list1 = []
list2 = []
while node1:
list1.append(node1.val)
node1 = node1.next
while node2:
if node2.val in list1:
return node2
else:
node2 = node2.next

if __name__=='__main__':
A1 = ListNode(1)
A2 = ListNode(2)
A3 = ListNode(3)
A1.next=A2
A2.next=A3

B4 = ListNode(4)
B5 = ListNode(5)
B4.next=B5

C6=ListNode(6)
C7=ListNode(7)

A3.next=C6
B5.next=C6
C6.next=C7

solution=Solution()
ans=solution.FindFirstCommonNode(A1,B4)
print(ans.val)```

### 37.数字在排序数组中出现的次数

```# -*- coding:utf-8 -*-
class Solution:
def GetNumberOfK(self, data, k):
# write code here
ans=0
for i in range(0,len(data)):
if data[i]==k:
ans=ans+1
if data[i]>k:
break
return ans

if __name__=='__main__':
data=[1,2,3,3,3,4,4,5]
k=3
solution=Solution()
ans=solution.GetNumberOfK(data,k)
print(ans)```

### 38.二叉树的深度

```# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

class Solution:
def TreeDepth(self, pRoot):
# write code here
if pRoot is None:
return 0
left=self.TreeDepth(pRoot.left)
right=self.TreeDepth(pRoot.right)
print(left,right)
return max(left,right)+1

if __name__=='__main__':
A1 = TreeNode(1)
A2 = TreeNode(2)
A3 = TreeNode(3)
A4 = TreeNode(4)
A5 = TreeNode(5)
A6 = TreeNode(6)

A1.left=A2
A1.right=A3
A2.left=A4
A2.right=A5
A4.left=A6

solution=Solution()
ans=solution.TreeDepth(A1)
print('ans=',ans)```

### 39.平衡二叉树

```# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def IsBalanced_Solution(self, pRoot):
# write code here
if pRoot is None:
return True
if abs(self.TreeDepth(pRoot.left)-self.TreeDepth(pRoot.right))>1:
return False
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)

def TreeDepth(self,root):
if root is None:
return 0
left=self.TreeDepth(root.left)
right=self.TreeDepth(root.right)
return max(left+1,right+1)

if __name__=='__main__':
A1 = TreeNode(1)
A2 = TreeNode(2)
A3 = TreeNode(3)
A4 = TreeNode(4)
A5 = TreeNode(5)
A6 = TreeNode(6)

A1.left=A2
A1.right=A3
A2.left=A4
A2.right=A5
#A4.left=A6

solution=Solution()
ans=solution.IsBalanced_Solution(A1)
print(ans)```

### 40.数组中只出现一次的数字

```# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
# write code here
arrayset=set(array)
dict={}
for num in arrayset:
dict[num]=0
for i in range(0,len(array)):
dict[array[i]]=dict[array[i]]+1
ans=[]
for num in arrayset:
if dict[num]==1:
ans.append(num)
return ans

if __name__=='__main__':
array=[1,1,2,2,3,3,4,5,5,6,7,7]
solution=Solution()
ans=solution.FindNumsAppearOnce(array)
print(ans)```

### 41.和为S的连续正整数序列

```# -*- coding:utf-8 -*-
class Solution:
def FindContinuousSequence(self, tsum):
# write code here
ans=[]
for i in range(1,tsum//2+1):
oneans=[]
for k in range(1,tsum):
tempsum=((i+i+k-1)*k)//2
if tempsum==tsum:
for j in range(i,i+k):
oneans.append(j)
break
if oneans !=[]:
ans.append(oneans)
return ans

if __name__=='__main__':
tsum=15
solution=Solution()
ans=solution.FindContinuousSequence(tsum)
print(ans)```

### 42.和为S的两个数字

```# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
ans=[]
i,j,minres=0,len(array)-1,1000000
for i in range(0,len(array)-1):
j=len(array)-1
while True:
tempsum = array[i] + array[j]
if tempsum == tsum:
if array[i]*array[j]<minres:
ans=[]
ans.append(array[i])
ans.append(array[j])
minres=array[i]*array[j]
break
else:
j = j - 1
if tempsum<tsum:
break
if j<=i:
break
return ans

if __name__=='__main__':
array=[1,2,4,7,11,15]
tsum=15
solution=Solution()
ans=solution.FindNumbersWithSum(array,tsum)
print(ans)```

### 43.左旋字符子串

```# -*- coding:utf-8 -*-
class Solution:
def LeftRotateString(self, s, n):
# write code here
if s=='' and n==0:
return ''
ans=''
ans=s[n:]+s[0:n]
return ans

if __name__=='__main__':
s='abcdefg'
n=2
solution=Solution()
ans=solution.LeftRotateString(s,n)
print(ans)```

### 44.反转单词顺序

```# -*- coding:utf-8 -*-
class Solution:
def ReverseSentence(self, s):
# write code here
ans,word=[],''
for i in range(0,len(s)):
word = word + s[i]
if s[i]==' ':
ans.append(word)
word=''
if i==len(s)-1:
word=word+' '
ans.append(word)
ans.reverse()
res=''
for c in ans:
res=res+c
return res[:len(res)-1]

if __name__=='__main__':
solution=Solution()
s='I am a student.'
ans=solution.ReverseSentence(s)
print(ans)```

0 条评论

• ### 每周分享第一期

这里记录我过去一周看到的新闻、故事、技术、资料等等，分享给各位。同时也欢迎各位投稿，投稿地址zhenhai.gl@gmail.com。

• ### 剑指Offer 45-66题(Python版)

题目：LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看...

• ### 剑指Offer 1-22题(Python版)

题目： 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数...

• ### Vijos P1784 数字统计【模拟】

数字统计 背景 来自 NOIP2010 普及组 第一题 描述 请统计某个给定范围[L, R]的所有整数中，数字2出现的次数。 比如在给定范围[2, 22]，数...

• ### 【最新】ICCV 2017 Tutorial 大全目录

【导读】当地时间 10月 22 日到10月29日，两年一度的计算机视觉国际顶级会议 International Conference on Computer V...

• ### LeetCode 831. 隐藏个人信息

定义名称 name 是长度大于等于 2 （length ≥ 2），并且只包含小写字母 a-z 和大写字母 A-Z 的字符串。

• ### 高可用篇之Keepalived （HAProxy+keepalived 搭建高可用负载均衡集群）

Keepalived是Linux下一个轻量级别的高可用解决方案。健康检查和失败切换是keepalived的两大核心功能。所谓的健康检查，就是采用tcp三次握手，...

• ### ios Charts MarkerView遇到的一个问题

两个问题 问题1：最大值的的时候 MarkerView 坐标有问题 ，原因就是最大值的时候，曲线已经在View的顶部了，所以MarkerView 的Y坐标还要...

• ### RTSP协议视频智能分析/智能识别服务平台EasyNVR新增自定义登录失败锁定用户功能

对于流媒体服务器来说，登录鉴权的存在能够给与用户一定的安全保护，TSINGSEE青犀视频云边端架构视频平台提供简单的登录鉴权，并且在EasyNVR视频平台内新增...

• ### Spark UDF加载外部资源

由于Spark UDF的输入参数必须是数据列column，在UDF中进行如Redis查询、白/黑名单过滤前，需要加载外部资源(如配置参数、白名单)初始化它们的实...