Java解决比特维位计数

Java解决比特维位计数

01 题目

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

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

示例 2：

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

提示：

• 0 <= n <= 105

02 知识点

• 动态规划（DP）

• 二进制原理

03 我的题解

public class dongtai01 {public static void main(String[] args) {//测试和检查数据int[] nums=countBits(2);for (int i = 0; i < nums.length; i++) {System.out.println(nums[i]);}}public static int[] countBits(int n) {//根据题设得到返回数组int[] nums=new int[n+1];//循环判断每一个数的二进制有几个1for (int i = 0; i < nums.length; i++) {nums[i]=countBit(i);}return nums;}public static int countBit(int n) {//计数器int count=0;//当n=0时终止while (n!=0) {//根据二进制转化原理，二进制是十进制不断除以2的余数if (n%2==1) {//当余数为1时，计数器加一count++;}//下一次循环前除2n=n/2;}return count;}
}