Giả sử ta có hai ký tự đặc biệt. Ký tự đầu tiên có thể được biểu diễn bằng một bit 0. Ký tự thứ hai có thể được biểu diễn bằng hai bit như (10 hoặc 11). Vì vậy, nếu ta có một chuỗi được biểu diễn bởi nhiều bit. Ta cần kiểm tra xem ký tự cuối cùng có phải là ký tự 1-bit hay không. Chuỗi cho trước luôn kết thúc bằng 0.
Ví dụ, nếu đầu vào là [1,0,0], thì đầu ra sẽ là True, vì cách duy nhất để giải mã là ký tự 2-bit (10) và ký tự 1-bit (0). Vì vậy, ký tự cuối cùng là ký tự 1-bit.
Để giải quyết, ta thực hiện các bước sau:
- Khi kích thước bits > 1, thực hiện:
- current := phần tử đầu tiên của bits, sau đó xóa phần tử đầu tiên khỏi bits
- Nếu current bằng 1, thì:
- Xóa phần tử đầu tiên khỏi bits
- Nếu kích thước bits bằng 0, thì:
- Trả về False
- Trả về true khi bits[0] bằng 0, ngược lại false
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
class Solution: def isOneBitCharacter(self, bits): while len(bits) > 1: current = bits.pop(0) if current == 1: bits.pop(0) if len(bits) == 0: return False return bits[0] == 0 ob = Solution() print(ob.isOneBitCharacter([1,0,0]))
Đầu vào
[1,0,0]
Đầu ra
True