Đề bài
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ụ
Đầ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].
Đầ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.