Đề bài
A probability lab flips a coin many times and writes the results as a string of H (heads) and T (tails). A streak is a maximal group of consecutive equal results; HHTHHH has the streaks HH, T and HHH. Students are often surprised how long the longest streak in a random record is, so the lab measures it.
Implement coin_toss_streaks(tosses).
Input
tosses: The results in order, using only H and T.
Output
Return [longest_heads, longest_tails, streaks]: the length of the longest heads streak, the length of the longest tails streak (0 if that side never comes up) and the total number of streaks.
Ràng buộc
0 ≤ length of 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
The streaks are HH, T and HHH, so the longest heads streak is 3, the longest tails streak is 1, and there are 3 streaks.
Đầ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
Heads never comes up, so its longest streak is 0; there is one tails streak of length 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
A new streak starts at index 0 and wherever a toss differs from the one before.
Gợi ý 2
Keep one best length for heads and one for tails.
Gợi ý 3
An empty string has no streaks at all.
Độ phức tạp mong đợi
O(n) time, O(1) extra space
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.