统计 K-Free 子集的总数

Submission

运行时间: 46 ms

内存: 16.1 MB

class Solution:
    def countTheNumOfKFreeSubsets(self, nums: List[int], k: int) -> int:
        nums.sort()
        count_nums = defaultdict(list)

        for num in nums:
            count_nums[num%k].append(num)
        
        ans = 1 
        for count_num in count_nums.values():
            dp = [0] * len(count_num)
            dp[0] = 2 
            for j in range(1, len(count_num)):
                if count_num[j] - count_num[j-1] == k:
                    dp[j] = dp[j-1]+dp[j-2] if j > 1 else dp[j-1] + 1 
                else:
                    dp[j] = 2 * dp[j-1]
            ans *= dp[-1]
        return ans

Explain

题解的思路是将数组中的数字根据它们除以k的余数进行分类，存储在字典中，其中键是余数，值是具有相同余数的数字列表。对于每个余数类别，使用动态规划计算可能的子集数量。动态规划数组dp记录了当前长度的子序列可以形成的'k-free'子集数量。如果两个相邻数字之差等于k，则该子集可以选择包含或不包含前一个数字，否则可以自由选择包含任何前面的数字。最后，所有余数类别的结果相乘得到最终答案。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def countTheNumOfKFreeSubsets(self, nums: List[int], k: int) -> int:
        nums.sort()  # 对数组进行排序
        count_nums = defaultdict(list)  # 使用字典存储余数分类

        for num in nums:
            count_nums[num%k].append(num)  # 对数字进行分类
        
        ans = 1
        for count_num in count_nums.values():  # 遍历每个分类
            dp = [0] * len(count_num)  # 初始化动态规划数组
            dp[0] = 2  # 只有一个元素时，可以选择包含或不包含
            for j in range(1, len(count_num)):
                if count_num[j] - count_num[j-1] == k:
                    dp[j] = dp[j-1]+dp[j-2] if j > 1 else dp[j-1] + 1  # 根据相邻元素之差决定状态转移
                else:
                    dp[j] = 2 * dp[j-1]  # 默认状态转移
            ans *= dp[-1]  # 计算所有分类的结果乘积
        return ans  # 返回最终结果

Explore

排序数组主要有两个作用：首先，它能帮助以统一的方式将数组中的元素按照它们除以k的余数进行分类，确保同一分类中的元素聚集在一起，便于后续处理。其次，排序保证了每个分类中的元素按照自然顺序排列，这对于动态规划计算尤为重要，因为在制定状态转移方程时，我们需要考虑元素之间的相对位置和大小关系。通过对元素进行排序，可以直接通过索引顺序来比较元素，简化了动态规划的实现，尤其是在处理元素间差值等于k的情况时更加直观和易于实现。

在动态规划中，当两个相邻数字之差等于k时，状态转移方程会变化，是因为这种情况下，根据题目定义的'k-free'子集的要求，这两个数字不能同时出现在同一个子集中。因此，对于当前数字，我们在计算其包含在子集中的可能性时，不能简单地考虑包括前一个数字的所有情况，而是需要排除掉同时包含前一个数字的情况。这就导致了状态转移方程的变化：我们需要从前一个状态（不包括前一个数字的所有子集情况）和再前一个状态（考虑更早的数字，但不包括前一个数字的可能性）来进行状态的更新。这种变化确保了我们构建的子集满足'k-free'的条件，即子集中任何两个元素的差不应该是k。

动态规划数组dp[j]中的每个元素代表的是考虑到第j个元素时，可以形成的所有可能的'k-free'子集的数量。在初始化阶段，dp[0]设置为2，表示第一个元素可以选择包含或不包含，即存在两种情况：一个是空集，一个是只包含这一个元素的集合。对于后续的每个元素，其dp[j]的值基于前面元素的dp值计算得出。如果当前元素与前一个元素的差不等于k，意味着可以自由选择是否包含该元素，因此状态转移为dp[j] = 2 * dp[j-1]，即每种前一个状态都可以选择包含或不包含当前元素。如果差等于k，则需要特殊处理，从而确保不违反'k-free'的条件，此时dp[j]的值会考虑不包含前一个元素的所有情况，因此根据前面的状态来适当减少可能的子集数量。这样的计算过程确保了每一步都严格符合题目要求，避免了非法子集的生成。