1. 问题背景与理解今天想和大家分享一道LeetCode上的动态规划题目——第3850题统计结果等于k的序列数目。这道题乍看简单但实际处理起来有不少值得深究的细节。我在解题过程中踩过几个坑也总结出了一些优化技巧希望能帮助到正在刷题的朋友们。题目大意是给定一个整数数组nums和一个整数k我们需要统计所有可能的非空子序列使得这些子序列中所有元素的按位与结果恰好等于k。按位与操作大家应该都熟悉就是把数字转为二进制后逐位进行与运算。举个例子nums [1,2,3], k 0。那么符合条件的子序列有[1,2],[1,3],[2,3],[1,2,3]因为它们的按位与结果都是0。而[1],[2],[3]的按位与结果分别是1,2,3不符合条件。2. 解题思路分析2.1 暴力解法及其局限性最直观的想法当然是枚举所有可能的子序列然后逐个计算它们的按位与结果。对于一个长度为n的数组子序列总数是2^n - 1去掉空序列。对于每个子序列计算按位与需要O(m)时间m是子序列长度。这种暴力解法的时间复杂度是O(n * 2^n)当n20时2^20≈100万还能接受但当n30时计算量就达到10亿级别显然会超时。所以我们需要寻找更高效的解法。2.2 关键观察点经过分析我发现几个重要性质按位与操作的性质a b ≤ min(a, b)。这意味着随着子序列长度的增加按位与结果只会保持不变或变小。必要条件如果某个子序列的按位与结果是k那么这个子序列中的所有数字与k做按位与的结果必须还是k。换句话说这些数字在k的二进制表示中为1的位上必须都是1。预处理基于上一点我们可以先过滤掉那些与k按位与结果不等于k的数字因为它们不可能出现在符合条件的子序列中。2.3 动态规划解法基于上述观察我们可以设计一个动态规划解法。定义dp[mask]表示当前按位与结果为mask的子序列数目。初始时dp[所有数字的按位或] 1空序列。然后对于每个数字num我们更新dp数组 对于所有可能的mask如果num mask mask那么dp[num mask] dp[mask]最后dp[k]就是我们要的答案。这种解法的时间复杂度是O(n * K)其中K是可能的mask数量。在最坏情况下K2^32对于32位整数这显然不可行。因此需要进一步优化。3. 优化后的解决方案3.1 预处理过滤首先我们过滤掉所有与k按位与不等于k的数字。因为这些数字一旦包含在子序列中整个子序列的按位与结果就不可能等于k。filtered [x for x in nums if (x k) k]3.2 关键位分析接下来我们关注那些在k的二进制表示中为0的位。对于这些位我们需要确保子序列中至少有一个数字在该位为0这样才能保证最终按位与结果在该位为0。3.3 容斥原理应用我们可以使用容斥原理来计算符合条件的子序列数目。具体步骤计算所有由过滤后数字组成的非空子序列数目total 2^m - 1其中m是过滤后数组的长度。对于k的每个为0的二进制位减去那些所有数字在该位都为1的子序列数目。加上那些在两个不同为0的位上所有数字都为1的子序列数目因为被减去了两次。依此类推按照容斥原理处理所有组合。3.4 具体实现def countSubsequences(nums, k): # 预处理过滤 filtered [x for x in nums if (x k) k] m len(filtered) if m 0: return 0 # 找出k中为0的位 zero_bits [] temp (~k) ((1 32) - 1) # 取k的补码考虑32位整数 for i in range(32): if temp (1 i): zero_bits.append(i) # 如果没有为0的位说明k的所有位都是1 if not zero_bits: return (1 m) - 1 # 应用容斥原理 from itertools import combinations total 0 for r in range(1, len(zero_bits)1): for bits in combinations(zero_bits, r): mask 0 for b in bits: mask | (1 b) # 计算所有数字在bits指定的位上都是1的数量 cnt sum(1 for x in filtered if (x mask) mask) if cnt 0: continue if r % 2 1: total - (1 cnt) - 1 else: total (1 cnt) - 1 return (1 m) - 1 total4. 复杂度分析与优化4.1 时间复杂度预处理过滤O(n) 找出零位O(32) O(1) 容斥部分最坏情况下需要处理C(32,1)C(32,2)...C(32,32)2^32-1种组合但实际上k的零位数量通常很少。如果k有t个零位时间复杂度是O(m 2^t)4.2 空间复杂度主要是存储过滤后的数组和零位信息O(n t)4.3 进一步优化当t较大时比如t202^t会很大。这时可以考虑以下优化分组处理将零位分成若干组每组单独处理后再合并结果。动态规划用DP来统计满足各种位约束的子序列数目。位运算技巧利用位运算的性质减少计算量。5. 实际测试与验证为了验证我们的解法我设计了几个测试用例基础测试 nums [1,2,3], k 0 预期输出4[1,2],[1,3],[2,3],[1,2,3]边界测试 nums [3,3,3], k 3 预期输出7所有非空子序列复杂测试 nums [1,2,3,4,5,6,7,8,9,10], k 0 预期输出968无解测试 nums [1,3,5,7], k 2 预期输出06. 常见错误与调试技巧在实现过程中我遇到了几个典型错误忘记预处理过滤 最初没有过滤那些与k按位与不等于k的数字导致结果偏大。容斥原理应用错误 开始时错误地计算了需要减去或加上的子序列数目导致结果不正确。整数溢出 当m较大时2^m可能超过普通整数范围需要使用模运算或大整数。调试技巧打印中间变量特别是过滤后的数组和零位信息对小规模测试用例手动计算预期结果使用assert语句验证关键步骤的正确性7. 性能对比为了展示优化效果我对比了三种解法在n20时的运行时间暴力枚举约5秒基础DP约1秒优化后的容斥解法约0.01秒可以看到优化后的解法性能提升显著。8. 扩展思考这道题还可以从以下几个方向扩展统计按位或等于k的子序列数目统计按位异或等于k的子序列数目统计满足多个位运算条件的子序列数目将问题扩展到子数组而非子序列每种变体都有其独特的解题思路和技巧值得进一步探索。 LeetCode 3850题解：统计按位与等于k的子序列数目
1. 问题背景与理解今天想和大家分享一道LeetCode上的动态规划题目——第3850题统计结果等于k的序列数目。这道题乍看简单但实际处理起来有不少值得深究的细节。我在解题过程中踩过几个坑也总结出了一些优化技巧希望能帮助到正在刷题的朋友们。题目大意是给定一个整数数组nums和一个整数k我们需要统计所有可能的非空子序列使得这些子序列中所有元素的按位与结果恰好等于k。按位与操作大家应该都熟悉就是把数字转为二进制后逐位进行与运算。举个例子nums [1,2,3], k 0。那么符合条件的子序列有[1,2],[1,3],[2,3],[1,2,3]因为它们的按位与结果都是0。而[1],[2],[3]的按位与结果分别是1,2,3不符合条件。2. 解题思路分析2.1 暴力解法及其局限性最直观的想法当然是枚举所有可能的子序列然后逐个计算它们的按位与结果。对于一个长度为n的数组子序列总数是2^n - 1去掉空序列。对于每个子序列计算按位与需要O(m)时间m是子序列长度。这种暴力解法的时间复杂度是O(n * 2^n)当n20时2^20≈100万还能接受但当n30时计算量就达到10亿级别显然会超时。所以我们需要寻找更高效的解法。2.2 关键观察点经过分析我发现几个重要性质按位与操作的性质a b ≤ min(a, b)。这意味着随着子序列长度的增加按位与结果只会保持不变或变小。必要条件如果某个子序列的按位与结果是k那么这个子序列中的所有数字与k做按位与的结果必须还是k。换句话说这些数字在k的二进制表示中为1的位上必须都是1。预处理基于上一点我们可以先过滤掉那些与k按位与结果不等于k的数字因为它们不可能出现在符合条件的子序列中。2.3 动态规划解法基于上述观察我们可以设计一个动态规划解法。定义dp[mask]表示当前按位与结果为mask的子序列数目。初始时dp[所有数字的按位或] 1空序列。然后对于每个数字num我们更新dp数组 对于所有可能的mask如果num mask mask那么dp[num mask] dp[mask]最后dp[k]就是我们要的答案。这种解法的时间复杂度是O(n * K)其中K是可能的mask数量。在最坏情况下K2^32对于32位整数这显然不可行。因此需要进一步优化。3. 优化后的解决方案3.1 预处理过滤首先我们过滤掉所有与k按位与不等于k的数字。因为这些数字一旦包含在子序列中整个子序列的按位与结果就不可能等于k。filtered [x for x in nums if (x k) k]3.2 关键位分析接下来我们关注那些在k的二进制表示中为0的位。对于这些位我们需要确保子序列中至少有一个数字在该位为0这样才能保证最终按位与结果在该位为0。3.3 容斥原理应用我们可以使用容斥原理来计算符合条件的子序列数目。具体步骤计算所有由过滤后数字组成的非空子序列数目total 2^m - 1其中m是过滤后数组的长度。对于k的每个为0的二进制位减去那些所有数字在该位都为1的子序列数目。加上那些在两个不同为0的位上所有数字都为1的子序列数目因为被减去了两次。依此类推按照容斥原理处理所有组合。3.4 具体实现def countSubsequences(nums, k): # 预处理过滤 filtered [x for x in nums if (x k) k] m len(filtered) if m 0: return 0 # 找出k中为0的位 zero_bits [] temp (~k) ((1 32) - 1) # 取k的补码考虑32位整数 for i in range(32): if temp (1 i): zero_bits.append(i) # 如果没有为0的位说明k的所有位都是1 if not zero_bits: return (1 m) - 1 # 应用容斥原理 from itertools import combinations total 0 for r in range(1, len(zero_bits)1): for bits in combinations(zero_bits, r): mask 0 for b in bits: mask | (1 b) # 计算所有数字在bits指定的位上都是1的数量 cnt sum(1 for x in filtered if (x mask) mask) if cnt 0: continue if r % 2 1: total - (1 cnt) - 1 else: total (1 cnt) - 1 return (1 m) - 1 total4. 复杂度分析与优化4.1 时间复杂度预处理过滤O(n) 找出零位O(32) O(1) 容斥部分最坏情况下需要处理C(32,1)C(32,2)...C(32,32)2^32-1种组合但实际上k的零位数量通常很少。如果k有t个零位时间复杂度是O(m 2^t)4.2 空间复杂度主要是存储过滤后的数组和零位信息O(n t)4.3 进一步优化当t较大时比如t202^t会很大。这时可以考虑以下优化分组处理将零位分成若干组每组单独处理后再合并结果。动态规划用DP来统计满足各种位约束的子序列数目。位运算技巧利用位运算的性质减少计算量。5. 实际测试与验证为了验证我们的解法我设计了几个测试用例基础测试 nums [1,2,3], k 0 预期输出4[1,2],[1,3],[2,3],[1,2,3]边界测试 nums [3,3,3], k 3 预期输出7所有非空子序列复杂测试 nums [1,2,3,4,5,6,7,8,9,10], k 0 预期输出968无解测试 nums [1,3,5,7], k 2 预期输出06. 常见错误与调试技巧在实现过程中我遇到了几个典型错误忘记预处理过滤 最初没有过滤那些与k按位与不等于k的数字导致结果偏大。容斥原理应用错误 开始时错误地计算了需要减去或加上的子序列数目导致结果不正确。整数溢出 当m较大时2^m可能超过普通整数范围需要使用模运算或大整数。调试技巧打印中间变量特别是过滤后的数组和零位信息对小规模测试用例手动计算预期结果使用assert语句验证关键步骤的正确性7. 性能对比为了展示优化效果我对比了三种解法在n20时的运行时间暴力枚举约5秒基础DP约1秒优化后的容斥解法约0.01秒可以看到优化后的解法性能提升显著。8. 扩展思考这道题还可以从以下几个方向扩展统计按位或等于k的子序列数目统计按位异或等于k的子序列数目统计满足多个位运算条件的子序列数目将问题扩展到子数组而非子序列每种变体都有其独特的解题思路和技巧值得进一步探索。