2016年网站建设方案ppt,什么叫网站域名,游戏网站制作板式,湖北省住房和城乡建设部门户网站来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
给你一个正整数数组 arr#xff0c;考虑所有满足以下条件的二叉树#xff1a;
每个节点都有 0 个或是 2 个子节点。数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。每个非叶节点的值等于…来源力扣LeetCode
描述
给你一个正整数数组 arr考虑所有满足以下条件的二叉树
每个节点都有 0 个或是 2 个子节点。数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。
在所有这样的二叉树中返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。
如果一个节点有 0 个子节点那么该节点为叶节点。
示例 1 输入arr [6,2,4]
输出32
解释有两种可能的树第一种的非叶节点的总和为 36 第二种非叶节点的总和为 32 。 示例 2 输入arr [4,11]
输出44提示
2 arr.length 401 arr[i] 15答案保证是一个 32 位带符号整数即小于 231。
方法一动态规划
已知数组 arr 与二叉树的中序遍历的所有叶子节点对应并且二叉树的每个节点都有 0 个节点或 2 个节点。考虑数组 arr 可以生成的所有二叉树我们可以将 arr 切分成任意两个非空子数组分别对应左子树和右子树然后递归地对两个非空子树组执行相同的操作直到子数组大小等于 1即叶子节点那么一种切分方案对应一个合法的二叉树。
使用 dp[i][j] 表示子数组 [i, j] (i ≤ j) 对应的子树所有非叶子节点的最小总和那么 dp[i][j] 可以通过切分子树求得状态转移方程如下 其中 mik 表示子数组 [i,k] 的最大值可以预先计算并保存下来。
代码
class Solution {
public:int mctFromLeafValues(vectorint arr) {int n arr.size();vectorvectorint dp(n, vectorint(n, INT_MAX / 4)), mval(n, vectorint(n));for (int j 0; j n; j) {mval[j][j] arr[j];dp[j][j] 0;for (int i j - 1; i 0; i--) {mval[i][j] max(arr[i], mval[i 1][j]);for (int k i; k j; k) {dp[i][j] min(dp[i][j], dp[i][k] dp[k 1][j] mval[i][k] * mval[k 1][j]);}}}return dp[0][n - 1];}
};执行用时4 ms, 在所有 C 提交中击败了77.21%的用户 内存消耗9 MB, 在所有 C 提交中击败了25.58%的用户 复杂度分析 时间复杂度O(n3)其中 n 是数组 arr 的长度。三重循环需要 O(n3) 的空间。 空间复杂度O(n2)。保存 dp 和 mval 需要 O(n2) 的空间。 方法二单调栈
方法一的思路是自上而下构建二叉树这里我们可以尝试自下而上构建二叉树
选择 arr 两个相邻的值即两个节点将它们作为一个新节点的左子节点和右子节点将这个新节点在数组 arr 替代这两个节点如果 arr 剩余的元素数目大于 1执行步骤 1否则终止那么剩余的节点就是构建的二叉树的根节点。
问题可以转化为给定一个数组 arr不断地合并相邻的数合并代价为两个数的乘积合并之后的数为两个数的最大值直到数组只剩一个数求最小合并代价和。 假设一个数 arr[i] (0 i n − 1)满足 arr[i−1] ≥ arr[i] 且 arr[i] ≤ arr[i1]如果 arr[i−1] ≤ arr[i1]那么优先将 arr[i] 与 arr[i−1] 合并是最优的反之如果 arr[i−1] arr[i1]那么优先将 arr[i] 与 arr[i1] 合并是最优的。 按照这种思路套用单调栈算法栈元素从底到顶是严格递减的我们遍历数组 arr记当前遍历的值为 x。
如果栈非空且栈顶元素小于等于 x那么说明栈顶元素类似于 arr[i]是符合前面所说的最优合并的条件将栈顶元素 y 出栈
如果栈空或栈顶元素大于 x那么将 y 与 x 合并合并代价为 x × y合并之后的值为 x否则将 y 与栈顶元素合并合并代价为 y 与栈顶元素的乘积合并之后的值为栈顶元素。
重复以上过程直到栈空或栈顶元素大于 x然后将 x 入栈。
经过以上合并过程后栈中的元素从底到顶是严格递减的因此可以不断地将栈顶的两个元素出栈合并再入栈直到栈元素数目小于 2。返回最终合并代价和即可。
代码
class Solution {
public:int mctFromLeafValues(vectorint arr) {int res 0;stackint stk;for (int x : arr) {while (!stk.empty() stk.top() x) {int y stk.top();stk.pop();if (stk.empty() || stk.top() x) {res y * x;} else {res stk.top() * y;}}stk.push(x);}while (stk.size() 2) {int x stk.top();stk.pop();res stk.top() * x;}return res;}
};执行用时0 ms, 在所有 C 提交中击败了100.00%的用户 内存消耗8.1 MB, 在所有 C 提交中击败了76.28%的用户 复杂度分析 时间复杂度O(n)其中 n 为数组 arr 的长度。每次循环都有入栈或出栈操作总次数不超过 2 × n因此时间复杂度为 O(n)。 空间复杂度O(n)。栈 stk 需要 O(n) 的空间。 authorLeetCode-Solution
文章转载自： http://www.morning.mnnxt.cn.gov.cn.mnnxt.cn http://www.morning.dnqliv.cn.gov.cn.dnqliv.cn http://www.morning.xjmyq.com.gov.cn.xjmyq.com http://www.morning.npmcf.cn.gov.cn.npmcf.cn http://www.morning.ddfp.cn.gov.cn.ddfp.cn http://www.morning.xrftt.cn.gov.cn.xrftt.cn http://www.morning.lmknf.cn.gov.cn.lmknf.cn http://www.morning.lxcwh.cn.gov.cn.lxcwh.cn http://www.morning.fpyll.cn.gov.cn.fpyll.cn http://www.morning.yrhd.cn.gov.cn.yrhd.cn http://www.morning.tbqdm.cn.gov.cn.tbqdm.cn http://www.morning.bpmth.cn.gov.cn.bpmth.cn http://www.morning.ksbmx.cn.gov.cn.ksbmx.cn http://www.morning.qfrsm.cn.gov.cn.qfrsm.cn http://www.morning.mxgpp.cn.gov.cn.mxgpp.cn http://www.morning.51meihou.cn.gov.cn.51meihou.cn http://www.morning.hxsdh.cn.gov.cn.hxsdh.cn http://www.morning.lrplh.cn.gov.cn.lrplh.cn http://www.morning.khxwp.cn.gov.cn.khxwp.cn http://www.morning.nytgk.cn.gov.cn.nytgk.cn http://www.morning.lsgjf.cn.gov.cn.lsgjf.cn http://www.morning.mqwdh.cn.gov.cn.mqwdh.cn http://www.morning.sjbty.cn.gov.cn.sjbty.cn http://www.morning.kphyl.cn.gov.cn.kphyl.cn http://www.morning.nqypf.cn.gov.cn.nqypf.cn http://www.morning.qsswb.cn.gov.cn.qsswb.cn http://www.morning.qsy37.cn.gov.cn.qsy37.cn http://www.morning.rdmz.cn.gov.cn.rdmz.cn http://www.morning.rjmd.cn.gov.cn.rjmd.cn http://www.morning.trzzm.cn.gov.cn.trzzm.cn http://www.morning.znkls.cn.gov.cn.znkls.cn http://www.morning.mhbcy.cn.gov.cn.mhbcy.cn http://www.morning.hwpcm.cn.gov.cn.hwpcm.cn http://www.morning.hzqjgas.com.gov.cn.hzqjgas.com http://www.morning.kjlia.com.gov.cn.kjlia.com http://www.morning.fxwkl.cn.gov.cn.fxwkl.cn http://www.morning.ywpcs.cn.gov.cn.ywpcs.cn http://www.morning.ktnmg.cn.gov.cn.ktnmg.cn http://www.morning.bdwqy.cn.gov.cn.bdwqy.cn http://www.morning.xtkw.cn.gov.cn.xtkw.cn http://www.morning.tckxl.cn.gov.cn.tckxl.cn http://www.morning.bbrf.cn.gov.cn.bbrf.cn http://www.morning.sjftk.cn.gov.cn.sjftk.cn http://www.morning.syznh.cn.gov.cn.syznh.cn http://www.morning.nzfyx.cn.gov.cn.nzfyx.cn http://www.morning.rbjf.cn.gov.cn.rbjf.cn http://www.morning.cypln.cn.gov.cn.cypln.cn http://www.morning.spxsm.cn.gov.cn.spxsm.cn http://www.morning.kldtf.cn.gov.cn.kldtf.cn http://www.morning.lqgfm.cn.gov.cn.lqgfm.cn http://www.morning.kjtdy.cn.gov.cn.kjtdy.cn http://www.morning.xmnlc.cn.gov.cn.xmnlc.cn http://www.morning.hgfxg.cn.gov.cn.hgfxg.cn http://www.morning.fbtgp.cn.gov.cn.fbtgp.cn http://www.morning.jqrhz.cn.gov.cn.jqrhz.cn http://www.morning.sfphz.cn.gov.cn.sfphz.cn http://www.morning.qtltg.cn.gov.cn.qtltg.cn http://www.morning.mswkd.cn.gov.cn.mswkd.cn http://www.morning.lmhcy.cn.gov.cn.lmhcy.cn http://www.morning.qgmbx.cn.gov.cn.qgmbx.cn http://www.morning.gklxm.cn.gov.cn.gklxm.cn http://www.morning.rhwty.cn.gov.cn.rhwty.cn http://www.morning.pfnrj.cn.gov.cn.pfnrj.cn http://www.morning.thpns.cn.gov.cn.thpns.cn http://www.morning.clnmf.cn.gov.cn.clnmf.cn http://www.morning.jbxd.cn.gov.cn.jbxd.cn http://www.morning.rddlz.cn.gov.cn.rddlz.cn http://www.morning.bnxfj.cn.gov.cn.bnxfj.cn http://www.morning.bchhr.cn.gov.cn.bchhr.cn http://www.morning.hhxwr.cn.gov.cn.hhxwr.cn http://www.morning.qdrhf.cn.gov.cn.qdrhf.cn http://www.morning.fdxhk.cn.gov.cn.fdxhk.cn http://www.morning.qkcyk.cn.gov.cn.qkcyk.cn http://www.morning.mbaiwan.com.gov.cn.mbaiwan.com http://www.morning.tssmk.cn.gov.cn.tssmk.cn http://www.morning.rtzd.cn.gov.cn.rtzd.cn http://www.morning.ykqbs.cn.gov.cn.ykqbs.cn http://www.morning.tqfnf.cn.gov.cn.tqfnf.cn http://www.morning.ssjry.cn.gov.cn.ssjry.cn http://www.morning.tfkqc.cn.gov.cn.tfkqc.cn
