织梦手机网站教程视频,高校网站设计方案,ico加网站,做调查挣钱的网站目录
823. 带因子的二叉树
题目描述#xff1a;
实现代码与解析#xff1a;
dp hash
原理思路#xff1a; 823. 带因子的二叉树
题目描述#xff1a; 给出一个含有不重复整数元素的数组 arr #xff0c;每个整数 arr[i] 均大于 1。
用这些整数来构建二叉树#x…目录
823. 带因子的二叉树
题目描述
实现代码与解析
dp hash
原理思路 823. 带因子的二叉树
题目描述 给出一个含有不重复整数元素的数组 arr 每个整数 arr[i] 均大于 1。
用这些整数来构建二叉树每个整数可以使用任意次数。其中每个非叶结点的值应等于它的两个子结点的值的乘积。
满足条件的二叉树一共有多少个答案可能很大返回 对 109 7 取余 的结果。
示例 1:
输入: arr [2, 4]输出: 3
解释: 可以得到这些二叉树: [2], [4], [4, 2, 2]
示例 2:
输入: arr [2, 4, 5, 10]输出: 7解释: 可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].提示
1 arr.length 10002 arr[i] 109arr 中的所有值 互不相同
实现代码与解析
dp hash
class Solution {
public:int mod 1e9 7;int numFactoredBinaryTrees(vectorint arr) {unordered_maplong, long f; // 以 first 为根的种类为 secondsort(arr.begin(), arr.end());for (auto t: arr) f[t] 1;for (int i 0; i arr.size(); i){for (int j 0; j i; j){long long x arr[i], y arr[j];if (x % y 0 f.count(x / y)) f[x] f[y] * f[x / y] % mod;}}long res 0;for (auto [a, b]: f)res (res b) % mod;return res;}
};
原理思路 dp含义以 first 为 根 的种类为 second。 这里为什么没用数组来存dp呢如果我们这里用数组存后面要判断一个数的因数是否存在arr中也要再定义一个hash等于说这个map其两个作用一个是dp一个是hash。当然也可以不用hash用双指针或者二分也可以找到。 遍历顺序肯定是从树底到顶也就是从小到大排序后开始遍历。 若x 可整除 y 并且 两个因数y , x / y都在arr中那么f[ i ] f[x] f[y] * f[x / y]; 种类是子树种类乘积 最后sum一下即可。
