一 填表法，计算不同二叉搜索树的数量
给定一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
本题可以假设 n 个节点有排序，因为互不相同，存在等价性。
也就是：
- 如果 有两组不同的节点，数量相同，那么它们组成的二叉搜索树的种类是一样的。
对于一种特殊的情况: 有三个不同节点。
那么分别选定 ,
,
, 以他们为根节点的二叉搜索树被划分成两部分
- 情况1
空集和
- 情况2
分成
和
- 情况3
和 空集
所有的种类为 三种情况的加和，其中情况1 和情况 3 是等价的。而情况是两种子情况的乘积。
推到一般情况，我们发现问题可以被分解成一系列字问题
表达成数学递推式子为
简而言之， 能决定
因而可以逐步求得 —— 如果使用自顶向下递归，将会产生大量的重复子问题，计算效率极慢。但是用自底向上逐步求解，则每个
可以在期望运行时间
内求得，整个算法的效率时间界是
C++ 代码
int num_of_trees(int n) {
vector<int> table(n + 1);
table[0] = 1;
for (int i = 1; i <= n; ++i) {
int s = 0;
for (int j = 0; j < i; ++j) {
s += table[j] * table[i - j - 1];
}
table[i] = s;
}
return table[n];
}
注意这个结果在n增长到20左右时会膨胀得特别快，因而 32 位整数可能无法容纳最后的结果。实际应用中需要严格考虑数据类型的表达范围。
丑数
丑数是只包含质因数 2、3 和/或 5 的正整数。1 定义为丑数。
我们怎么推演出丑数表。
丑数表的前 10项为：
1, 2, 3, 4, 5, 6, 8, 9,10, 12, 15, 16, 18, ...
一种用最小堆的方案是，每次采取一定的规律生成2, 3 ,5 的倍数，存储起来，由于“这个规律”不太能保证绝对的大小顺序，因而使用最小堆存取新丑数。
一边存，一边取，迭代 n 次后我们计算出来 第n 个丑数
算法要保证每次都有数可取, 并且下一个丑数能及时存入堆中。
我们稍微推演一下：
- 第一步，将
作为第一个丑数
- 第二步，分别将
的 2, 3 ,5 倍
, 它们一定都是丑数，加入到堆中，然后从堆中取出最小的数 2 作为第 2 个丑数，
, 此时堆中仍有 [3, 5] 两个数
- 第三步，
, 将
- 第四步，
将
入堆，此时堆中有 [4, 5, 6, 6, 9, 10, 15] 我们发现出现了重复数 6，因此需要有一个哈希表来去重，去重以后，堆中元素为 [4, 5, 6, 9, 10, 15]
... 以此类推。
很明显，上面这种入堆的方案不会遗漏任何丑数。其次，通过n 步之后，堆中的丑数数量远远大于 n 个，但是不超过 3n个(因为有一些重复数) ， 并且 n 次迭代后， 前 n 个丑数已经出现。因为下一次最小的丑数是 的两倍 。
这个算法可以在 O(nlogn) 的复杂度下计算出第 n 个丑数。
算法多计算了大概 3 倍规模的丑数
int nthUglyNumber(int n) {
vector<int> factors{2, 3, 5};
unordered_set<long> table; // 哈希表用于去重
priority_queue<long, vector<long>, greater<long> > heap; // std库的默认堆是最大堆，因此需要声明 greater<long> 参数
table.insert(1L);
heap.push(1L);
int ugly_n = 0;
for (int i = 0; i < n; ++i) {
ugly_n = heap.top();
heap.pop();
for (int factor: factors) {
long next = (long)ugly_n * factor;
if (table.count(next) == 0) {
table.insert(next);
heap.push(next);
}
}
}
return ugly_n;
}
动态规划解法
我们分别列出 2,3,5 的倍数列表
2n —— [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30,....]
3n —— [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, ...]
5n —— [5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, ...]
列表中有些数是丑数，有些不是，但是，理论上，所有的丑数都会至少出现在其中之一上。
我们从上面的列表中筛选出丑数，得到下面的丑数表
2n A —— [2,4,6, 8,10,12,16,18,20,24,30, ....]
3n B—— [3,6,9,12,15,18,24,27,30,36,...]
5n C—— [5,10,15,20,25,30,40, 45, 50, ....]
假设我们知道了第 n 个丑数是 ， 那么第 n + 1 个丑数
就是
三个数组中没有被用过的最小的数。
用三个循环子p1, p2, p3 分别代表三个数组中当前元素，对于每个 数组，必然有
采用动态规划的思想，假设我们已经得到了 前面的 n - 1 个丑数 ，并且当前循环子分别落在 p1, p2, p3 的位置，由上面的推导，我们知道丑数 和
中的一个或多个相等，把和
相等的循环子向后移动一格(有可能要移动两个或三个), 不妨设
与
相等。
那么 ，有
其它几种情况
写成C++代码
int nthUglyNumber(int n) {
int i1 = 1, i2 = 1, i3 = 1;
vector<int> dp(n + 1);
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
int _2x = dp[i1] * 2;
int _3x = dp[i2] * 3;
int _5x = dp[i3] * 5;
int x = min(min(_2x, _3x), _5x);
dp[i] = x;
if (x == _2x) {
i1++;
}
if (x == _3x) {
i2++;
}
if (x == _5x) {
i3++;
}
}
return dp[n];
}
动态规划的方法显然有着更好地时间界。因而它是一种更优的方案。
我们可以用它解决一类这种问题： 在几个分类里以此挑选“最优”选项的问题。
网友评论