“This is the 12th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

The title

Given an integer n, for each I in 0 <= I <= n, count the number of 1s in its binary representation and return an array ans of length N + 1 as the answer.

Example 1:

Input: n = 2 Output: [0,1,1] Description: 0 --> 0 1 --> 1 2 --> 10Copy the code

Example 2:

Input: n = 5 output:,1,1,2,1,2 [0] : 0 > 0 1 -- - > 1 2 -- 3 -- -- > > 10, 11 4 - > 5-100 - > 101Copy the code

Their thinking

Let’s start with a concept: the lowest set bit

The lowest set bit is the lowest 1 bit in a positive integer binary. For example, the binary representation of 1010 is 1010, whose lowest setting bit is 2.

Bits [x] = bits[y] + 1 if y = x & (x-1) and y = 0, bits[x] = bits[y] + 1. So for any positive integer x, bits[x] = bits[x & (x-1)] + 1. Iterating over every positive integer from 1 to n, calculating the bits value.

Code implementation

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) = =0) {
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        returnbits; }}Copy the code

The last

  • Time complexity: O(n).

  • Space complexity: O(1).

Previous articles:

  • Binary tree summary: binary tree properties
  • Binary tree summary: binary tree modification and construction
  • StoreKit2 smells this good? Yeah, I tried it. It smells good
  • After reading this article, I am no longer afraid of being asked how to construct a binary tree.
  • The game guys are trying to get people to pay again. That’s bad!
  • Take you rolled a netease holding cloud music home | adapter
  • Netease Cloud Music Home Page (3)
  • Netease Cloud Music Home Page (2)
  • Netease Cloud Music Home Page (a)
  • Does the code need comments? Write and you lose
  • I would not study in Codable for a long time. They are for fun
  • IOS handles web data gracefully. Do you really? Why don’t you read this one
  • UICollectionView custom layout! This one is enough

Please drink a cup ☕️ + attention oh ~

  1. After reading, remember to give me a thumbs-up oh, there is 👍 power
  2. Follow the public number – HelloWorld Jie Shao, the first time push new posture

Finally, creation is not easy, if it is helpful to you, I hope you can praise and support, what questions can also be discussed in the comments section 😄 ~