当前位置：网站首页>leetcode：281. 锯齿迭代器

leetcode：281. 锯齿迭代器

2022-08-10 16:39:00 【OceanStar的学习笔记】

题目来源

leetcode：281-VIP. 之字形迭代器

题目描述

在这里插入图片描述

class ZigzagIterator   {
    
public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2){
    
        
    }
    bool  hasNext(){
    

    }
    int next(){
    

    }
};

题目解析

思路（仅适用于k = 2时）

用两个变量i和j分别记录两个向量的当前元素，初始化为0
next：
- 当i < j时，说明需要打印v1的元素，否则打印v2的元素
hasNext：
- 当 $i == v 1. s i ze$ && $j == v 2. s i ze$ ，那么返回false
- 当 $i == v 1. s i ze ∣∣ j == v 2. s i ze$ ，那么将对应的i或者j赋值为INT_MAX，这样不影响打印另一个值

class ZigzagIterator   {
    
    std::vector<std::vector<int>> v;
    int i, j;
public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2){
    
        v.push_back(v1);
        v.push_back(v2);
        i = j = 0;
    }
    bool  hasNext(){
    
        if(i >= v[0].size()){
    
            i = INT32_MAX;
        }
        if(j >= v[1].size()){
    
            j = INT32_MAX;
        }
        return i < v[0].size() || j < v[1].size();
    }
    int next(){
    
        return i <= j ? v[0][i++] : v[1][j++];
    }
};

思路二

直接在初始化的时候就两个数组按照之字形的顺序存入另一个一维数组中
接下来就维护一个变量i，并按照顺序打印新数组中的值即可

class ZigzagIterator   {
    
  
public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2){
    
        int n1 = v1.size(), n2 = v2.size(), n = std::max(n1, n2);
        for (int i = 0; i < n; ++i) {
    
            if(i < n1){
    
                v.push_back(v1[i]);
            }
            if(i < n2){
    
                v.push_back(v2[i]);
            }
        }
    }
    
    bool  hasNext(){
    
        return idx < v.size();
    }
    int next(){
    
        return v[idx++];
    }

private:
    vector<int> v;
    int idx = 0;
};

但是如果v比较大，那么空间复杂度会很高。看下面方法

follow

queue + iterator：

用一个queue保存iterator的pair，初始化的时候，有几个数组就生成几个pair放到queue里面，每个pair保存该数组的首位置和尾位置的iterator
next的时候：
- 取出queue队首的一个pair
- 如果当前的iterator不等于end，将其下一个位置的iterator和end存入队尾，然后返回当前位置的是
haxNext：
- queue是否为空

class ZigzagIterator   {
    
    std::queue<std::pair<std::vector<int>::iterator, std::vector<int>::iterator>> q;
public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2){
    
        if(!v1.empty()){
    
            q.push(make_pair(v1.begin(), v1.end()));
        }
        if(!v2.empty()){
    
            q.push(make_pair(v2.begin(), v2.end()));
        }
    }
    
    bool  hasNext(){
    
        return !q.empty();
    }
    int next(){
    
        auto it = q.front().first, end = q.front().second; q.pop();
        if(it + 1 != end){
    
            q.push(make_pair(it + 1, end));
        }
        return *it;
    }

private:

};