Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Coin Toss Streaks

Find the longest streak of heads, the longest streak of tails and the number of streaks in a coin toss record.

Bạn sẽ học được gì

  • Split a sequence into maximal runs
  • Track the best run for each value
  • Count runs

Đề bài

Xem bản dịch

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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.