核心思想：Brian Kernighan算法
思路：
x=x&(x-1)：可以用于清除二進制數中最右側的1。
舉個例子，20的二進制表示為10100，其最右側的1在第三位上。20-1=19，19的二進制表示為10011，10100&10011=10000。可以看到，Brian Kernighan算法可以二進制數將最右側的1清除。
只要清除一次1，就記錄一下，即可。

class Solution {public int[] countBits(int n) {int[] counts = new int[n + 1];for(int i = 0; i <= n; i++){counts[i] = one(i);}return counts;}public int one(int i ){int c = 0;while(i > 0){i = i & (i - 1);c++;}return c;} }

時間復雜度為O(nlogn)
方法二：
核心思想：動態規劃
思路：
偶數：偶數是相當于被某個更小的數乘2，乘2怎么來的？在二進制運算中，就是左移一位，也就是在低位多加1個0，那樣就說明dp[i] = dp[i / 2]
奇數：奇數由不大于該數的偶數+1得到，偶數+1在二進制位上會發生什么？會在低位多加1個1，那樣就說明dp[i] = dp[i-1] + 1，當然也可以寫成dp[i] = dp[i / 2] + 1

class Solution {public int[] countBits(int n) {int[] ones = new int[n + 1];for(int i = 0; i <= n; i++){if(i % 2 == 0){ones[i] = ones[i / 2];}else{ones[i] = ones[i - 1] + 1;}}return ones;} }

時間復雜度為O(n)

總結

以上是生活随笔為你收集整理的LeetCode 热题100-76-比特位计数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。