338. Bit count

subject

Give you an integer n , about 0 <= i <= n Each of the i , Calculate its binary representation 1 The number of , Returns a length of n + 1 Array of ans As the answer .
Example ：

Ideas

For all numbers , There are only two kinds of ：
** Odd number ：** In binary representation , The odd number must be one more than the even number before 1, Because more is the lowest 1.
give an example ：
0 = 0 1 = 1
2 = 10 3 = 11
even numbers ： In binary representation , In even numbers 1 The number of must be divided by 2 The number after that is the same . Because the lowest point is 0, Divide 2 Is to move one bit to the right , That is to put that 0 Just erase it , therefore 1 The number of is constant .
give an example ：
2 = 10 4 = 100 8 = 1000
3 = 11 6 = 110 12 = 1100
initialization dp[0] = 0;

Code

class Solution {
    
    public int[] countBits(int n) {
    
        int[] res = new int[n+1];
        res[0] = 0;
        for(int i = 1; i <= n; i++){
    
            if((i & 1) != 0) // Odd number 
                res[i] = res[i-1] + 1;
            else
                res[i] = res[i/2];
        }
        return res;
    }
}