美丽子集的数目
难度:
标签:
题目描述
You are given an array nums of positive integers and a positive integer k.
A subset of nums is beautiful if it does not contain two integers with an absolute difference equal to k.
Return the number of non-empty beautiful subsets of the array nums.
A subset of nums is an array that can be obtained by deleting some (possibly none) elements from nums. Two subsets are different if and only if the chosen indices to delete are different.
Example 1:
Input: nums = [2,4,6], k = 2 Output: 4 Explanation: The beautiful subsets of the array nums are: [2], [4], [6], [2, 6]. It can be proved that there are only 4 beautiful subsets in the array [2,4,6].
Example 2:
Input: nums = [1], k = 1 Output: 1 Explanation: The beautiful subset of the array nums is [1]. It can be proved that there is only 1 beautiful subset in the array [1].
Constraints:
1 <= nums.length <= 201 <= nums[i], k <= 1000
代码结果
运行时间: 45 ms, 内存: 16.0 MB
/*
* 思路：
* 1. 使用Java Stream的组合生成所有子集。
* 2. 过滤掉不满足美丽子集条件的子集。
* 3. 计算剩余子集的数量。
*/
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class BeautifulSubsetsStream {
public static int countBeautifulSubsets(int[] nums, int k) {
int n = nums.length;
// 生成所有非空子集并判断是否为美丽子集
return (int) IntStream.range(1, 1 << n)
.mapToObj(i -> IntStream.range(0, n)
.filter(j -> (i & (1 << j)) != 0)
.mapToObj(j -> nums[j])
.collect(Collectors.toList()))
.filter(subset -> isBeautifulSubset(subset, k))
.count();
}
private static boolean isBeautifulSubset(List<Integer> subset, int k) {
for (int i = 0; i < subset.size(); i++) {
for (int j = i + 1; j < subset.size(); j++) {
if (Math.abs(subset.get(i) - subset.get(j)) == k) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
int[] nums1 = {2, 4, 6};
int k1 = 2;
System.out.println(countBeautifulSubsets(nums1, k1)); // 输出：4
int[] nums2 = {1};
int k2 = 1;
System.out.println(countBeautifulSubsets(nums2, k2)); // 输出：1
}
}解释
方法:
题解的核心思想是通过模 k 的分组来识别可能的冲突，即当两个数的差为 k 时，它们在同一个模 k 的组内的位置之间相差 1。算法首先通过模 k 对 nums 中的数字进行分组，并使用 Counter 来统计同一组内每个数出现的次数。对每个组内的数字进行排序，然后使用动态规划计算每组内可以形成的美丽子集数目。对于每组，如果两个数之间的差为 k，则在计算子集时需要考虑不选取前一个数的情况。最后，所有组的子集数目相乘（去除空集的情况）即为结果。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
算法中提到的`模 k 的分组`是如何帮助识别可能冲突的？具体是如何通过模 k 的值来分组的？
▷🦆
题解中提到使用动态规划来计算每个组的美丽子集数目，能否详细解释这个动态规划过程中状态转移的逻辑？特别是`f[i+1] = f[i] + f[i-1] * (2**g[i][1]-1)`这一步。
▷🦆
在计算子集时，为什么要特别处理当两个数之间的差为 k 的情况？这种处理方式是如何避免选择导致非美丽子集的数的？
▷