首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 281. 锯齿迭代器(map+vector)

LeetCode 281. 锯齿迭代器(map+vector)

作者头像
Michael阿明
发布2020-07-13 16:26:46
5690
发布2020-07-13 16:26:46
举报

1. 题目

给出两个一维的向量,请你实现一个迭代器,交替返回它们中间的元素。

示例:
输入:
v1 = [1,2]
v2 = [3,4,5,6] 
输出: [1,3,2,4,5,6]

解析: 通过连续调用 next 函数直到 hasNext 函数返回 false,
     next 函数返回值的次序应依次为: [1,3,2,4,5,6]。
     
拓展:假如给你 k 个一维向量呢?你的代码在这种情况下的扩展性又会如何呢?

拓展声明:
 “锯齿” 顺序对于 k > 2 的情况定义可能会有些歧义。
 所以,假如你觉得 “锯齿” 这个表述不妥,也可以认为这是一种 “循环”。

例如:
输入:
[1,2,3]
[4,5,6,7]
[8,9]
输出: [1,4,8,2,5,9,3,6,7].

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/zigzag-iterator 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

class ZigzagIterator {
    map<int, vector<int>> m;
    unordered_map<int,int> idx;
    int total = 0;
    map<int, vector<int>>::iterator it;
public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
        m[0] = v1;
        m[1] = v2;
        it = m.begin();
        idx[0] = 0;
        idx[1] = 0;
        total += v1.size()+v2.size();
    }

    int next() {
    	if(!hasNext())
    		return -1;
        if(it == m.end())
        	it = m.begin();//循环
        if(idx[it->first] == it->second.size())
        {	//该数组指针到结尾了
            m.erase(it++);//删除该数组,移动到下一个数组
            return next();
        }
        int val = it->second[idx[it->first]];//答案值
        idx[it->first]++;//数组遍历位置+1
        it++;//去下一个数组
        total--;//总数-1
        return val;
    }

    bool hasNext() {
        return total;
    }
};

12 ms 8.6 MB

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-07-03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
  • 2. 解题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档