Re: [閒聊] 每日LeetCode

[z2147483648 (溢傷了喇)]

: https://leetcode.com/problems/binary-trees-with-factors/description/
: 823. Binary Trees With Factors
: 給你一個陣列 arr，裡面的數字不重複且大於 1，我們可以不限制次數的使用這些
: 數字構建出一個二元樹，這個二元樹需要滿足左右節點的值相乘等於父節點，求出
: 共有幾種組合。
: Example 1:
: Input: arr = [2,4]
: Output: 3
: Explanation: We can make these trees: [2], [4], [4, 2, 2]


思路：題目可以解讀成從arr中找到一個數 恰等於 兩個數相乘，

且自己一個數也算一種組合


1.也是想到動態規劃

如果 i = j*k 且 (i,j,k) 都在arr裡面

則 [sum == i的組合] 就多了 [sum == j的組合] * [sum == k的組合]

2.沒有重複的數字，不用考慮重複答案的刪除

3.數字都>1，不用考慮1*自己的case

comb[i] :定義為 sum = i的總組合數

從 i = arr.min() 依序算到 i = arr.max()就可以了


[作法1] comb = [0] * (max(arr)+1)

// 結果MLE

[作法2] 利用map存需要的comb[i]


========== Python

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        comb = {}

        for i in range(len(arr)):
            comb[arr[i]] = 1


        for num in sorted(comb.keys()):
            for j in range(len(arr)):
                if (num <= arr[j]):
                    continue
                elif (num > arr[j] and num % arr[j] == 0 and (num//arr[j] in
comb)):
                    comb[num] += comb[arr[j]] * comb[num//arr[j]]

        summary = 0
        for num, count in comb.items():
            summary += count
        return summary % (10**9+7)


========== C++

C++不像Python，int會爆炸，這邊用long long
==========

class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& arr) {
        # define ll long long
        const int MOD = 1e9+7;
        map<ll, ll> mp;
        for (const auto& num : arr)
        {
            mp[num] = 1;
        }

        for (const auto& [num, count] : mp)
        {
            for (const ll& anum : arr)
            {
                if (num <= anum){}
                else if ((num > anum) && (num % anum == 0) &&
(mp.count(num/anum) == 1))
                {
                    mp[num] += (mp[anum] * mp[num/anum]);
                }
            }
        }

        ll sum = 0;
        for (const auto& [num, count] : mp)
        {
            sum += count;
        }
        return sum % MOD;
    }
};

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.167.12.199 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698344513.A.379.html
→ Rushia: 大師
→ z2147483648: R大才是我的偶像