Đề bài
Một phòng thí nghiệm xác suất tung đồng xu rất nhiều lần và ghi kết quả thành một chuỗi (string) gồm H (mặt ngửa) và T (mặt sấp). Một loạt là nhóm dài nhất có thể các kết quả giống nhau liên tiếp; HHTHHH có các loạt HH, T và HHH. Học sinh thường ngạc nhiên vì loạt dài nhất trong một dãy kết quả ngẫu nhiên lại dài đến thế, nên phòng thí nghiệm muốn đo nó.
Hãy viết coin_toss_streaks(tosses).
Đầu vào
tosses: Các kết quả theo thứ tự, chỉ gồm H và T.
Đầu ra
Trả về [longest_heads, longest_tails, streaks]: độ dài loạt ngửa dài nhất, độ dài loạt sấp dài nhất (bằng 0 nếu mặt đó không lần nào xuất hiện) và tổng số loạt.
Ràng buộc
0 ≤ độ dài tosses ≤ 100,000
Ví dụ
Đầu vào:
tosses = "HHTHHH"
Kết quả mong đợi:
expected = [3, 1, 3]
Đầu vào:
std::string tosses = "HHTHHH";
Kết quả mong đợi:
std::vector<long long> expected = {3, 1, 3};
Đầu vào:
string tosses = "HHTHHH";
Kết quả mong đợi:
long[] expected = new long[] {3, 1, 3};
Giải thích
Các loạt là HH, T và HHH, nên loạt ngửa dài nhất là 3, loạt sấp dài nhất là 1, và có tổng cộng 3 loạt.
Đầu vào:
tosses = "TTTT"
Kết quả mong đợi:
expected = [0, 4, 1]
Đầu vào:
std::string tosses = "TTTT";
Kết quả mong đợi:
std::vector<long long> expected = {0, 4, 1};
Đầu vào:
string tosses = "TTTT";
Kết quả mong đợi:
long[] expected = new long[] {0, 4, 1};
Giải thích
Mặt ngửa không xuất hiện lần nào nên loạt ngửa dài nhất là 0; có một loạt sấp dài 4: [0, 4, 1].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Một loạt mới bắt đầu tại chỉ số 0 và tại mọi vị trí mà kết quả khác với lần tung trước đó.
Gợi ý 2
Giữ một độ dài tốt nhất cho mặt ngửa và một cho mặt sấp.
Gợi ý 3
Chuỗi rỗng không có loạt nào.
Độ phức tạp mong đợi
thời gian O(n), bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.