6/26 每日一題 (計算數字在2進制中有幾個1)

 Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 0 <= n <= 105

 

Follow up:

• It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
• Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

class Solution:

    def countBits(self, n: int) -> List[int]:

        ans=[]

        for i in range(n+1):

            a=bin(i)[2:]

            ans.append(a.count('1'))

        return ans

       

-----------------------參考答案

#通過將i右移1位(i >> 1) ,也就是得到i//2的 二進制表示中1的數量。

#(i&1) 這是 i 和 二進制數字1的AND位元運算當,最後一位是0或1時, 1&1=1 0&1=0 

#目的是獲取i的二進制表示的最後一位

#and[i>>1] 這是獲取ans數組中所引為 i >> 1 的元素值,

#這個值表示了i的二進制表示中去掉最後一位的1的數量

#所以透過ans[i >> 1] + (i & 1) 就可以得到i的二進制表示中1的總數量

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans=[0]*(n+1)  
        for i in range(1,n+1):
            ans[i]=ans[i>>1]+(i&1)

            
        return ans