题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路:二叉搜索树的特性是所有左子树值都小于中节点,所有右子树的值都大于中节点,递归遍历左子树和右子树的值。
# -*- 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)
题目:输入一颗二叉树的根节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前)。
思路:利用递归的方法,计算加左子树和右子树之后的值,当参数较多是,可以将结果添加到函数变量之中。
# -*- 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)
题目:输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)。
思路:将大问题转变为小问题,每次都进行复制头部节点,然后进行递归,每次同样处理头部节点。
# -*- coding:utf-8 -*-
class RandomListNode:
def __init__(self, x):
self.label = x
self.next = None
self.random = None
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
# 复制头部节点
if pHead is None:
return None
newHead=RandomListNode(pHead.label)
newHead.next=pHead.next
newHead.random=pHead.random
# 递归其他节点
newHead.next=self.Clone(pHead.next)
return newHead
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)
题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
思路:递归将根结点和左子树的最右节点和右子树的最左节点进行连接起来。
# -*- 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)
题目:输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入:输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
思路:通过将第k位的字符提取到最前面,然后进行和后面的每个字符进行交换,得到所有结果集。
# -*- 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)
题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0
题解:利用list列表来存放每个数出现的次数ans[numbers[i]]=ans[numbers[i]]+1。
# -*- 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)
题目:输入n个整数,找出其中最小的K个数,例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。
# -*- 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)
题目:HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住?(子向量的长度至少是1)
# -*- 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)
题目:求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。
思路:对每个数字的每位进行分解,含有1则结果加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)
题目:输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。
思路:将数组转换成字符串之后,进行两两比较字符串的大小,比如3,32的大小由332和323确定,即3+32和32+3确定。
# -*- 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)
题目:把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
思路:每一个丑数必然是由之前的某个丑数与2,3或5的乘积得到的,这样下一个丑数就用之前的丑数分别乘以2,3,5,找出这三这种最小的并且大于当前最大丑数的值,即为下一个要求的丑数。
# -*- 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)
题目:在一个字符串(0<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1。
思路:找出所有出现一次的字符,然后进行遍历找到第一次出现字符的位置。
# -*- 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)
题目描述:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。
输入描述:题目保证输入的数组中没有的相同的数字。
数据范围:对于%50的数据,size<=10^4 对于%75的数据,size<=10^5 对于%100的数据,size<=2*10^5
示例1 输入 1,2,3,4,5,6,7,0 输出 7
# -*- 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)
题目:输入两个链表,找出它们的第一个公共结点。
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
list1 = []
list2 = []
node1 = pHead1
node2 = pHead2
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)
题目:统计一个数字在排序数组中出现的次数。
# -*- 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)
题目:输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
# -*- 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)
题目:输入一棵二叉树,判断该二叉树是否是平衡二叉树。
题解:平衡二叉树是左右子数的距离不能大于1,因此递归左右子树,判断子树距离是否大于1。
# -*- 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)
题目:一个整型数组里除了两个数字之外,其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。
题解:将数组中数转到set之中,然后利用dict存储每个数字出现的次数。
# -*- 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)
题目:小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述:输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序。
思路:首项加尾项*2等于和,那么只要遍历项的开始和长度即可。
# -*- 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)
题目:输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
输出描述:对应每个测试案例,输出两个数,小的先输出。
思路:利用i和j从后面进行扫描结果,选取最小的乘积放入到结果集之中。
# -*- 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)
题目:汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S,请你把其循环左移K位后的序列输出。例如,字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果,即“XYZdefabc”。是不是很简单?OK,搞定它!
# -*- 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)
题目:牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“student. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?
# -*- 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)
你看到的这篇文章来自于公众号「谓之小一」,欢迎关注我阅读更多文章。