โจทย์
ห้องแล็บความน่าจะเป็นโยนเหรียญหลายครั้ง แล้วบันทึกผลเป็นสตริงของ H (หัว) และ T (ก้อย) ช่วงหนึ่งช่วงคือกลุ่มของผลที่เหมือนกันและต่อเนื่องกันยาวที่สุดเท่าที่เป็นไปได้ เช่น HHTHHH มีช่วง HH, T และ HHH นักเรียนมักแปลกใจว่าช่วงที่ยาวที่สุดในผลสุ่มยาวได้ขนาดไหน ห้องแล็บจึงวัดค่านี้
จงเขียน coin_toss_streaks(tosses)
อินพุต
tosses: ผลการโยนตามลำดับ ใช้เฉพาะ H และ T
เอาต์พุต
คืนค่า [longest_heads, longest_tails, streaks] คือความยาวของช่วงหัวที่ยาวที่สุด ความยาวของช่วงก้อยที่ยาวที่สุด (เป็น 0 ถ้าด้านนั้นไม่เคยออกเลย) และจำนวนช่วงทั้งหมด
เงื่อนไข
0 ≤ ความยาวของ tosses ≤ 100,000
ตัวอย่าง
อินพุต:
tosses = "HHTHHH"
ผลลัพธ์ที่คาดหวัง:
expected = [3, 1, 3]
อินพุต:
std::string tosses = "HHTHHH";
ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {3, 1, 3};
อินพุต:
string tosses = "HHTHHH";
ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {3, 1, 3};
คำอธิบาย
ช่วงต่าง ๆ คือ HH, T และ HHH ช่วงหัวที่ยาวที่สุดจึงเป็น 3 ช่วงก้อยที่ยาวที่สุดเป็น 1 และมีทั้งหมด 3 ช่วง
อินพุต:
tosses = "TTTT"
ผลลัพธ์ที่คาดหวัง:
expected = [0, 4, 1]
อินพุต:
std::string tosses = "TTTT";
ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {0, 4, 1};
อินพุต:
string tosses = "TTTT";
ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {0, 4, 1};
คำอธิบาย
หัวไม่เคยออกเลย ช่วงหัวที่ยาวที่สุดจึงเป็น 0 และมีช่วงก้อยหนึ่งช่วงที่ยาว 4 จึงได้ [0, 4, 1]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ช่วงใหม่เริ่มที่ดัชนี 0 และทุกตำแหน่งที่ผลการโยนต่างจากครั้งก่อนหน้า
คำใบ้ 2
เก็บความยาวที่ดีที่สุดไว้หนึ่งค่าสำหรับหัว และอีกหนึ่งค่าสำหรับก้อย
คำใบ้ 3
สตริงว่างไม่มีช่วงใดเลย
ความซับซ้อนที่คาดหวัง
เวลา O(n), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน