好分区的数目
难度:
标签:
题目描述
You are given an array nums consisting of positive integers and an integer k.
Partition the array into two ordered groups such that each element is in exactly one group. A partition is called great if the sum of elements of each group is greater than or equal to k.
Return the number of distinct great partitions. Since the answer may be too large, return it modulo 109 + 7.
Two partitions are considered distinct if some element nums[i] is in different groups in the two partitions.
Example 1:
Input: nums = [1,2,3,4], k = 4 Output: 6 Explanation: The great partitions are: ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) and ([4], [1,2,3]).
Example 2:
Input: nums = [3,3,3], k = 4 Output: 0 Explanation: There are no great partitions for this array.
Example 3:
Input: nums = [6,6], k = 2 Output: 2 Explanation: We can either put nums[0] in the first partition or in the second partition. The great partitions will be ([6], [6]) and ([6], [6]).
Constraints:
1 <= nums.length, k <= 10001 <= nums[i] <= 109
代码结果
运行时间: 83 ms, 内存: 16.2 MB
import java.util.*;
import java.util.stream.*;
/**
* 使用 Java Stream API 实现的题解。
* 给定一个正整数数组 nums 和一个整数 k。
* 分区的定义是：将数组划分成两个有序的组，并满足每个元素恰好存在于某一个组中。
* 如果分区中每个组的元素和都大于等于 k，则认为分区是一个好分区。
* 返回不同的好分区的数目。由于答案可能很大，请返回对 10^9 + 7 取余后的结果。
*/
public class GoodPartitionsStream {
private static final int MOD = 1_000_000_007;
public int countGoodPartitions(int[] nums, int k) {
int n = nums.length;
return (int) IntStream.range(0, (1 << n))
.filter(mask -> {
long sum1 = IntStream.range(0, n)
.filter(i -> (mask & (1 << i)) != 0)
.mapToLong(i -> nums[i])
.sum();
long sum2 = IntStream.range(0, n)
.filter(i -> (mask & (1 << i)) == 0)
.mapToLong(i -> nums[i])
.sum();
return sum1 >= k && sum2 >= k;
})
.count() % MOD;
}
public static void main(String[] args) {
GoodPartitionsStream solution = new GoodPartitionsStream();
int[] nums1 = {1, 2, 3, 4};
int k1 = 4;
System.out.println(solution.countGoodPartitions(nums1, k1)); // 输出：6
int[] nums2 = {3, 3, 3};
int k2 = 4;
System.out.println(solution.countGoodPartitions(nums2, k2)); // 输出：0
int[] nums3 = {6, 6};
int k3 = 2;
System.out.println(solution.countGoodPartitions(nums3, k3)); // 输出：2
}
}
解释
方法:
这道题解的核心是使用动态规划来确定可以形成好分区的组合数。首先，如果数组总和小于2*k，则不可能形成两个组，每个组的和都至少为k。因此，如果数组和小于2*k，直接返回0。使用一个动态规划数组f，其中f[j]表示通过选择部分元素能够形成和为j的方式数。初始化f[0]=1，表示和为0的方式有一种（即一个元素都不选）。遍历数组中的每个元素x，从k-1向下至x更新f数组，f[j]更新为f[j]和f[j-x]的和，即考虑不选x和选x两种情况。最后，计算所有可能的分区方式，即2的nums长度次方，减去那些不符合好分区的情况（即两个分区中至少有一个的和小于k的情况，这些情况的总数是f数组中从1到k-1的元素的两倍），然后对结果取模。
时间复杂度:
O(n*k)
空间复杂度:
O(k)
代码细节讲解
🦆
在动态规划的过程中，为什么要从k-1向下至x更新数组f？为什么不能从x向上到k-1更新？
▷🦆
动态规划数组f初始化时，f[0]为什么设为1而其他索引的值为0？
▷🦆
如何确保遍历数组元素并更新动态规划数组时，不会出现重复计算同一个元素的情况？
▷🦆
题解中提到的计算不符合好分区的情况，具体是如何计算从1到k-1的元素的两倍的？
▷