{"id":2772,"date":"2018-04-29T03:04:22","date_gmt":"2018-04-29T10:04:22","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2772"},"modified":"2018-10-27T15:06:32","modified_gmt":"2018-10-27T22:06:32","slug":"leetcode-823-binary-trees-with-factors","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-823-binary-trees-with-factors\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 823. Binary Trees With Factors"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 823. Binary Trees With Factors - \u5237\u9898\u627e\u5de5\u4f5c EP186\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/uKNYf170n3s?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1><strong>Problem<\/strong><\/h1>\n<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e9b\u53ef\u4ee5\u91cd\u590d\u4f7f\u7528\u7684\u6570\u5b57\u95ee\u80fd\u591f\u6784\u6210\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u7279\u6b8a\u4e8c\u53c9\u6811\uff08\u6839\u7ed3\u70b9\u7684\u503c\u9700\u4e3a\u5b50\u8282\u70b9\u503c\u7684\u4e58\u79ef\uff09\u3002<\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/binary-trees-with-factors\/description\/\">https:\/\/leetcode.com\/problems\/binary-trees-with-factors\/description\/<\/a><\/p>\n<p>Given an array of unique integers, each integer is strictly greater than 1.<\/p>\n<p>We make a binary tree using these integers\u00a0and each number may be used for any number of times.<\/p>\n<p>Each non-leaf node&#8217;s\u00a0value should be equal to the product of the values of it&#8217;s children.<\/p>\n<p>How many binary trees can we make?\u00a0 Return the answer\u00a0<strong>modulo 10 ** 9 + 7<\/strong>.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input:<\/strong> <code>A = [2, 4]\r\n<\/code><strong>Output:<\/strong> 3 <strong>Explanation:<\/strong> We can make these trees: <code>[2], [4], [4, 2, 2]<\/code><\/pre>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input:<\/strong> <code>A = [2, 4, 5, 10]\r\n<\/code><strong>Output:<\/strong> <code>7\r\n<\/code><strong>Explanation:<\/strong> We can make these trees: <code>[2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2]<\/code>.<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ol>\n<li><code>1 &lt;= A.length &lt;=\u00a01000.<\/code><\/li>\n<li><code>2 &lt;=\u00a0A[i]\u00a0&lt;=\u00a010 ^ 9<\/code>.<\/li>\n<\/ol>\n<h1><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-2785\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/823-ep186.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/823-ep186.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/823-ep186-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/823-ep186-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/h1>\n<h1><strong>Solution: DP<\/strong><\/h1>\n<p>Use dp[i] to denote the number of valid binary trees using the first i + 1 smallest elements and roots at A[i].<\/p>\n<p>dp[i] = sum(dp[j] * dp[i\/j]),\u00a0 0 &lt;= j &lt; i, A[i] is a factor of A[j] and A[i] \/ A[j] also in A.<\/p>\n<pre class=\"crayon:false \">      A[i]\r\n     \/    \\\r\n A[j]  (A[i]\/A[j])\r\n  \/ \\     \/ \\\r\n .....   .....<\/pre>\n<p>ans = sum(dp[i]), for all possible i.<\/p>\n<p>Time complexity: O(n^2)<\/p>\n<p>Space complexity: O(n^2)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 53 ms\r\nclass Solution {\r\npublic:\r\n  int numFactoredBinaryTrees(vector&lt;int&gt;&amp; A) {\r\n    constexpr long kMod = 1000000007;\r\n    std::sort(A.begin(), A.end());\r\n    unordered_map&lt;int, long&gt; dp;\r\n    for (int i = 0; i &lt; A.size(); ++i) {\r\n      dp[A[i]] = 1;\r\n      for (int j = 0; j &lt; i; ++j)\r\n        if (A[i] % A[j] == 0 &amp;&amp; dp.count(A[i] \/ A[j]))\r\n          dp[A[i]] += (dp[A[j]] * dp[A[i] \/ A[j]]) % kMod;\r\n    }    \r\n    long ans = 0;\r\n    for (const auto&amp; kv : dp)\r\n      ans += kv.second;\r\n    return ans % kMod;\r\n  }\r\n};<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Problem \u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e9b\u53ef\u4ee5\u91cd\u590d\u4f7f\u7528\u7684\u6570\u5b57\u95ee\u80fd\u591f\u6784\u6210\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u7279\u6b8a\u4e8c\u53c9\u6811\uff08\u6839\u7ed3\u70b9\u7684\u503c\u9700\u4e3a\u5b50\u8282\u70b9\u503c\u7684\u4e58\u79ef\uff09\u3002 https:\/\/leetcode.com\/problems\/binary-trees-with-factors\/description\/ Given an array of unique integers, each integer is strictly greater than 1. We make a binary tree using these integers\u00a0and each&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46,45],"tags":[18,177,28],"class_list":["post-2772","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","category-tree","tag-dp","tag-medium","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2772","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2772"}],"version-history":[{"count":11,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2772\/revisions"}],"predecessor-version":[{"id":4219,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2772\/revisions\/4219"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2772"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2772"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2772"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}