动态规划攻略之：比特位计数

动态规划攻略之：比特位计数

题目

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例1：

输入：n = 2输出：[0,1,1]

示例2：

输入：n = 5输出：[0,1,1,2,1,2]解释：0 --> 01 --> 12 --> 103 --> 114 --> 1005 --> 101

解题思路

首先来看一个概念：最低设置位

最低设置位是正整数二进制中最低的 1 所在位。例如，1010 的二进制表示是 1010，其最低设置位为 2。

于是，定义一个正整数 x, 令 y = x & (x - 1), 则 y 为将 x 的最低设置位从 1 变成 0 之后的数，显然 0 <= y < x, bits[x] = bits[y] + 1。因此对于任意正整数 x, 都有 bits[x] = bits[x & (x - 1)] + 1。遍历从 1 到 n 的每个正整数，计算 bits 的值。

代码实现

class Solution { public int[] countBits(int n) { int[] bits = new int[n + 1]; int highBit = 0; for (int i = 1; i <= n; i++) { if ((i & (i - 1)) == 0) { highBit = i; } bits[i] = bits[i - highBit] + 1; } return

最后

时间复杂度：O(n)。空间复杂度：O(1)。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。