leetcode338. 比特位计数

338. 比特位计数

常用技巧 | 位运算

我的解法：

class Solution {public int[] countBits(int n) {int[] res = new int[n+1];int k = 1; //k控制当前起始的位置for(int i = 1;i <= n;++i){res[i] = res[i-k] + 1;if((i + 1) / 2 == k)  k = i + 1;}return res;}
}

法一：

class Solution {public int[] countBits(int n) {int[] res = new int[n+1];for(int i = 1;i <= n;++i){if(i % 2 == 1)  res[i] = res[i-1] + 1;//奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。else  res[i] = res[i/2];//偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。
}return res;}
}