住房城乡建设部门户网站,国家高新技术企业补贴多少钱,android写wordpress,城乡建设部官网在计算机科学中#xff0c;计算整数的二进制表示中1的个数#xff08;也称为汉明重量#xff09;是一个常见问题。本文将介绍一种高效且优雅的动态规划解法#xff0c;帮助您理解其核心原理和实现细节。
问题描述 连接地址#xff1a;338. 比特位计数 - 力扣#xff08;…在计算机科学中计算整数的二进制表示中1的个数也称为汉明重量是一个常见问题。本文将介绍一种高效且优雅的动态规划解法帮助您理解其核心原理和实现细节。
问题描述 连接地址338. 比特位计数 - 力扣LeetCode 动态规划解法
核心思路
我们利用二进制数的数学特性和动态规划的思想 最高有效位(MSB)每个数都可以表示为2ᵏ j其中2ᵏ是不超过该数的最大2的幂次 状态转移数字i的1的个数 (i - 2ᵏ)的1的个数 1最高位贡献的1 递推公式bits[i] bits[i - highBit] 1
class Solution {public int[] countBits(int n) {int[] bits new int[n 1]; // 存储结果int highBit 0; // 当前最高有效位for (int i 1; i n; i) {// 检测2的幂次i (i-1) 0if ((i (i - 1)) 0) {highBit i; // 更新最高有效位}bits[i] bits[i - highBit] 1; // 状态转移}return bits;}
}
关键技巧检测2的幂次 if ((i (i - 1)) 0)
这个位运算技巧利用了2的幂次数的二进制特性 2的幂次数的二进制形式为100...0 减1后变为011...1 两者按位与结果为0
示例 8 (1000) 7 (0111) 0000 → 是2的幂次 7 (0111) 6 (0110) 0110 ≠ 0 → 不是2的幂次
逐步演算n5
i二进制是否2的幂次highBit计算过程bits[i]00000-0(基准)010001是1bits[0]1120010是2bits[0]1130011否2bits[1]1240100是4bits[0]1150101否4bits[1]12 复杂度分析 时间复杂度O(n) - 只需一次遍历 空间复杂度O(1) - 除结果数组外仅使用常数空间
算法优势 高效利用位运算检测2的幂次仅需O(1)时间 避免重复计算动态规划复用之前结果 数学基础牢固基于二进制数的数学特性 代码简洁优雅仅需10行左右代码
实际应用
这种算法在以下场景有重要应用 位图处理和图像压缩 密码学中的位操作 内存对齐检查 数据结构和算法优化 计算机图形学中的位操作
总结
通过本文我们学习了一种高效计算比特位数的动态规划算法。该算法巧妙地利用了二进制数的特性 使用位运算检测2的幂次 通过最高有效位分解问题 动态规划避免重复计算
这种解法不仅高效O(n)时间复杂度而且代码简洁优雅是动态规划与位运算结合的经典范例。理解这个算法有助于提升对二进制数和动态规划本质的认识为解决类似问题提供思路。
