福建省建设厅网站林瑞良,北京网页设计公司,阿里巴巴国际站入驻费用及条件,马鞍山网站设计制作目录
题目#xff1a;
示例#xff1a;
分析#xff1a;
代码#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
题目给我们一些元素#xff0c;让我们用这些元素连接形成特定的二叉树#xff0c;每种元素可以使用任意次数#xff0c;形成的二叉树要…目录
题目
示例
分析
代码 题目 示例 分析
题目给我们一些元素让我们用这些元素连接形成特定的二叉树每种元素可以使用任意次数形成的二叉树要求每个非叶子节点的值都为左右子树节点的值的乘积。
一个数要等于两个数的乘积那么那两个数一定会比那一个数更小所以我们可以从较小的数入手那么我们首先将数组从小到大进行排序接着从左到右从小到大去遍历。
在遍历之前我们先做个预处理我们用一个map来存住所有元素的值以元素为键值全部初始化为1。map每个键值对的含义就是以键为根节点能形参的二叉树有多少个因为每个元素都可以以自身一个节点为一棵符合标准的二叉树所以是初始化为1。
初始化完毕就开始遍历我们需要套两层for循环第一层去遍历每个根节点去更新以当前节点为根节点所能形成的二叉树的数量更新的方法就是第二层for循环去遍历比这个节点的值更小的元素因为要相乘等于当前元素那么乘数肯定是比当前元素更小的。
第一层遍历我们设下标为 i 第二层下标为 j 我们去寻找 arr[ i ] / arr[ j ] 这个元素在不在我们的map里如果在那么我们就把map里键为arr[ i ] 的键值对中的值加上以那两个乘数为根节点能形成的二叉树的数量的乘积化简一下就是 m[ arr [ i ] ] m[ arr[ i ] / arr[ j ] ] * m[ arr[ j ] ]。
由于我们是从小到大遍历的所以我们每次都是会更新比后面的数更小的元素以此元素为根节点能形参的二叉树这样就可以得到推导出以后面较大的元素为根节点能形参的二叉树的数量。所以虽然我们没有用到dp数组但它本质上来说还是属于动态规划。
还有一点要注意的就是题目有说要对结果取余10的九次方加7所以为了避免数值溢出我们每次操作都要做一个取余的操作。 代码
class Solution {
public:int numFactoredBinaryTrees(vectorint arr) {int resarr.size(); //单个节点可以单独为一棵树,初始化为数组长度sort(arr.begin(),arr.end());unordered_mapint,longm; //用来记录以每个数为根节点的二叉树数目for(int i:arr){m[i]1;}for(int i0;iarr.size();i){for(int j0;ji;j){//如果发现arr[i]整除arr[j]的数也在数组里,那么可以多组成的二叉树数目等于以arr[j]为根节点的二叉树数目乘上以另一个除数为根节点的二叉树数目.if(arr[i]%arr[j]0m.find(arr[i]/arr[j])!m.end()){int tm[arr[i]/arr[j]]*m[arr[j]]%1000000007;m[arr[i]]t; //更新以arr[i]为根节点的二叉树数目.rest;res%1000000007;}}}return res;}
};
