leetcode如何求将子数组重新排序得到同一个二叉查找树的方案数
这篇文章给大家分享的是有关leetcode如何求将子数组重新排序得到同一个二叉查找树的方案数的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。
成都创新互联公司致力于网站建设、成都网站建设,成都网站设计,集团网站建设等服务标准化,推过标准化降低中小企业的建站的成本,并持续提升建站的定制化服务水平进行质量交付,让企业网站从市场竞争中脱颖而出。 选择成都创新互联公司,就选择了安全、稳定、美观的网站建设服务!
给你一个数组 nums 表示 1 到 n 的一个排列。我们按照元素在 nums 中的顺序依次插入一个初始为空的二叉查找树(BST)。请你统计将 nums 重新排序后,统计满足如下条件的方案数:重排后得到的二叉查找树与 nums 原本数字顺序得到的二叉查找树相同。
比方说,给你 nums = [2,1,3],我们得到一棵 2 为根,1 为左孩子,3 为右孩子的树。数组 [2,3,1] 也能得到相同的 BST,但 [3,2,1] 会得到一棵不同的 BST 。
请你返回重排 nums 后,与原数组 nums 得到相同二叉查找树的方案数。
由于答案可能会很大,请将结果对 10^9 + 7 取余数。
示例 1:
输入:nums = [2,1,3]
输出:1
解释:我们将 nums 重排, [2,3,1] 能得到相同的 BST 。没有其他得到相同 BST 的方案了。
示例 2:
输入:nums = [3,4,5,1,2]
输出:5
解释:下面 5 个数组会得到相同的 BST:
[3,1,2,4,5]
[3,1,4,2,5]
[3,1,4,5,2]
[3,4,1,2,5]
[3,4,1,5,2]
示例 3:
输入:nums = [1,2,3]
输出:0
解释:没有别的排列顺序能得到相同的 BST 。
示例 4:
输入:nums = [3,1,2,5,4,6]
输出:19
示例 5:
输入:nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]
输出:216212978
解释:得到相同 BST 的方案数是 3216212999。将它对 10^9 + 7 取余后得到 216212978。
提示:
1 <= nums.length <= 1000
1 <= nums[i] <= nums.length
nums 中所有数 互不相同
解题思路
1,这个题目是组合排列+搜索树的组合题目
2,搜索树的性质,左节点<根<右节点
3,我们可以把树拆成左、根、右三部分
4,只要不改变左树内部元素的相对位置和右树内部元素的相对位置,搜索树不变
5,因此变成了排列组合问题
6,假设左树节点为m,右树为n
7,总个数为: C(len(m+n),len(m))*f(m)*f(n)
8,最后还需要把自己剪掉
代码实现
func numOfWays(nums []int) int {
return (getAllCount(nums)%1000000007-1+1000000007)%1000000007
}
func split(nums[]int)([]int,[]int){
var l,r []int
for i:=1;i
if nums[i]
l=append(l,nums[i])
}else{
r=append(r,nums[i])
}
}
return l,r
}
func getAllCount(nums []int) int{
if len(nums)<1{
return 1
}
l,r:=split(nums)
s:=way(len(l),len(r))
return (s*getAllCount(l)%1000000007)*getAllCount(r)%1000000007
}
func way(l,r int)int{
sum:=1
for i:=1;i<=l;i++{
sum=(sum*(r+i)/i)%1000000007
}
return sum
}
感谢各位的阅读!关于“leetcode如何求将子数组重新排序得到同一个二叉查找树的方案数”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!
文章题目:leetcode如何求将子数组重新排序得到同一个二叉查找树的方案数
文章路径:http://pwwzsj.com/article/pgsppp.html