【归并排序】【图论】【动态规划】【 深度游戏搜索】1569将子数组重新排序得到同一个二叉搜索树的方案数

简介: 【归并排序】【图论】【动态规划】【 深度游戏搜索】1569将子数组重新排序得到同一个二叉搜索树的方案数

本文涉及知识点

动态规划汇总

图论 深度游戏搜索 归并排序 组合

LeetCoce1569将子数组重新排序得到同一个二叉搜索树的方案数

给你一个数组 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 。

提示:

1 <= nums.length <= 1000

1 <= nums[i] <= nums.length

nums 中所有数 互不相同 。

归并排序

原以为必须用归并排序的思想,其实可以不用归并排序。

原理

对每棵树(子树),只讨论左子树和右子树之间的顺序,不讨论子树内部的顺序。

a,根节点必定是第一个。

b,混略内部顺序后,左子树的节点完全相同,假定其为ln个;右子树的节点也相同,假定其为rn个。就是组合C m + n n \Large C_{m+n}^nCm+nn

DFS 各子树 的结果相乘。

动态规划的状态表示

每个子树的范围是确定,比如:根节点的范围为[1,n],左子树[1,nums[0]-1] 右子树[nums[0],n]。每根子树,需要三个子状态:最小值(iMin),最大值(iMax),根节点的值(nums[iRoot])。 由于1到n,都出现且只出现一次,所以此子树的节点数为:最大值-最小值+1。

动态规划的转移方程

左树:iMin,nums[iRoot]-1, nums(iRoot…]中第一个在左树范围的小标。

右树:,nums[iRoot]+1,iMax,nums(iRoot…]中第一个在右树范围的小标。

动态规划的填表顺

深度优先,从根节点开始。

动态规划的返回值

dfs(1,n,0)-1。

代码

核心代码

template<int MOD = 1000000007>
class C1097Int
{
public:
  C1097Int(long long llData = 0) :m_iData(llData% MOD)
  {
  }
  C1097Int  operator+(const C1097Int& o)const
  {
    return C1097Int(((long long)m_iData + o.m_iData) % MOD);
  }
  C1097Int& operator+=(const C1097Int& o)
  {
    m_iData = ((long long)m_iData + o.m_iData) % MOD;
    return *this;
  }
  C1097Int& operator-=(const C1097Int& o)
  {
    m_iData = (m_iData + MOD - o.m_iData) % MOD;
    return *this;
  }
  C1097Int  operator-(const C1097Int& o)
  {
    return C1097Int((m_iData + MOD - o.m_iData) % MOD);
  }
  C1097Int  operator*(const C1097Int& o)const
  {
    return((long long)m_iData * o.m_iData) % MOD;
  }
  C1097Int& operator*=(const C1097Int& o)
  {
    m_iData = ((long long)m_iData * o.m_iData) % MOD;
    return *this;
  }
  bool operator<(const C1097Int& o)const
  {
    return m_iData < o.m_iData;
  }
  C1097Int pow(long long n)const
  {
    C1097Int iRet = 1, iCur = *this;
    while (n)
    {
      if (n & 1)
      {
        iRet *= iCur;
      }
      iCur *= iCur;
      n >>= 1;
    }
    return iRet;
  }
  C1097Int PowNegative1()const
  {
    return pow(MOD - 2);
  }
  int ToInt()const
  {
    return m_iData;
  }
private:
  int m_iData = 0;;
};
template<class Result = C1097Int<> >
class CCombination
{
public:
  CCombination()
  {
    m_v.assign(1, vector<Result>(1,1));
  }
  Result Get(int sel, int total)
  {
    while (m_v.size() <= total)
    {
      int iSize = m_v.size();
      m_v.emplace_back(iSize + 1, 1);
      for (int i = 1; i < iSize; i++)
      {
        m_v[iSize][i] = m_v[iSize - 1][i] + m_v[iSize - 1][i - 1];
      }
    }
    return m_v[total][sel];
  }
protected:
  vector<vector<Result>> m_v;
};
class Solution {
public:
  int numOfWays(vector<int>& nums) {
    m_nums = nums;
    return (DFS(1, nums.size(), 0) - 1).ToInt();
  }
  C1097Int<> DFS(int iMin, int iMax, int iRoot)
  {
    int iLeftRoot = -1, iRightRoot = -1;
    for (int i = (int)m_nums.size()-1; i > iRoot; i--)
    {
      if ((m_nums[i] < m_nums[iRoot])&&(m_nums[i] >= iMin ))
      {
        iLeftRoot = i;
      }
      if ((m_nums[i] > m_nums[iRoot])&& (m_nums[i] <= iMax))
      {
        iRightRoot = i;
      }
    }
    C1097Int<> biRet = m_com.Get(m_nums[iRoot]-iMin,iMax-iMin);
    if (-1 != iLeftRoot)
    {
      biRet *= DFS(iMin, m_nums[iRoot] - 1, iLeftRoot);
    }
    if (-1 != iRightRoot)
    {
      biRet *= DFS(m_nums[iRoot] + 1,iMax, iRightRoot);
    }
    return biRet;
  }
  vector<int> m_nums;
  CCombination<> m_com;
};

