Offer II 003. Offer II 003.

Leetcode-cn.com/problems/w3…

Topic describes

Given a non-negative integer n, count the number of 1s in the binary representation of each number between 0 and n and output an array. Example 1: input: n = 2 output:,1,1 [0] : 0 > 0 1 -- - > 2 - > 10 example 2:1 input: n = 5 output:,1,1,2,1,2 [0] interpretation: 0 --> 01 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101 Description: 0 <= n <= 105 Advanced: It is very easy to give a solution with time complexity O(n*sizeof(INTEGER)). But can you do that in one scan in linear time O(n)? The space complexity of the algorithm is O(n). Can you refine the solution further? Requires that you do this without using any built-in functions (such as __builtin_popcount in C++) in C++ or any other language. Attention: https://leetcode-cn.com/problems/counting-bits/Copy the code

Train of thought

If I is even, it’s the first digit of I minus 1 plus 1 if I is odd, it’s the first digit of I over 2

code

  • Language support: Python3

Python3 Code:


class Solution:
    def countBits(self, n: int) - >List[int] :
        Method # # violence
        # resList = []
        # for i in range(n+1):
        # res = 0
        # while i >=1:
        # res += 1 if (i% 2 == 1) else 0
        # i //= 2
        # resList.append(res)
        # return resList
        # If I is even, then the last digit of I -1 +1
        # If I is odd, it's one of I /2
        resList = []
        for i in range(n+1):
            res = None
            if i == 0:
                res = 0
            elif i == 1:
                res = 1
            elif i %2= =0:# the even
                res = resList[i//2]
            else:# odd
                res = resList[i-1] +1
            resList.append(res)
        return resList

Copy the code

Complexity analysis

Let n be the length of the array.

  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)