ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

Longest Run of Rolls

Find where the longest run of equal consecutive dice rolls starts and how long it is.

สิ่งที่คุณจะได้เรียนรู้

  • Detect where a run of equal values ends
  • Keep the start and length of the best run
  • Break ties toward the first run

โจทย์

ดูฉบับแปล

A dice simulator records every roll of a six-sided die in a list. A run is a group of consecutive rolls with the same value; a single roll is a run of length 1. Find the longest run. If several runs share the longest length, report the one that starts first.

Implement longest_run_of_rolls(rolls).

Input

rolls: The rolls in the order they happened, each from 1 to 6.

Output

Return [start, length]: the 0-based index where the longest run starts and its length. For an empty list return [-1, 0].

เงื่อนไข

0 ≤ number of rolls ≤ 10,000

1 ≤ roll ≤ 6

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
rolls = [1, 4, 4, 2, 6, 6, 6, 3]

ผลลัพธ์ที่คาดหวัง:
expected = [4, 3]
อินพุต:
std::vector<long long> rolls = {1, 4, 4, 2, 6, 6, 6, 3};

ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {4, 3};
อินพุต:
long[] rolls = new long[] {1, 4, 4, 2, 6, 6, 6, 3};

ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {4, 3};

คำอธิบาย

The three 6s starting at index 4 beat the two 4s: [4, 3].

ตัวอย่างที่ 2
อินพุต:
rolls = [5, 5, 2, 2, 3]

ผลลัพธ์ที่คาดหวัง:
expected = [0, 2]
อินพุต:
std::vector<long long> rolls = {5, 5, 2, 2, 3};

ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {0, 2};
อินพุต:
long[] rolls = new long[] {5, 5, 2, 2, 3};

ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {0, 2};

คำอธิบาย

Both pairs have length 2; the 5s start first, at index 0: [0, 2].

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

Remember where the current run started.

คำใบ้ 2

When the value changes (or the list ends), compare the finished run with the best one.

คำใบ้ 3

Replace the best only when the new run is strictly longer.

ความซับซ้อนที่คาดหวัง

O(n) time, O(1) extra space

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก