题目

给定一个非负整数 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

说明 :0 <= n <= 105

进阶:给出时间复杂度为 O(n*sizeof(integer)) 的解答非常容易。但你可以在线性时间 O(n) 内用一趟扫描做到吗？

要求算法的空间复杂度为 O(n) 。

你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount ）来执行此操作。

注意：本题与主站 338 题相同

解题思路分析

1、位运算；时间复杂度O(n)，空间复杂度O(n)

func countBits(n int) []int {
   res := make([]int, n+1)
   for i := 1; i <= n; i++ {
      res[i] = res[i&(i-1)] + 1
   }
   return res
}

2、动态规划；时间复杂度O(n)，空间复杂度O(n)

func countBits(n int) []int {
   dp := make([]int, n+1)
   for i := 1; i <= n; i++ {
      if i%2 == 0 {
         dp[i] = dp[i/2]
      } else {
         dp[i] = dp[i-1] + 1
      }
   }
   return dp
}

3、暴力法；时间复杂度O(n)，空间复杂度O(n)

func countBits(n int) []int {
   res := make([]int, 0)
   for i := 0; i <= n; i++ {
      count := 0
      value := i
      for value != 0 {
         if value%2 == 1 {
            count++
         }
         value = value / 2
      }
      res = append(res, count)
   }
   return res
}

4、内置函数；时间复杂度O(n)，空间复杂度O(n)

func countBits(n int) []int {
   res := make([]int, 0)
   for i := 0; i <= n; i++ {
      count := bits.OnesCount(uint(i))
      res = append(res, count)
   }
   return res
}

总结

Easy题目，题目同leetcode 338.比特位计数