Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Longest Run of Rolls

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

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

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

Đề bài

Xem bản dịch

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].

Ràng buộc

0 ≤ number of rolls ≤ 10,000

1 ≤ roll ≤ 6

Ví dụ

Ví dụ 1
Đầu vào:
rolls = [1, 4, 4, 2, 6, 6, 6, 3]

Kết quả mong đợi:
expected = [4, 3]
Đầu vào:
std::vector<long long> rolls = {1, 4, 4, 2, 6, 6, 6, 3};

Kết quả mong đợi:
std::vector<long long> expected = {4, 3};
Đầu vào:
long[] rolls = new long[] {1, 4, 4, 2, 6, 6, 6, 3};

Kết quả mong đợi:
long[] expected = new long[] {4, 3};

Giải thích

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

Ví dụ 2
Đầu vào:
rolls = [5, 5, 2, 2, 3]

Kết quả mong đợi:
expected = [0, 2]
Đầu vào:
std::vector<long long> rolls = {5, 5, 2, 2, 3};

Kết quả mong đợi:
std::vector<long long> expected = {0, 2};
Đầu vào:
long[] rolls = new long[] {5, 5, 2, 2, 3};

Kết quả mong đợi:
long[] expected = new long[] {0, 2};

Giải thích

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

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Remember where the current run started.

Gợi ý 2

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

Gợi ý 3

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

Độ 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.