class Solution {
public:
int countPartitions(vector<int>& nums, int k) {
}
};
2518. 好分区的数目
给你一个正整数数组 nums 和一个整数 k 。
分区 的定义是：将数组划分成两个有序的 组 ，并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k ，则认为分区是一个好分区。
返回 不同 的好分区的数目。由于答案可能很大，请返回对 109 + 7 取余 后的结果。
如果在两个分区中，存在某个元素 nums[i] 被分在不同的组中，则认为这两个分区不同。
示例 1：
输入：nums = [1,2,3,4], k = 4 输出：6 解释：好分区的情况是 ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) 和 ([4], [1,2,3]) 。
示例 2：
输入：nums = [3,3,3], k = 4 输出：0 解释：数组中不存在好分区。
示例 3：
输入：nums = [6,6], k = 2 输出：2 解释：可以将 nums[0] 放入第一个分区或第二个分区中。 好分区的情况是 ([6], [6]) 和 ([6], [6]) 。
提示：
1 <= nums.length, k <= 10001 <= nums[i] <= 109原站题解
python3 解法, 执行用时: 176 ms, 内存消耗: 15.1 MB, 提交时间: 2023-01-03 11:52:06
class Solution:
def countPartitions(self, nums: List[int], k: int) -> int:
if sum(nums) < k * 2: return 0
MOD = 10 ** 9 + 7
f = [0] * k
f[0] = 1
for x in nums:
for j in range(k - 1, x - 1, -1):
f[j] = (f[j] + f[j - x]) % MOD
return (pow(2, len(nums), MOD) - sum(f) * 2) % MOD
java 解法, 执行用时: 3 ms, 内存消耗: 41.1 MB, 提交时间: 2023-01-03 11:51:37
class Solution {
private static final int MOD = (int) 1e9 + 7;
public int countPartitions(int[] nums, int k) {
var sum = 0L;
for (var x : nums) sum += x;
if (sum < k * 2) return 0;
var ans = 1;
var f = new int[k];
f[0] = 1;
for (var x : nums) {
ans = ans * 2 % MOD;
for (var j = k - 1; j >= x; --j)
f[j] = (f[j] + f[j - x]) % MOD;
}
for (var x : f)
ans = (ans - x * 2 % MOD + MOD) % MOD; // 保证答案非负
return ans;
}
}
golang 解法, 执行用时: 8 ms, 内存消耗: 2.5 MB, 提交时间: 2023-01-03 11:51:06
func countPartitions(nums []int, k int) int {
const mod int = 1e9 + 7
sum := 0
for _, x := range nums {
sum += x
}
if sum < k*2 {
return 0
}
ans := 1
f := make([]int, k)
f[0] = 1
for _, x := range nums {
ans = ans * 2 % mod
for j := k - 1; j >= x; j-- {
f[j] = (f[j] + f[j-x]) % mod
}
}
for _, x := range f {
ans -= x * 2
}
return (ans%mod + mod) % mod // 保证答案非负
}
cpp 解法, 执行用时: 12 ms, 内存消耗: 7.6 MB, 提交时间: 2023-01-03 11:50:44
class Solution {
const int MOD = 1e9 + 7;
public:
int countPartitions(vector<int> &nums, int k) {
if (accumulate(nums.begin(), nums.end(), 0L) < k * 2) return 0;
int ans = 1, f[k]; memset(f, 0, sizeof(f));
f[0] = 1;
for (int x : nums) {
ans = ans * 2 % MOD;
for (int j = k - 1; j >= x; --j)
f[j] = (f[j] + f[j - x]) % MOD;
}
for (int x : f)
ans = (ans - x * 2 % MOD + MOD) % MOD; // 保证答案非负
return ans;
}
};