338. 比特位计数

一 题目:

二 思路:

动态规划:
划分子问题

• 如果当前数字i为奇数,则前一个数是偶数(最后一个数字为0),那前一个数字加1,就是二进制末位的0变成了1而已,1的数量加了1
• 如果当前数字i为偶数,那么其比特位计数和其i/2的值是一样的,为一个数是偶数那么他的二进制比他的一半的二进制只是多了一个0而已

另外这里判断奇偶可以用&运算,比如我们可以判断(i&1)是否等于1,等于1就是奇数,否则是偶数,至于为什么呢?因为&操作两个位均为1才为1,而数字1的前面N位均补充为0，跟它做与运算，前面肯定为0

三 代码:

 class Solution {
        public int[] countBits(int n) {
            int[] dp = new int[n + 1];
            dp[0] = 0;
            // 如果当前数字i为奇数,则前一个数是偶数(最后一个数字为0),那前一个数字加1,就是二进制末位的0变成了1而已,1的数量加了1
            // 如果当前数字i为偶数,那么其比特位计数和其i/2的值是一样的,为一个数是偶数那么他的二进制比他的一半的二进制只是多了一个0而已
            for (int i = 1; i <= n; i++) {
                //如果是奇数
                if ((i&1)==1){
                    dp[i]=dp[i-1]+1;
                }else{
                    dp[i]=dp[i/2];
                }
            }
            return dp;
        }
    }