Re: [閒聊] 每日LeetCode

[ZooseWu (動物園 公告)]

※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 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裡面

有的話就把兩個child的可能性乘起來


另外宣告一個Set

可以讓判斷乘數有沒有在陣列中的時候不用再找整個陣列一次

因為Set的時間複雜度是O(1)


原本想說可以不用理會乘數跟被乘數交換的狀況

反正最終都會輪到

但是後來看了別人的解答後

發現我沒有考慮到數字很大的情況下

n跟sqrt(n)會差很大

有加上這個判斷可以讓時間複雜度從O(n^2)降到O(n*sqrt(n))


TS code:

function numFactoredBinaryTrees (arr: number[]): number {
  const sortedArr = arr.sort((a, b) => (a - b))
  const set = new Set(sortedArr)
  const dp: number[] = new Array(arr.length)
  for (let i = 0; i < sortedArr.length; i++) {
    const element = sortedArr[i]
    dp[i] = 1
    for (let j = 0; j < i; j++) {
      const lChild = sortedArr[j];
      if (lChild > Math.sqrt(element)) break
      if (element % lChild === 0) {
        const rChild = element / lChild
        if (rChild === lChild) {
          dp[i] = (dp[i] + dp[j] * dp[j]) % 1000000007
        } else if (set.has(rChild)) {
          dp[i] = (dp[i] + dp[j] * dp[sortedArr.indexOf(rChild)] * 2) %
1000000007
        }
      }
    }
  }
  let result = 0
  for (let i = 0; i < dp.length; i++) {
    const dpItem = dp[i]
    result = (result + dpItem) % 1000000007
  }
  return result
}

--
                                                                    Zoosewu
                              Yoututbe顯示PTT推文
                       可以在各個網站追實況或Live時使用
預覽圖: https://i.imgur.com/ZhtXdAJ.png https://i.imgur.com/WqbLNV3.png
完整介紹: https://github.com/zoosewu/PTTChatOnYoutube/tree/master/homepage
支援的網站: Youtube Twitch Holotools Niji-mado Holodex

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698380230.A.F4C.html