[算法] 剑指offer2 golang 面试题3：前n个数字二进制形式中1的个数

题目1:

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

func countBits(n int) []int {
    

}

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

思路1:

思路1: 暴力计算每一个数字的每一位1的个数,时间复杂度 O(n*17),10^5 < ^17

代码

func countBits(n int) []int {
    
    //思路1: 暴力计算每一个数字的每一位1的个数,时间复杂度 O(n*17),10^5 < ^17
    //参数处理
    if n == 0 {
    
        return []int{
    0}
    }
    res := make([]int,n+1)
    for i:=0;i <=n;i++{
    
        count := 0 
        for j:=0;j<17;j ++{
    
            if i & (1 << j) != 0 {
    
                count ++
            }
        }
        res[i] = count
    }
    return res
}

测试

思路2:

// 要点: i&（i-1）就是比i中1少一个的数字
// 我们可以通过之前求到的i中1的个数来求,时间复杂度是 O(n)

代码2

func countBits(n int) []int {
    
    // 要点: i&（i-1）就是比i中1少一个的数字
    // 我们可以通过之前求到的i中1的个数来求,时间复杂度是 O(n)
    if n == 0 {
    
        return []int{
    0}
    }
    res := make([]int,n+1)
    res[0] = 0
    for i:=1;i <=n;i++{
    
        res[i] = res[i&(i-1)] + 1
    }
    return res
}

测试2