LeetCode-338. 比特位计数

小灰灰 2024-03-24 14:42 43阅读 0赞

#### 目录 ####

*   *  题目思路
     *  动态规划

题目来源  
[338. 比特位计数][338.]

### 题目思路 ###

奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。

0 = 0       1 = 1
    2 = 10      3 = 11

偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。

2 = 10       4 = 100       8 = 1000
    3 = 11       6 = 110       12 = 1100

可能不理解为啥3和6的个数是一样的

6>>1 表示向右移，除以2 偶数最低位是一定是0，所以1的个数是一样的

### 动态规划 ###

*  1.确定dp数组（dp table）以及下标的含义

dp\[i\]表示当前数1个的数，根据题目要求返回一个长度为 n + 1 的数组 ans 作为答案。

*  2.确定递推公式

如果为奇数的话，那么由前面的偶数加1，dp\[i\] = dp\[i-1\] + 1;  
如果为偶数的话，那么i/2就是1的个数，dp\[i\] = dp\[i/2\];

if(i % 2 == 1){
        
                    dp[i] = dp[i-1] + 1;
                }else{
        
                    dp[i] = dp[i/2];
                }

*  3.dp数组如何初始化

根据递推公式可知dp\[i\] = dp\[i-1\] + 1，我们要初始化dp\[0\]

*  4.确定遍历顺序

由递归公式可知，我们可以从左到右依次遍历

*  5.举例推导dp数组

![在这里插入图片描述][79a2ef10d20a49b182097d6b96911e95.png]  
代码实现

class Solution {
        
        public int[] countBits(int n) {
        
            int[] dp = new int[n+1];
            for(int i=1;i<dp.length;i++){
        
                if(i % 2 == 1){
        
                    dp[i] = dp[i-1] + 1;
                }else{
        
                    dp[i] = dp[i/2];
                }
            }
            return dp;
        }
    }

![在这里插入图片描述][3c5ddba0bc0544dabdc4c6f5a7e5293a.png]

[338.]: https://leetcode.cn/problems/counting-bits/
[79a2ef10d20a49b182097d6b96911e95.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/58131bd793f943b5859ea8b8abc4a579.png
[3c5ddba0bc0544dabdc4c6f5a7e5293a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/57426a25f5c645cca3ce69cc82c95eac.png