1569. Number of Ways to Reorder Array to Get Same BST 解題紀錄

Given an array nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elements of nums in order into an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums. For example, given nums = [2,1,3], we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1] also yields the same BST but [3,2,1] yields a different BST. Return the number of ways to reorder nums such that the BST formed is identical to the original BST formed from nums. Since the answer may be very large, return it modulo 109 + 7.   Example 1:
megapx
Input: nums = [2,1,3] Output: 1 Explanation: We can reorder nums to be [2,3,1] which will yield the same BST. There are no other ways to reorder nums which will yield the same BST. Example 2:
megapx
Input: nums = [3,4,5,1,2] Output: 5 Explanation: The following 5 arrays will yield the same BST: [3,1,2,4,5] [3,1,4,2,5] [3,1,4,5,2] [3,4,1,2,5] [3,4,1,5,2] Example 3:
megapx
Input: nums = [1,2,3] Output: 0 Explanation: There are no other orderings of nums that will yield the same BST.   Constraints: 1 <= nums.length <= 1000 1 <= nums[i] <= nums.length All integers in nums are distinct. 這題題目給我們一個"插入順序"nums,長度為 N。 題目想知道還有幾個相同的"插入順序"可以跟這個順序形成一樣的合法二元樹? 這題外圈決定了,是所有合法數量 - 1(因為原始的 nums 占一個插入順序)。 內圈要考慮如何把這個數算出來, 具體來說就是考慮在插入的時候有幾種可能? 把這個可能逐層遞歸回來就是。 我在寫的時候有兩個問題: - 要怎麼降每層計算組合數複雜度? - 要怎麼切分小於及大於的可用元素? 有個方法是做小費馬,但其他方法我想不出來,所以去偷看解答(#。 解第一個問題的訣竅在: 用 pascal 三角形算組合數, pascal[N][K] 等於 CN取K項的係數(完全沒連結過,我以為這是多項式係數)。 第二個問題: 因為這題的 len(nums) <= 1000, 所以可以每層重新切分就好, worst case 總複雜度 O(N^2)。 所以每一層的當下組合數是: CN取K 的組合數 * 小於 nums[i] 的組合數 * 大於 nums[i] 的組合數 這樣去做 DFS 就好了。 C++程式碼:
megapx
計算複雜度:O(N^2) 空間複雜度:O(N^2) -> dfs 跟 pascal 都是 O(N^2) Github程式碼:
MurMur: 每天都覺得腦子不夠用,看到 pascal 表我人都傻了。 這題有些解答能降到 120ms,程式碼邏輯我看是差不多的,所以推測是因為測資改了,不必太焦慮。 明天會記錄禮拜五的 Daily 2916. Subarrays Distinct Element Sum of Squares II, 這題也蠻有趣的。
愛心
86
留言
encourage first comment
有些話想說嗎 快分享出來彼此交流吧!
留言……