900. RLE iterator

Preface

C++ It's a high-level programming language , from C Language expansion and upgrading , As early as 1979 By Benjani · Strauss LUP is AT&T Developed by Bell studio .
C++ Both can be carried out C Process programming of language , It can also be used for object-based programming characterized by abstract data types , It can also carry out object-oriented programming characterized by inheritance and polymorphism .C++ Good at object-oriented programming at the same time , You can also do process based programming .
C++ Have the practical characteristics of computer operation , At the same time, it is also committed to improving the programming quality of large-scale programs and the problem description ability of programming languages .

Java Is an object-oriented programming language , Not only absorbed C++ The advantages of language , It's abandoned C++ The incomprehensible inheritance in 、 Concepts such as pointer , therefore Java Language has two characteristics: powerful and easy to use .Java As the representative of static object-oriented programming language , Excellent implementation of object-oriented theory , Allow programmers to do complex programming in an elegant way of thinking .
Java It's simple 、 object-oriented 、 Distributed 、 Robustness, 、 Security 、 Platform independence and portability 、 Multithreading 、 Dynamic and so on .Java Can write desktop applications 、Web Applications 、 Distributed system and embedded system applications, etc .

Python By Guido of the Dutch Society for mathematical and computer science research · Van rosum On 1990 It was designed in the early 's , As a course called ABC A substitute for language .Python Provides efficient advanced data structure , It's also a simple and effective way of object-oriented programming .Python Syntax and dynamic types , And the nature of interpretative language , Make it a programming language for scripting and rapid application development on most platforms , With the continuous update of the version and the addition of new language features , Gradually used for independent 、 Development of large projects .
Python The interpreter is easy to extend , have access to C Language or C++（ Or something else can be done through C Calling language ） Expand new functions and data types .Python It can also be used as an extensible programming language in customizable software .Python Rich library of standards , Provides source code or machine code for each major system platform .
2021 year 10 month , Compiler for language popularity index Tiobe take Python Crowned the most popular programming language ,20 Put it in... For the first time in years Java、C and JavaScript above .

describe

We can use run length coding ( namely RLE ) To encode a sequence of integers . In even length encoding ( from 0 Start ) In the run length code array of , For all even numbers i ,encoding[i] Tell us about nonnegative integers encoding[i + 1] The number of repetitions in a sequence .

    for example , Sequence arr = [8,8,8,5,5] Can be encoded as encoding =[3,8,2,5] .encoding =[3,8,0,9,2,5] and encoding =[2,8,1,8,2,5] It's also arr Effective RLE .

Given a run length encoding array , Design an iterator to traverse it .

Realization RLEIterator class :

    RLEIterator(int[] encoded) Initialize the object with the encoded array .
    int next(int n) After being exhausted in this way n Elements and returns the last exhausted element . If there are no remaining elements to be exhausted , Then return to -1 .

Example 1：

Input ：
["RLEIterator","next","next","next","next"]
[[[3,8,0,9,2,5]],[2],[1],[1],[2]]
Output ：
[null,8,8,5,-1]
explain ：
RLEIterator rLEIterator = new RLEIterator([3, 8, 0, 9, 2, 5]); // This maps to the sequence [8,8,8,5,5].
rLEIterator.next(2); // Consume the sequence of 2 The item , return 8. Now the rest of the sequence is [8, 5, 5].
rLEIterator.next(1); // Consume the sequence of 1 The item , return 8. Now the rest of the sequence is [5, 5].
rLEIterator.next(1); // Consume the sequence of 1 The item , return 5. Now the rest of the sequence is [5].
rLEIterator.next(2); // Consume the sequence of 2 The item , return -1. This is because the first item to be consumed is 5,
But the second one doesn't exist . Because the last item to be consumed does not exist , We go back to -1.

Tips ：

    2 <= encoding.length <= 1000
    encoding.length For me
    0 <= encoding[i] <= 109
    1 <= n <= 109
    Each test case calls next No more than 1000 Time

Method 1 ： Maintain the location of the next element and the number of deletions

analysis

Calling next() Function time , We will not actually delete the remaining elements （ Or change the array A Value ）, Instead, maintain two variables i and q, among i Indicates that the iterator is currently pointing to an element A[i + 1],q Indicates the number of times it has been deleted ,q The value of cannot be greater than A[i].

for example , Array A by [1,2,3,4] when , It represents a sequence of [2,4,4,4]. When i and q The values of are 0 and 0 when , Indicates that no element has been deleted ; When i and q The values of are 0 and 1 when , Show elements A[0 + 1] = 2 Been deleted 1 Time ; When i and q The values of are 2 and 1 when , Show elements A[2 + 1] = 4 Been deleted 1 Time , And all previous elements are deleted .

Algorithm

If we call next(n), Delete immediately n Elements , So for the current element A[i + 1], The number of times we can delete is D = A[i] - q.

If n > D, Then we will delete all A[i + 1], And iterate to the next element , namely n -= D; i += 2; q = 0.

If n <= D, Then the last element we delete is A[i + 1], namely q += D; return A[i + 1].

class RLEIterator {
    int[] A;
    int i, q;

    public RLEIterator(int[] A) {
        this.A = A;
        i = q = 0;
    }

    public int next(int n) {
        while (i < A.length) {
            if (q + n > A[i]) {
                n -= A[i] - q;
                q = 0;
                i += 2;
            } else {
                q += n;
                return A[i+1];
            }
        }

        return -1;
    }
}