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)