leetcode338-Counting Bits

题目

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1：
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

分析

可以一个一个去计算每个数字的位数，也可以通过观察数字的规律找到更简单的办法，每个数字的位数和前一个数字的位数有很大的关系

public class countingBits {public static void main(String[] args) {int[] res = getBit(5);for(int i = 0;i<res.length;i++) {System.out.println(res[i]);}}public static int[] getBit(int n) {int[] res = new int[n+1];for(int i = 1;i<=n;i++) {res[i] = res[i & (i-1)] + 1;}return res;}
}