LeetCode 900 RLE 迭代器题解用游标指针优雅遍历游程编码序列【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文围绕 LeetCode 900「RLE 迭代器」RLE Iterator展开这道中等难度的设计题要求实现一个能够按需耗尽游程编码Run-Length Encoding序列的迭代器。文章将带你掌握游程编码的核心概念、理解伪更新游标遍历的精髓并给出可直接运行的正确实现同时结合本仓库的 游程编码与哈夫曼编码专题 与 设计题专题 深化对压缩算法与设计题套路trade-off的理解。题目背景什么是游程编码在进入题目之前先理解 RLERun-Length Encoding游程编码的本质。游程编码是一种简单的无损压缩算法其基本思想是将重复且连续出现多次的字符用「连续出现次数某个字符」来描述。仓库中的 游程编码与哈夫曼编码专题 给出了一个直观的例子字符串AAAAABBBBCCC可以被描述为5A4B3C其中5A表示有 5 个连续的A4B表示 4 个连续的B3C表示 3 个连续的C。当文件中存在大量连续重复的二进制内容时例如大面积纯色色块的 BMP 图像这种编码能获得很好的压缩效果。本题正是在此基础上提出的给定一个游程编码数组实现一个迭代器来遍历它解码后的原始序列。注意我们并不真正把序列展开存储而是直接在编码数组上进行逻辑遍历这正是本题的核心考点。题目描述与示例题目要求编写一个遍历游程编码序列的迭代器迭代器由RLEIterator(int[] A)初始化其中A是某个序列的游程编码。更具体地对于所有偶数iA[i]告诉我们在序列中重复非负整数值A[i 1]的次数。迭代器支持一个函数next(int n)它耗尽接下来的n个元素n 1并返回以这种方式耗去的最后一个元素。如果没有剩余的元素可供耗尽则next返回-1。示例推演例如我们以A [3,8,0,9,2,5]开始这是序列[8,8,8,5,5]的游程编码。这是因为该序列可以读作三个八零个九两个五。输入[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]。.next(2)耗去序列的 2 个项返回8。现在剩下的序列是[8, 5, 5]。.next(1)耗去序列的 1 个项返回8。现在剩下的序列是[5, 5]。.next(1)耗去序列的 1 个项返回5。现在剩下的序列是[5]。.next(2)耗去序列的 2 个项返回-1。这是由于第一个被耗去的项是5但第二个项并不存在。由于最后一个要耗去的项不存在我们返回-1。注意.next(2)之所以返回-1是因为题目要求返回被耗去的最后一个元素——最后一个元素并不存在因此即使前面还有 1 个元素可耗也必须返回-1。这是一个非常关键的细节也是本题最容易踩的坑。数据规模提示0 A.length 1000且A.length是偶数。0 A[i] 10^9。每个测试用例最多调用1000次RLEIterator.next(int n)。每次调用RLEIterator.next(int n)都有1 n 10^9。从数据规模可以看出编码数组长度最多 1000、调用次数最多 1000但单次n可以高达10^9绝不能真的把编码序列展开成原始数组元素总数可能高达500 × 10^9只能在编码数组上做逻辑运算。前置知识哈夫曼编码和游程编码可阅读仓库中的 游程编码与哈夫曼编码专题 完整了解两种无损压缩算法的原理。该专题还指出实际无损压缩格式如 PNG、GIF、PDF、ZIP往往是先做游程编码、再做哈夫曼编码的组合使用。设计题的基本套路本题在仓库的 设计题专题 中被列为中等难度的代表题目。该专题的核心观点是设计题基本是选好数据结构算法实现就水到渠成关键是针对特定问题做出恰当的设计选择trade-off。思路分析这是一个游程编码的典型题目。算法分为两个部分初始化RLEIterator构造函数与调用next(n)。思路一物理更新数组简单但低效最朴素的想法是初始化时记住整个A每次调用next(n)时判断n是否大于A[i]i从 0 开始如果n A[i]说明当前这一段的元素不够耗移除数组前两项把该段完全耗尽更新n n - A[i]重复步骤 1。如果n A[i]说明当前段元素足够更新A[i] A[i] - n返回A[i 1]。这种做法的问题是每次都要物理修改/移除数组前部元素需要移动元素时间成本高且会破坏原始数据。思路二伪更新游标推荐本仓库采用的解法不更新数组本身而是做伪更新用一个变量current记录当前访问到的数组位置段索引。这样既避免了数组元素的移动也保留了原始数组。很多时候我们需要保留原始数据那就必须用这种方法本仓库的题解采用的就是这种方式。维护两个核心状态this.A原始游程编码数组不修改只读取。this.current当前正在处理的段的起始下标指向A中某个偶数位即该段的 count 位置。每次调用next(n)时while循环只要current未越界且当前段的剩余数量A[current]小于n说明该段不够耗于是把n减去A[current]代表耗光该段current 2跳到下一段。循环结束后若current A.length说明所有段都已耗尽返回-1。否则A[current] - n把当前段剩余数量扣减返回A[current 1]该段对应的元素值。注意这里虽然修改了A[current]count 字段但只是就地更新计数并不会移动元素或改变数组结构因此代价极低同时对于逻辑上已耗尽的段我们通过推进current指针来跳过符合伪更新的思想。完整代码实现JavaScript/** * param {number[]} A */ var RLEIterator function(A) { this.A A; this.current 0; }; /** * param {number} n * return {number} */ RLEIterator.prototype.next function(n) { const A this.A; while(this.current A.length A[this.current] n){ n n - A[this.current]; this.current 2; } if(this.current A.length){ return -1; } A[this.current] A[this.current] - n; // 更新Count return A[this.current 1]; // 返回element }; /** * Your RLEIterator object will be instantiated and called as such: * var obj new RLEIterator(A) * var param_1 obj.next(n) */代码逐步解析构造函数this.A A保存编码数组this.current 0指向第一个段下标 0 是 count下标 1 是对应元素。while 循环A[this.current] n表示当前段即使全部耗尽也满足不了n个元素的需求因此必须跳过该段——n减去该段数量current前进 2一个段占两个数组元素。该循环可能跳过多个段属于累进式跳跃。越界判断循环结束后若current已经越界说明已无元素可耗返回-1。这也正好处理了示例中.next(2)只剩 1 个元素时的情形第一个被耗去的项是5但第二个项并不存在因此返回-1。命中返回若current未越界说明n个元素在该段内即可满足。此时更新A[current] - n记录该段被消耗的进度返回A[current 1]作为被耗去的最后一个元素。复杂度分析以A.length表示编码数组长度、m表示调用next的次数时间复杂度整体上current指针只增不减全部调用累加起来最多遍历完整个数组因此m次调用的均摊时间复杂度为O(m A.length)单次调用最坏为O(A.length)一次性跳过多段。空间复杂度O(1)只使用了两个状态变量不需要额外存储这也是伪更新方案相比展开序列方案的最大优势——后者在n高达10^9时根本无法落地。边界情况与易错点返回 -1 的判定时机题目要求返回耗去的最后一个元素当被耗元素不存在时必须返回-1即使n个元素中的前几个仍然存在。这一点必须在循环结束后的越界判断中统一处理而不能在循环中途提前返回。count 恰好等于 n 的情况当A[current] n时循环条件A[this.current] n不成立直接走到更新分支A[current]变为 0返回A[current 1]。此时该段逻辑上已空但current并未前进——这没有问题因为下一次调用next时若还需要消耗A[current] n0 n将成立循环会立即跳过该段。这是代码逻辑能够自洽的关键。空数组初始化若A []构造函数正常运行首次调用next时 while 条件current A.length立即不成立返回-1。不要真的展开序列编码数组中 count 之和可能极大每个 count 最高10^9最多 500 段任何形式的展开存储都会导致内存或时间爆炸务必在编码数组上做逻辑运算。在仓库中的定位与扩展阅读本题目在仓库中属于中等难度设计题可见于中等难度题目合集与911. 在线选举、460. LFU 缓存等设计题并列。设计题专题作者精选的 6 道设计题之一用于演示选择合适数据结构/状态表示这一核心设计套路。题解总览 与 introduction.md均收录了该题标注 推荐。如果希望彻底理解游程编码的来龙去脉以及它和哈夫曼编码的组合使用方式请务必阅读 游程编码与哈夫曼编码专题其中还探讨了如何提取子序列等编码策略问题以及游程编码在纯色图片、CDN 图片存储等场景中的实际意义。该专题与本题目互为印证理解压缩编码的存储结构是写出高效遍历器的前提。总结RLE 迭代器是一道看着简单、写对不易的设计题核心收获有三点数据结构决定解法在编码数组上用一个单调递增的游标current模拟序列遍历避免了展开原始序列的空间爆炸也避免了物理删除数组元素的额外开销。伪更新思想的普适性当需要保留原始数据、又要模拟消费进度时用一个外部游标记录位置往往比真正修改数据结构更优雅、更高效。边界处理的严谨性-1的返回时机、count 恰好耗尽、空数组等边界情况是这类迭代器题目能否一次写对的关键。掌握这道题之后再遇到在线选举911. 在线选举、LFU 缓存460. LFU 缓存等设计题时你会更容易抓住先定数据结构、再谈算法的解题主线。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 900 RLE 迭代器题解：用游标指针优雅遍历游程编码序列
LeetCode 900 RLE 迭代器题解用游标指针优雅遍历游程编码序列【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文围绕 LeetCode 900「RLE 迭代器」RLE Iterator展开这道中等难度的设计题要求实现一个能够按需耗尽游程编码Run-Length Encoding序列的迭代器。文章将带你掌握游程编码的核心概念、理解伪更新游标遍历的精髓并给出可直接运行的正确实现同时结合本仓库的 游程编码与哈夫曼编码专题 与 设计题专题 深化对压缩算法与设计题套路trade-off的理解。题目背景什么是游程编码在进入题目之前先理解 RLERun-Length Encoding游程编码的本质。游程编码是一种简单的无损压缩算法其基本思想是将重复且连续出现多次的字符用「连续出现次数某个字符」来描述。仓库中的 游程编码与哈夫曼编码专题 给出了一个直观的例子字符串AAAAABBBBCCC可以被描述为5A4B3C其中5A表示有 5 个连续的A4B表示 4 个连续的B3C表示 3 个连续的C。当文件中存在大量连续重复的二进制内容时例如大面积纯色色块的 BMP 图像这种编码能获得很好的压缩效果。本题正是在此基础上提出的给定一个游程编码数组实现一个迭代器来遍历它解码后的原始序列。注意我们并不真正把序列展开存储而是直接在编码数组上进行逻辑遍历这正是本题的核心考点。题目描述与示例题目要求编写一个遍历游程编码序列的迭代器迭代器由RLEIterator(int[] A)初始化其中A是某个序列的游程编码。更具体地对于所有偶数iA[i]告诉我们在序列中重复非负整数值A[i 1]的次数。迭代器支持一个函数next(int n)它耗尽接下来的n个元素n 1并返回以这种方式耗去的最后一个元素。如果没有剩余的元素可供耗尽则next返回-1。示例推演例如我们以A [3,8,0,9,2,5]开始这是序列[8,8,8,5,5]的游程编码。这是因为该序列可以读作三个八零个九两个五。输入[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]。.next(2)耗去序列的 2 个项返回8。现在剩下的序列是[8, 5, 5]。.next(1)耗去序列的 1 个项返回8。现在剩下的序列是[5, 5]。.next(1)耗去序列的 1 个项返回5。现在剩下的序列是[5]。.next(2)耗去序列的 2 个项返回-1。这是由于第一个被耗去的项是5但第二个项并不存在。由于最后一个要耗去的项不存在我们返回-1。注意.next(2)之所以返回-1是因为题目要求返回被耗去的最后一个元素——最后一个元素并不存在因此即使前面还有 1 个元素可耗也必须返回-1。这是一个非常关键的细节也是本题最容易踩的坑。数据规模提示0 A.length 1000且A.length是偶数。0 A[i] 10^9。每个测试用例最多调用1000次RLEIterator.next(int n)。每次调用RLEIterator.next(int n)都有1 n 10^9。从数据规模可以看出编码数组长度最多 1000、调用次数最多 1000但单次n可以高达10^9绝不能真的把编码序列展开成原始数组元素总数可能高达500 × 10^9只能在编码数组上做逻辑运算。前置知识哈夫曼编码和游程编码可阅读仓库中的 游程编码与哈夫曼编码专题 完整了解两种无损压缩算法的原理。该专题还指出实际无损压缩格式如 PNG、GIF、PDF、ZIP往往是先做游程编码、再做哈夫曼编码的组合使用。设计题的基本套路本题在仓库的 设计题专题 中被列为中等难度的代表题目。该专题的核心观点是设计题基本是选好数据结构算法实现就水到渠成关键是针对特定问题做出恰当的设计选择trade-off。思路分析这是一个游程编码的典型题目。算法分为两个部分初始化RLEIterator构造函数与调用next(n)。思路一物理更新数组简单但低效最朴素的想法是初始化时记住整个A每次调用next(n)时判断n是否大于A[i]i从 0 开始如果n A[i]说明当前这一段的元素不够耗移除数组前两项把该段完全耗尽更新n n - A[i]重复步骤 1。如果n A[i]说明当前段元素足够更新A[i] A[i] - n返回A[i 1]。这种做法的问题是每次都要物理修改/移除数组前部元素需要移动元素时间成本高且会破坏原始数据。思路二伪更新游标推荐本仓库采用的解法不更新数组本身而是做伪更新用一个变量current记录当前访问到的数组位置段索引。这样既避免了数组元素的移动也保留了原始数组。很多时候我们需要保留原始数据那就必须用这种方法本仓库的题解采用的就是这种方式。维护两个核心状态this.A原始游程编码数组不修改只读取。this.current当前正在处理的段的起始下标指向A中某个偶数位即该段的 count 位置。每次调用next(n)时while循环只要current未越界且当前段的剩余数量A[current]小于n说明该段不够耗于是把n减去A[current]代表耗光该段current 2跳到下一段。循环结束后若current A.length说明所有段都已耗尽返回-1。否则A[current] - n把当前段剩余数量扣减返回A[current 1]该段对应的元素值。注意这里虽然修改了A[current]count 字段但只是就地更新计数并不会移动元素或改变数组结构因此代价极低同时对于逻辑上已耗尽的段我们通过推进current指针来跳过符合伪更新的思想。完整代码实现JavaScript/** * param {number[]} A */ var RLEIterator function(A) { this.A A; this.current 0; }; /** * param {number} n * return {number} */ RLEIterator.prototype.next function(n) { const A this.A; while(this.current A.length A[this.current] n){ n n - A[this.current]; this.current 2; } if(this.current A.length){ return -1; } A[this.current] A[this.current] - n; // 更新Count return A[this.current 1]; // 返回element }; /** * Your RLEIterator object will be instantiated and called as such: * var obj new RLEIterator(A) * var param_1 obj.next(n) */代码逐步解析构造函数this.A A保存编码数组this.current 0指向第一个段下标 0 是 count下标 1 是对应元素。while 循环A[this.current] n表示当前段即使全部耗尽也满足不了n个元素的需求因此必须跳过该段——n减去该段数量current前进 2一个段占两个数组元素。该循环可能跳过多个段属于累进式跳跃。越界判断循环结束后若current已经越界说明已无元素可耗返回-1。这也正好处理了示例中.next(2)只剩 1 个元素时的情形第一个被耗去的项是5但第二个项并不存在因此返回-1。命中返回若current未越界说明n个元素在该段内即可满足。此时更新A[current] - n记录该段被消耗的进度返回A[current 1]作为被耗去的最后一个元素。复杂度分析以A.length表示编码数组长度、m表示调用next的次数时间复杂度整体上current指针只增不减全部调用累加起来最多遍历完整个数组因此m次调用的均摊时间复杂度为O(m A.length)单次调用最坏为O(A.length)一次性跳过多段。空间复杂度O(1)只使用了两个状态变量不需要额外存储这也是伪更新方案相比展开序列方案的最大优势——后者在n高达10^9时根本无法落地。边界情况与易错点返回 -1 的判定时机题目要求返回耗去的最后一个元素当被耗元素不存在时必须返回-1即使n个元素中的前几个仍然存在。这一点必须在循环结束后的越界判断中统一处理而不能在循环中途提前返回。count 恰好等于 n 的情况当A[current] n时循环条件A[this.current] n不成立直接走到更新分支A[current]变为 0返回A[current 1]。此时该段逻辑上已空但current并未前进——这没有问题因为下一次调用next时若还需要消耗A[current] n0 n将成立循环会立即跳过该段。这是代码逻辑能够自洽的关键。空数组初始化若A []构造函数正常运行首次调用next时 while 条件current A.length立即不成立返回-1。不要真的展开序列编码数组中 count 之和可能极大每个 count 最高10^9最多 500 段任何形式的展开存储都会导致内存或时间爆炸务必在编码数组上做逻辑运算。在仓库中的定位与扩展阅读本题目在仓库中属于中等难度设计题可见于中等难度题目合集与911. 在线选举、460. LFU 缓存等设计题并列。设计题专题作者精选的 6 道设计题之一用于演示选择合适数据结构/状态表示这一核心设计套路。题解总览 与 introduction.md均收录了该题标注 推荐。如果希望彻底理解游程编码的来龙去脉以及它和哈夫曼编码的组合使用方式请务必阅读 游程编码与哈夫曼编码专题其中还探讨了如何提取子序列等编码策略问题以及游程编码在纯色图片、CDN 图片存储等场景中的实际意义。该专题与本题目互为印证理解压缩编码的存储结构是写出高效遍历器的前提。总结RLE 迭代器是一道看着简单、写对不易的设计题核心收获有三点数据结构决定解法在编码数组上用一个单调递增的游标current模拟序列遍历避免了展开原始序列的空间爆炸也避免了物理删除数组元素的额外开销。伪更新思想的普适性当需要保留原始数据、又要模拟消费进度时用一个外部游标记录位置往往比真正修改数据结构更优雅、更高效。边界处理的严谨性-1的返回时机、count 恰好耗尽、空数组等边界情况是这类迭代器题目能否一次写对的关键。掌握这道题之后再遇到在线选举911. 在线选举、LFU 缓存460. LFU 缓存等设计题时你会更容易抓住先定数据结构、再谈算法的解题主线。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考