Tất cả thử thách
Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Loạt tung đồng xu liên tiếp

Tìm loạt mặt ngửa dài nhất, loạt mặt sấp dài nhất và số loạt trong kết quả tung đồng xu.

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

  • Chia một dãy thành các đoạn liên tiếp dài nhất có thể
  • Theo dõi đoạn dài nhất cho từng giá trị
  • Đếm số đoạn

Đề bài

Xem bản gốc (English)

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ụ

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

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.

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

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.

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.