只看楼主 举报 #每日一题#-基础-103 比特位计数

• 楼主

  王泽宇

  话题：25

  精华：0

  积分：107

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

  数据范围：0 <= n <= 1e5

  
  

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

   

  
  

  进阶：很容易就能实现时间复杂度为 O（n log n） 的解决方案，你可以在线性时间复杂度 O（n） 内用一趟扫描解决此问题吗？

  
  

  阅读：492 回复：2 2022-09-27 12:48:08 举报

• 2楼

  颜妙林

  话题：35

  精华：0

  积分：305

  

  偶数1的个数=该数>>1后1的个数
  

  奇数1的个数=（该数-1）后1的个数+1

  2022-09-27 19:52:12 举报

  还能输入140字