題目

給你一個整數 n ，對于 0 <= i <= n 中的每個 i ，計算其二進制表示中 1 的個數 ，返回一個長度為 n + 1 的數組 ans 作為答案。

示例

輸入：n = 2
輸出：[0,1,1]
解釋：
0 --> 0
1 --> 1
2 --> 10

輸入：n = 5
輸出：[0,1,1,2,1,2]
解釋：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/counting-bits
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

方法1：庫函數

Java實現

class Solution {public int[] countBits(int n) {int[] res = new int[n + 1];for (int i = 0; i <= n; i++) {res[i] = Integer.bitCount(i);}return res;} }

方法2：模擬

Java實現

class Solution {public int[] countBits(int n) {int[] res = new int[n + 1];for (int i = 0; i <= n; i++) {res[i] = count(i);}return res;}public int count(int n) {int sum = 0;while (n != 0) {if (n % 2 == 1) sum++;n /= 2;}return sum;} }

方法3：Brian Kernighan 算法

Java實現

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

總結

以上是生活随笔為你收集整理的力扣 338. 比特位计数的全部內容，希望文章能夠幫你解決所遇到的問題。

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