资讯专栏INFORMATION COLUMN

900-RLE 迭代器

zone / 1250人阅读

摘要:前言的第一道题目,虽然分值才分,但是却是中等难度的题目迭代器编写一个遍历游程编码序列的迭代器。迭代器由初始化,其中是某个序列的游程编码。迭代器支持一个函数,它耗尽接下来的个元素并返回以这种方式耗去的最后一个元素。

前言

Weekly Contest 101的第一道题目,虽然分值才4分,但是却是中等难度的题目RLE 迭代器:

编写一个遍历游程编码序列的迭代器。

迭代器由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]。
然后调用 RLEIterator.next 4次。

.next(2) 耗去序列的 2 个项,返回 8。现在剩下的序列是 [8, 5, 5]。

.next(1) 耗去序列的 1 个项,返回 8。现在剩下的序列是 [5, 5]。

.next(1) 耗去序列的 1 个项,返回 5。现在剩下的序列是 [5]。

.next(2) 耗去序列的 2 个项,返回 -1。 这是由于第一个被耗去的项是 5,
但第二个项并不存在。由于最后一个要耗去的项不存在,我们返回 -1。

PS:Leetcode这次的竞赛时间是1小时45分钟是因为竞赛开始了10分钟,但是题目还是看不到

解题思路

其实一开始做这个题目的时候我也是一头雾水,首先游程编码是一个我没接触过的概念,其次是这个题目描述说得太绕了。关于游程编码的概念,可以从网上找到介绍。

我先从示例入手简单讲解一下题目:

首先我们要知道关于初始化的数组其实是经过游程编码处理后的数组,即压缩后的数组。先展示游程编码前后的数组:

编码后
[3,8,0,9,2,5]

编码前
[8,8,8,5,5] 

根据题目的介绍,对编码后的数组进行处理后:[(3,8),(0,9),(2,5)]。每个括号内的其实就是(数字出现次数,对应的数字).也就是题目中所说的:

对于所有偶数 iA[i] 告诉我们在序列中重复非负整数值 A[i + 1] 的次数。

然后我们可以尝试进行解码:

解码(3,8)得到数组[8,8,8]

解码(0,9),由于次数为0,所以结果为[]

解码(2,5)得到[5,5]

然后按照顺序拼接起来[8,8,8,5,5]

而题目其实是要求我们根据输入的编码后的数组遍历解码(编码前)的数组

实现代码
/**
 * RLE 迭代器
 * @author RJH
 * create at 2018/9/9
 */
public class RLEIterator {
    /**
     * 当前原数据的索引,可以看做是一个指向当前访问位置的指针
     */
    private int index=0;
    /**
     * 当前遍历的元素,对应index+1的原数据的元素。其实是对应游程编码解压后的元素
     */
    private int element=-1;
    /**
     * 初始化的原数据,其实是游程编码压缩后的数组
     */
    private int[] data;

    public RLEIterator(int[] A) {
        data=A;
    }

    public int next(int n) {
        while (n>0){
            if(index>data.length-2){
                element=-1;
                break;
            }
            //当前元素出现次数
            int times=data[index];
            if(times>0){
                if(times>n){
                    data[index]=times-n;
                    element=data[index+1];
                }else{
                    //代表对应的元素已经遍历完了,所以设为0
                    data[index]=0;
                    //当前的元素则为index+1的元素
                    element=data[index+1];
                    index+=2;
                }
                n-=times;
            }else{
                //次数为0,直接访问下一个偶数index对应的次数
                index+=2;
            }
        }
        return element;
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/77036.html

相关文章

  • 当谈论迭代时,我谈些什么?

    摘要:示例代码如下此示例中可以看出,当迭代器终止时,通过抛出异常告知迭代器已耗尽。但如果迭代器所指向的数据结构在其存在时发生了插入或删除操作,则迭代器将可能失效。与的情形类似,对进行任何插入操作也将损坏迭代器。 花下猫语:之前说过,我对于编程语言跟其它学科的融合非常感兴趣,但我还说漏了一点,就是我对于 Python 跟其它编程语言的对比学习,也很感兴趣。所以,我一直希望能聚集一些有其它语言基...

    王军 评论0 收藏0
  • Python进阶:设计模式之迭代模式

    摘要:抓住了迭代器模式的本质,即是迭代,赋予了它极高的地位。输出结果输出结果小结迭代器模式几乎是种设计模式中最常用的设计模式,本文主要介绍了是如何运用迭代器模式,并介绍了模块生成迭代器的种方法,以及种生成迭代器的内置方法。 showImg(https://segmentfault.com/img/bVbmv7W?w=4272&h=2848); 在软件开发领域中,人们经常会用到这一个概念——设...

    pubdreamcc 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<