समस्या
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
उदाहरण
इनपुट:
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].
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।