一 填表法,计算不同二叉搜索树的数量
给定一个整数 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] 两个数
- 第三步, , 将 入堆,此时堆中有 [3, 4, 5, 6, 10], 取出最小的数 3 作为第3个丑数
- 第四步, 将 入堆,此时堆中有 [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];
}
动态规划的方法显然有着更好地时间界。因而它是一种更优的方案。
我们可以用它解决一类这种问题: 在几个分类里以此挑选“最优”选项的问题。
网友评论