文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 直接模擬
    • 2.2 二分查找

1. 題目

編寫(xiě)一個(gè)遍歷游程編碼序列的迭代器。

迭代器由 RLEIterator(int[] A) 初始化，其中 A 是某個(gè)序列的游程編碼。
更具體地，對(duì)于所有偶數(shù) i，A[i] 告訴我們?cè)谛蛄兄兄貜?fù)非負(fù)整數(shù)值 A[i + 1] 的次數(shù)。

迭代器支持一個(gè)函數(shù)：next(int n)，它耗盡接下來(lái)的 n 個(gè)元素（n >= 1）并返回以這種方式耗去的最后一個(gè)元素。
如果沒(méi)有剩余的元素可供耗盡，則 next 返回 -1 。

例如，我們以 A = [3,8,0,9,2,5] 開(kāi)始，這是序列 [8,8,8,5,5] 的游程編碼。
這是因?yàn)樵撔蛄锌梢宰x作 “三個(gè)八，零個(gè)九，兩個(gè)五”。

示例： 輸入：["RLEIterator","next","next","next","next"], [[[3,8,0,9,2,5]],[2],[1],[1],[2]] 輸出：[null,8,8,5,-1] 解釋： RLEIterator 由 RLEIterator([3,8,0,9,2,5]) 初始化。 這映射到序列 [8,8,8,5,5]。 然后調(diào)用 RLEIterator.next 4次。.next(2) 耗去序列的 2 個(gè)項(xiàng)，返回 8。現(xiàn)在剩下的序列是 [8, 5, 5]。.next(1) 耗去序列的 1 個(gè)項(xiàng)，返回 8。現(xiàn)在剩下的序列是 [5, 5]。.next(1) 耗去序列的 1 個(gè)項(xiàng)，返回 5。現(xiàn)在剩下的序列是 [5]。.next(2) 耗去序列的 2 個(gè)項(xiàng)，返回 -1。 這是由于第一個(gè)被耗去的項(xiàng)是 5， 但第二個(gè)項(xiàng)并不存在。由于最后一個(gè)要耗去的項(xiàng)不存在，我們返回 -1。提示： 0 <= A.length <= 1000 A.length 是偶數(shù)。 0 <= A[i] <= 10^9 每個(gè)測(cè)試用例最多調(diào)用 1000 次 RLEIterator.next(int n)。 每次調(diào)用 RLEIterator.next(int n) 都有 1 <= n <= 10^9 。

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/rle-iterator
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

2.1 直接模擬

class RLEIterator {vector<int> arr;vector<int> count;int idx = 0;int val; public:RLEIterator(vector<int>& A) {int n = A.size();arr.resize(n/2);count.resize(n/2);for(int i = 1; i < A.size(); i += 2){count[i/2] = A[i-1];//每個(gè)數(shù)字的個(gè)數(shù)arr[i/2] = A[i];//數(shù)字}}int next(int n) {val = -1;while(idx < count.size() && n > 0){if(count[idx] > n)//個(gè)數(shù)多{count[idx] -= n;//當(dāng)前數(shù)字個(gè)數(shù)減去nreturn arr[idx];}else//個(gè)數(shù)不夠 或者 剛好{n -= count[idx];//還差幾個(gè) n if(n == 0)val = arr[idx];idx++;//移動(dòng)到下一個(gè)數(shù)}}return val;} };

12 ms 8.2 MB

2.2 二分查找

• 記錄前綴和個(gè)數(shù)（非減序列），二分查找歷史第多少個(gè)（n也全部加起來(lái)）

class RLEIterator {vector<int> arr;vector<long long> count;long long totalcount = 0; public:RLEIterator(vector<int>& A) {for(int i = 1; i < A.size(); i += 2){if(A[i-1] == 0)//數(shù)量為0，跳過(guò) continue;totalcount += A[i-1];//前綴個(gè)數(shù)count.push_back(totalcount);arr.push_back(A[i]);}totalcount = 0;//重置}int next(int n) {totalcount += n; // 二分查找大于等于 totalcount 的第一個(gè)元素int l = 0, r = arr.size()-1, mid;while(l <= r){mid = l+((r-l)>>1);if(count[mid] < totalcount)l = mid+1;else{if(mid == 0 || count[mid-1] < totalcount)return arr[mid];elser = mid-1;}}return -1;} };

16 ms 8.5 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 900. RLE 迭代器（模拟/二分查找）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。