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

Dãy tung xúc xắc giống nhau dài nhất

Tìm vị trí bắt đầu và độ dài của dãy các lần tung xúc xắc liên tiếp cùng giá trị dài nhất.

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

  • Phát hiện nơi một dãy giá trị bằng nhau kết thúc
  • Lưu vị trí bắt đầu và độ dài của dãy tốt nhất
  • Khi hòa thì ưu tiên dãy xuất hiện trước

Đề bài

Xem bản gốc (English)

Một chương trình mô phỏng xúc xắc ghi lại mọi lần tung con xúc xắc sáu mặt vào một danh sách. Một dãy liên tiếp (run) là nhóm các lần tung liền nhau có cùng giá trị; một lần tung đơn lẻ là dãy có độ dài 1. Hãy tìm dãy dài nhất. Nếu nhiều dãy cùng dài nhất, chọn dãy bắt đầu sớm nhất.

Hãy viết longest_run_of_rolls(rolls).

Đầu vào

rolls: Kết quả các lần tung theo thứ tự, mỗi giá trị từ 1 đến 6.

Đầu ra

Trả về [start, length]: chỉ số (đánh số từ 0) nơi dãy dài nhất bắt đầu và độ dài của nó. Nếu danh sách rỗng, trả về [-1, 0].

Ràng buộc

0 ≤ số lần tung ≤ 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

Ba số 6 bắt đầu từ chỉ số 4 dài hơn hai số 4: [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

Cả hai cặp đều dài 2; cặp số 5 bắt đầu trước, tại chỉ số 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

Ghi nhớ vị trí bắt đầu của dãy hiện tại.

Gợi ý 2

Khi giá trị thay đổi (hoặc hết danh sách), so sánh dãy vừa kết thúc với dãy tốt nhất.

Gợi ý 3

Chỉ thay dãy tốt nhất khi dãy mới dài hơn hẳn.

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