剑指 Offer II 003 前 n 个数字二进制中 1 的个数

川长思鸟来 2024-03-27 10:36 37阅读 0赞

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

示例 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

## 方法一：位运算+动态规划 ##

思路：

所有的数都由奇数偶数组成，因而

*  当i为偶数：在二进制中，偶数的1的个数与偶数/2之后一样多（位运算相当于>>1个单位），因为偶数除开那个1，剩下的都是0，右移一个单位也只是少了个0
 *  当i为奇数：二进制中，奇数就是偶数+1，也就是在最低位上的是1而不是0，则，我们把奇数当偶数一样处理，最终再加上最低位的1即可

class Solution {
        public int[] countBits(int n) {
             
            int[] ans = new int[n + 1];
            // ans[i] = 「i >> 1 所包含的 1 的个数」+「i 的最低位是否为 1」
            for (int i = 1; i <= n; i++) ans[i] = ans[i >> 1] + (i & 1);
            
            return ans;
        }
    
    }

小细节：

for循环中一条执行语句能搞定的循环，最好不加花括号，一点点的性能下降在简单题中都是很亏贼的

![647835c1e7984fb59db27ed28666f1dc.png][]

![eff8d1a95fff459d9e8ebf7e2945eb78.png][]

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/w3tCBm  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[647835c1e7984fb59db27ed28666f1dc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/58f843ac54f9438584d45f54aaaf8751.png
[eff8d1a95fff459d9e8ebf7e2945eb78.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/869d395417cb49bb9ed82fd50803f613.png