[algorithm] sword finger offer2 golang interview question 3: the number of 1 in the binary form of the first n numbers

[ Algorithm ] The finger of the sword offer2 golang Interview questions 3： front n A number in binary form 1 The number of

subject 1:

Given a nonnegative integer n , Please calculate 0 To n In the binary representation of each number between 1 The number of , And output an array .

Example 1:

Input : n = 2
Output : [0,1,1]
explain :
0 --> 0
1 --> 1
2 --> 10
Example 2:

Input : n = 5
Output : [0,1,1,2,1,2]
explain :
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

explain :

0 <= n <= 105

func countBits(n int) []int {
    

}

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/w3tCBm
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas 1:

Ideas 1: Violence counts every digit of every number 1 The number of , Time complexity O(n*17),10^5 < ^17

Code

func countBits(n int) []int {
    
    // Ideas 1:  Violence counts every digit of every number 1 The number of , Time complexity  O(n*17),10^5 < ^17
    // Processing parameters 
    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
}

test

Ideas 2:

//  The main points of : i&（i-1） It's more than i in 1 One less number 
//  We can get through the previous i in 1 To find the number of , The time complexity is  O(n)

Code 2

func countBits(n int) []int {
    
    //  The main points of : i&（i-1） It's more than i in 1 One less number 
    //  We can get through the previous i in 1 To find the number of , The time complexity is  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
}

test 2