上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution {
public:
int numOfWays(vector<int>& nums) {
}
};
python3 解法, 执行用时: 112 ms, 内存消耗: 21.3 MB, 提交时间: 2023-10-10 23:46:12
class Solution:
def numOfWays(self, nums: List[int]) -> int:
def dac(arr):
if len(arr) <= 1: return 1
less, more = [], []
for x in arr[1:]: (less if x < arr[0] else more).append(x)
return comb(len(arr) - 1, len(less)) * dac(less) * dac(more) % MOD
MOD = int(1e9) + 7
comb = cache(math.comb)
return (dac(nums) - 1 + MOD) % MOD
java 解法, 执行用时: 88 ms, 内存消耗: 57.4 MB, 提交时间: 2023-10-10 23:44:56
class Solution {
static final int MOD = 1000000007;
long[][] c;
public int numOfWays(int[] nums) {
int n = nums.length;
if (n == 1) {
return 0;
}
c = new long[n][n];
c[0][0] = 1;
for (int i = 1; i < n; ++i) {
c[i][0] = 1;
for (int j = 1; j < n; ++j) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
}
}
TreeNode root = new TreeNode(nums[0]);
for (int i = 1; i < n; ++i) {
int val = nums[i];
insert(root, val);
}
dfs(root);
return (root.ans - 1 + MOD) % MOD;
}
public void insert(TreeNode root, int value) {
TreeNode cur = root;
while (true) {
++cur.size;
if (value < cur.value) {
if (cur.left == null) {
cur.left = new TreeNode(value);
return;
}
cur = cur.left;
} else {
if (cur.right == null) {
cur.right = new TreeNode(value);
return;
}
cur = cur.right;
}
}
}
public void dfs(TreeNode node) {
if (node == null) {
return;
}
dfs(node.left);
dfs(node.right);
int lsize = node.left != null ? node.left.size : 0;
int rsize = node.right != null ? node.right.size : 0;
int lans = node.left != null ? node.left.ans : 1;
int rans = node.right != null ? node.right.ans : 1;
node.ans = (int) (c[lsize + rsize][lsize] % MOD * lans % MOD * rans % MOD);
}
}
class TreeNode {
TreeNode left;
TreeNode right;
int value;
int size;
int ans;
TreeNode(int value) {
this.value = value;
this.size = 1;
this.ans = 0;
}
}
cpp 解法, 执行用时: 388 ms, 内存消耗: 141.4 MB, 提交时间: 2023-10-10 23:44:38
struct TNode {
TNode* left;
TNode* right;
int value;
int size;
int ans;
TNode(int val): left(nullptr), right(nullptr), value(val), size(1), ans(0) {}
};
class Solution {
private:
static constexpr int mod = 1000000007;
vector<vector<int>> c;
public:
void insert(TNode* root, int val) {
TNode* cur = root;
while (true) {
++cur->size;
if (val < cur->value) {
if (!cur->left) {
cur->left = new TNode(val);
return;
}
cur = cur->left;
}
else {
if (!cur->right) {
cur->right = new TNode(val);
return;
}
cur = cur->right;
}
}
}
void dfs(TNode* node) {
if (!node) {
return;
}
dfs(node->left);
dfs(node->right);
int lsize = node->left ? node->left->size : 0;
int rsize = node->right ? node->right->size : 0;
int lans = node->left ? node->left->ans : 1;
int rans = node->right ? node->right->ans : 1;
node->ans = (long long)c[lsize + rsize][lsize] % mod * lans % mod * rans % mod;
}
int numOfWays(vector<int>& nums) {
int n = nums.size();
if (n == 1) {
return 0;
}
c.assign(n, vector<int>(n));
c[0][0] = 1;
for (int i = 1; i < n; ++i) {
c[i][0] = 1;
for (int j = 1; j < n; ++j) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
}
TNode* root = new TNode(nums[0]);
for (int i = 1; i < n; ++i) {
int val = nums[i];
insert(root, val);
}
dfs(root);
return (root->ans - 1 + mod) % mod;
}
};
