338. Counting Bits

Problem

Bài toán yêu cầu: Với một số nguyên không âm n , hãy trả về một mảng ans có độ dài n + 1, trong đó ans[i] là số lượng bit 1 trong biểu diễn nhị phân của i (với 0 ≤ i ≤ n)

Phân tích và ý tưởng

Có nhiều cách giải tối ưu nhất là sử dụng DP kết hợp với thao tác bit:

Nhận xét: Số lượng bit 1 của i có thể tính từ bit 1 của i >> 1 (tức là i dịch phải 1 bit, tương đương với chia 2 lấy phần nguyên)

Nếu i là số chẵn, bit cuối là 0, nên số bit 1 của i bằng số bit 1 của i /2

Nếu i là số lẻ, bit cuối là 1, nên số bit 1 của i bằng số bit 1 của i / 2 cộng thêm 1

Solution

typescripttypescript

1function countBits(n: number): number[] {
2    const ans: number[] = Array(n + 1).fill(0);
3    for (let i = 1; i <= n; i++) {
4        ans[i] = ans[i >> 1] + (i & 1);
5    }
6    return ans;
7};

Loading content...