如何高效解决LeeCode 338题——比特位计数问题？

本文共计287个文字，预计阅读时间需要2分钟。

【题目描述】给你一个整数n，对于0 <=i <=n，计算二进制表示中1的个数，返回一个长度为n+1的数组，其中第i个元素表示0到i中二进制表示中1的个数。

【示例】输入：n=5输出：[0, 1, 1, 2, 1, 2]

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

​​leetcode.cn/problems/counting-bits/?favorite=2cktkvj​​

admin

Integer.toBinaryString(i); // 十进制转二进制Integer.bitCount(i) // 统计二进制中1的数量import java.math.BigInteger;import java.util.*;import java.util.regex.Pattern;// 2022-12-17class Solution { public int[] countBits(int n) { if ( n < 0) return null; int[] res = new int[n+1]; for (int i = 0; i <= n; i++){ int count = Integer.bitCount(i); res[i] = count; } return res; }}public class Main{ public static void main(String[] args) { int n = 5; new Solution().countBits(n); }}

Offical

public int[] countBits(int n) { if ( n < 0) return null; int[] res = new int[n+1]; for (int i = 0; i <= n; i++){ res[i] = countOnes(i); } return res;}private int countOnes(int x) { int one = 0; while (x > 0) { x &= (x - 1); // 相同为1 one++; } return one;}