Counting Bits

Q: Độ phức tạp thời gian của bài toán Đếm số bit là bao nhiêu?

Lời giải tốt nhất chạy trong thời gian O(n): mỗi trong số n+1 phần tử được tạo từ một phần tử trước đó bằng một phép cộng. Đếm số bit của từng số riêng lẻ mất thời gian O(n log n). Cả hai cách đều dùng O(1) bộ nhớ ngoài mảng đầu ra.

Q: Có công thức truy hồi O(n) nào khác để đếm bit không?

Có. i & (i-1) xóa bit 1 thấp nhất của i , nên bits[i] = bits[i & (i-1)] + 1 với mọi i lớn hơn hoặc bằng 1. Với 12 ( 1100 ), 12 & 11 bằng 8 ( 1000 ), số này có một bit 1, nên 12 có hai bit 1.

Q: Bạn có thể dùng hàm (function) popcount tích hợp sẵn không?

Gọi một hàm cho mỗi số, chẳng hạn như Integer.bitCount trong Java hoặc __builtin_popcount trong C và C++, sẽ cho câu trả lời chính xác. Người phỏng vấn thường yêu cầu phiên bản không dùng hàm đó, vì mục đích của bài toán là tái sử dụng những câu trả lời bạn đã tính trước đó.

DễThao tác bit Quy hoạch động

+10

Cho số nguyên không âm n, hãy trả về một mảng gồm n+1 phần tử, trong đó phần tử i là số lượng chữ số 1 trong biểu diễn nhị phân của i, với mọi i từ 0 đến n.

Hàm

countBits(n: integer) → integer-array

ninteger: số cuối cùng cần đếm, từ 0 trở lên
Trả vềinteger-array: một mảng gồm n+1 số đếm, trong đó phần tử i là số bit 1 trong i

Ràng buộc

0 ≤ n ≤ 2 × 10⁴

Ví dụ

Đầu vào: n = 2
Đầu ra: [0, 1, 1]
Giải thích: Trong hệ nhị phân, 0 là 0, 1 là 1 và 2 là 10: không có số 1, rồi đến một số 1, rồi cũng là một số 1.

Đầu vào: n = 5
Đầu ra: [0, 1, 1, 2, 1, 2]
Giải thích: 3 là 11 và 5 là 101, mỗi số có hai chữ số 1; 4 là 100, có một chữ số 1. Với 0, 1 và 2 trong ví dụ đầu tiên, số lượng lần lượt là 0, 1, 1, 2, 1, 2.

Câu hỏi mở rộng

Bạn có thể điền đầy đủ mảng trong thời gian O(n), không dùng hàm có sẵn để đếm bit và không đếm lại từng số từ đầu không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Đếm lại mọi số từ đầu sẽ lặp lại công việc: 13 là 1101, các bit của 6 (110) với thêm một chữ số ở cuối. Điền đáp án theo thứ tự tăng dần, mỗi mục đều dùng lại một mục nhỏ hơn và thêm một chữ số.

Đếm số bit của từng số

Ý tưởng

Đếm trực tiếp từng bit 1 của mỗi số: cộng x & 1 vào bộ đếm, dịch x sang phải một bit rồi dừng khi giá trị bằng 0. Với 13 (1101), các bit lần lượt là 1, 0, 1, 1, nên số lượng là 3.

Một số không vượt quá n có khoảng log2 n chữ số nhị phân, nên thuật toán chạy trong O(n log n): khoảng 20,000 × 15 = 300,000 bước với n = 2 × 10^4.

Thuật toán

Bắt đầu với một danh sách kết quả rỗng.
Với mỗi i từ 0 đến n, đặt count thành 0 và x thành i.
Khi x lớn hơn 0, cộng x & 1 vào count rồi dịch x sang phải một bit.
Thêm count vào danh sách kết quả.
Trả về danh sách kết quả.

def countBits(n):
    bits = []
    for i in range(n + 1):
        count = 0
        x = i
        while x > 0:
            count += x & 1  # the lowest bit
            x >>= 1         # shift it out
        bits.append(count)
    return bits

Xây dựng dựa trên một nửa số đó

Ý tưởng

Dịch i sang phải một bit sẽ xóa chữ số nhị phân cuối cùng của nó, còn i & 1 là chữ số đó. Vì vậy, i có các bit 1 của i >> 1 cộng với chữ số cuối cùng: bits[i] = bits[i >> 1] + (i & 1).

Với mọi i lớn hơn hoặc bằng 1, i >> 1 nhỏ hơn i. Vì vậy, điền mảng từ trái sang phải, bắt đầu với bits[0] = 0, đảm bảo phần tử bạn đọc luôn có sẵn. Với n = 5: bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2.

Mỗi phần tử cần một phép dịch bit, một phép AND và một phép cộng: thời gian O(n) và không dùng thêm bộ nhớ ngoài đầu ra.

Thuật toán

Tạo một mảng có tên bits gồm n+1 số 0. bits[0] giữ nguyên giá trị 0.
Với i từ 1 đến n, gán bits[i] bằng bits[i >> 1] + (i & 1).
Trả về bits.

def countBits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        # i >> 1 is i without its last bit, and i & 1 is that last bit
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

Lỗi thường gặp và trường hợp biên

Trả về n phần tử thay vì n+1. Với n = 0, đáp án là [0].
Thứ tự ưu tiên của toán tử. Trong Python, C, Java và JavaScript, + có độ ưu tiên cao hơn &, vì vậy bits[i >> 1] + i & 1 có nghĩa là (bits[i >> 1] + i) & 1. Hãy giữ dấu ngoặc quanh (i & 1).
Tra cứu bits[i-1] thay vì bits[i >> 1]. Các số liền kề không tuân theo quy tắc đơn giản nào: 7 là 111 với ba chữ số 1, còn 8 là 1000 với một chữ số 1.
Trong Lua và R, mảng bắt đầu từ 1, vì vậy số đếm cho i nằm ở chỉ số i+1, còn giá trị tra cứu cho i >> 1 nằm ở floor(i/2) + 1. Lua 5.1 không có toán tử dịch bit, nên hãy chia đôi bằng math.floor(i / 2).

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán Đếm số bit là bao nhiêu?

Lời giải tốt nhất chạy trong thời gian O(n): mỗi trong số n+1 phần tử được tạo từ một phần tử trước đó bằng một phép cộng. Đếm số bit của từng số riêng lẻ mất thời gian O(n log n). Cả hai cách đều dùng O(1) bộ nhớ ngoài mảng đầu ra.

Có công thức truy hồi O(n) nào khác để đếm bit không?

Có. i & (i-1) xóa bit 1 thấp nhất của i, nên bits[i] = bits[i & (i-1)] + 1 với mọi i lớn hơn hoặc bằng 1. Với 12 (1100), 12 & 11 bằng 8 (1000), số này có một bit 1, nên 12 có hai bit 1.

Bạn có thể dùng hàm (function) popcount tích hợp sẵn không?

Gọi một hàm cho mỗi số, chẳng hạn như Integer.bitCount trong Java hoặc __builtin_popcount trong C và C++, sẽ cho câu trả lời chính xác. Người phỏng vấn thường yêu cầu phiên bản không dùng hàm đó, vì mục đích của bài toán là tái sử dụng những câu trả lời bạn đã tính trước đó.

def countBits(n):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

n = 2

Đầu ra mong đợi

[0, 1, 1]