3 ways - Đếm Số 1 trong Biểu Diễn Nhị Phân

1. Mô Tả Vấn Đề

Cho một số nguyên không âm n, hãy tạo mảng ans có độ dài n+1 sao cho:

ans[i] = số lượng bit 1 trong biểu diễn nhị phân của số i, với 0 ≤ i ≤ n.

2. Các Phương Pháp và Triển khai

2.1 Phương Pháp Thô (Native)

def countBits_native(self, n: int) -> List[int]:
    ans = []
    for i in range(n+1):
        ans.append(bin(i).count('1'))
    return ans

• Ý tưởng: Với mỗi i, chuyển sang chuỗi nhị phân bằng bin(i) rồi đếm ký tự '1'.
• Độ phức tạp thời gian: O(nlog⁡n) vì mỗi bin(i) và .count('1') tốn O(log⁡i), tổng cộng ~∑i=0 → n: O(log⁡i)= O(n \log n).
• Độ phức tạp không gian: O(n)

2.2 Quy Hoạch Động (DP)

def countBits_dp(self, n: int) -> List[int]:
    ans = [0] * (n+1)
    for i in range(1, n+1):
        ans[i] = ans[i // 2] + (i % 2)
    return ans

• Ý tưởng: Đối với mỗi số i, mối quan hệ giữa i và i /2:
  • Nếu i là số chẵn khi đó i và i/2 cùng số lượng 1 trong biểu diễn nhị phân
  • Nếu i lẻ thì biểu diễn nhị phân của i và i/2 sẽ cách nhau 1 số 1 ( least significant bit)
• Độ phức tạp thời gian: O(n), mỗi i tính trong thời gian O(1).
• Độ phức tạp không gian: O(n)

2.3 Đệ Quy

def countBits_recursive(self, n: int) -> List[int]:
    ans = [0] * (n+1)

    def count_ones(num):
        if num == 0:
            return 0
        if ans[num] != 0:
            return ans[num]
        ans[num] = count_ones(num//2) + (num & 1)
        return ans[num]

    for i in range(1, n+1):
        count_ones(i)

    return ans

• Ý tưởng: Sử dụng đệ quy với bộ nhớ, áp dụng cùng công thức như DP.
• Độ phức tạp thời gian: O(n) trung bình, mỗi số chỉ tính một lần.
• Độ phức tạp không gian: O(n+logn), trong đó O(n) cho mảng và O(log n) cho độ sâu đệ quy.
• Lưu ý: Có overhead của đệ quy, không thực sự tối ưu bằng DP vòng lặp.

3. Tổng Kết Độ Phức Tạp

4. Đánh Giá và Khuyến Nghị

• Native: Dễ hiểu, nhưng chậm khi n lớn. Phù hợp kịch bản nhỏ hoặc minh họa.
• DP: Tối ưu nhất về thời gian và không gian. Lựa chọn hàng đầu cho dữ liệu lớn.
• Đệ quy: Minh họa công thức đệ quy rõ ràng, nhưng overhead và rủi ro tràn stack.