lc：338练习的一点思考

 

public int[] CountBits(int n) {
int[] res = new int[n + 1];
for (int i = 0; i <= n; i++)
{
res[i] = CountOnesWithBitOperation(i);
}
return res;
}
public int CountOnesWithBitOperation(int n)
{
int count = 0;
while (n != 0)
{
n &= (n - 1); // 消除最右边的1
count++;
}
return count;
}

这个算法的时间复杂度我n log n，回顾算法的时间复杂度如何计算，同时记忆这个二进制1数量的计算方法

注意原来的算法实现，CountOnesWithBitOperation中采用i与i-1的与运算消去右端1，这个步骤似乎可以利用到CountBits方法中@_@

关键在于理解 i & (i - 1) 这个位运算操作：
该操作可以消除数字 i 的二进制表示中最右边的 1
因此 res[i] = res[i & (i - 1)] + 1 表示：当前数字的 1 的个数 = 消除最右边 1 后的数字的 1 的个数 + 1

相邻数字或有特定关系的数字之间，比特位数往往存在递推关系

使用动态规划的思想优化后的实现：
public class Solution {
public int[] CountBits(int n) {
int[] res = new int[n + 1];
for (int i = 1; i <= n; i++) {
// i比(i&(i-1))多一个1
res[i] = res[i & (i - 1)] + 1;
}
return res;
}
}