338. Counting Bits

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 // 2%2  
1 --> 1 // out[2/2]
2 --> 10 // out[2] = out[2/2]+2%2
3 --> 11 // out[3] = out[3/2]+3%2
4 --> 100
5 --> 101

Java

class Solution {
    public int[] countBits(int n) {
        int out[]=new int[n+1];
        for(int i=1;i<=n;i++){
            out[i]=out[i/2]+i%2; // base 2, Quotient Remainder
        }
        return out;
    }
}

Python

轉二進位後算1個數

T:O(nlogn), S:O(1)
class Solution(object):
    def countBits(self, num):
        return [bin(x).count('1') for x in range(num+1)]

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)