2023年6月

class Solution {

public:

int numOfWays(vector& nums) {

m_vFact.emplace_back(1);

for (int i = 1; i < nums.size(); i++)

{

m_vFact.emplace_back(m_vFact.back()*i);

}

for (const auto& i : m_vFact )

{

m_vRevFact.emplace_back(i.PowNegative1());

}

return (Rev(nums) - 1).ToInt();

}

C1097Int<> Rev(vector& nums)

{

if (0 == nums.size())

{

return 1;

}

vector vLeft, vRight;

for (int i = 1; i < nums.size(); i++)

{

const int& n = nums[i];

if (n < nums[0])

{

vLeft.emplace_back(n);

}

else

{

vRight.emplace_back(n);

}

}

C1097Int<> iRet = m_vFact[vLeft.size() + vRight.size()] * m_vRevFact[vLeft.size()] * m_vRevFact[vRight.size()];

return iRet * Rev(vLeft) * Rev(vRight);

}

vector<C1097Int<>> m_vFact, m_vRevFact;

};


相关文章
|
1月前
|
人工智能 算法 测试技术
【动态规划】【二分查找】C++算法 466 统计重复个数
【动态规划】【二分查找】C++算法 466 统计重复个数
|
1月前
|
算法 测试技术 C++
【动态规划】【离线查询】【前缀和】689. 三个无重叠子数组的最大和
【动态规划】【离线查询】【前缀和】689. 三个无重叠子数组的最大和
|
8月前
|
算法
代码随想录 Day26 贪心 01 全集 LeetCode455 分发饼干 LeetCodeT346摆动序列 LeetCdoe T53 最大子数组和
代码随想录 Day26 贪心 01 全集 LeetCode455 分发饼干 LeetCodeT346摆动序列 LeetCdoe T53 最大子数组和
24 0
|
1月前
|
算法 测试技术 C#
【并集查找 图论 位运算】3108. 带权图里旅途的最小代价
【并集查找 图论 位运算】3108. 带权图里旅途的最小代价
|
5天前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
21天前
|
算法
DAY-7 | 牛客-BM21 寻找旋转数组的最小元素:二分法分治思想真的很可靠
这是一个关于编程题目的摘要:题目是牛客网上的&quot;BM21 旋转数组的最小数字&quot;,要求找到旋转数组中的最小数字。题解介绍了使用二分查找算法来解决此问题,因为其时间复杂度优于暴力搜索的线性时间复杂度。二分查找的核心是通过比较中间元素与右端元素的大小,不断缩小搜索范围,最终找到最小值。代码示例展示了如何实现这个算法。总结中强调了二分查找适用于部分有序数组,并指出了解决这类问题的关键在于理解数组的二段单调性。
31 1
|
1月前
leetcode代码记录(二叉树的最小深度
leetcode代码记录(二叉树的最小深度
14 0
|
1月前
|
存储 算法 搜索推荐
【算法训练-排序算法 三】【排序应用】合并区间
【算法训练-排序算法 三】【排序应用】合并区间
56 0
|
1月前
|
算法
Acwing.786 第k个数(图解快速选择算法)
Acwing.786 第k个数(图解快速选择算法)
|
1月前
|
人工智能 算法 BI
【树】【因子数】【数论】【深度优先搜索】2440. 创建价值相同的连通块
【树】【因子数】【数论】【深度优先搜索】2440. 创建价值相同的连通块

热门文章

最新文章