[Leetcode] Flatten 2D Vector 整平二维向量

MageekChiu 发布于2019-08-14 12:36 / 942人阅读

摘要：另一个则是的迭代器，它负责记录当前到哪一个的迭代器了。每次时，我们先调用一下，确保当前的迭代器有下一个值。代码当前列表的迭代器为空，或者当前迭代器中没有下一个值时，需要更新为下一个迭代器

Flatten 2D Vector

Implement an iterator to flatten a 2d vector.
For example, Given 2d vector =
[
  [1,2],
  [3],
  [4,5,6]
] 
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6].

数组法 复杂度

时间 O(N) 空间 O(1)

思路

用一个数组表示每个List的迭代器，然后再记录一个变量，用来表示当前用到了第几个迭代器。

代码

public class Vector2D {

    List> its;
    int curr = 0;
    
    public Vector2D(List> vec2d) {
        this.its = new ArrayList>();
        for(List l : vec2d){
            // 只将非空的迭代器加入数组
            if(l.size() > 0){
               this.its.add(l.iterator()); 
            }
        }
    }

    public int next() {
        Integer res = its.get(curr).next();
        // 如果该迭代器用完了，换到下一个
        if(!its.get(curr).hasNext()){
            curr++;
        }
        return res;
    }

    public boolean hasNext() {
        return curr < its.size() && its.get(curr).hasNext();
    }
}

双迭代器法 复杂度

时间 O(N) 空间 O(1)

思路

维护两个迭代器：一个是输入的List>的迭代器，它负责遍历List的迭代器。另一个则是List的迭代器，它负责记录当前到哪一个List的迭代器了。每次next时，我们先调用一下hasNext，确保当前List的迭代器有下一个值。

代码

public class Vector2D {

    Iterator> it;
    Iterator curr;
    
    public Vector2D(List> vec2d) {
        it = vec2d.iterator();
    }

    public int next() {
        hasNext();
        return curr.next();
    }

    public boolean hasNext() {
        // 当前列表的迭代器为空，或者当前迭代器中没有下一个值时，需要更新为下一个迭代器
        while((curr == null || !curr.hasNext()) && it.hasNext()){
            curr = it.next().iterator();
        }
        return curr != null && curr.hasNext();
    }
}

云服务器 GPU云服务器 Flatten LeetCode LeetCode_String leetcode_35_SearchIn

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

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

[Leetcode] Flatten Binary Tree to Linked List 整平二叉

摘要：栈法复杂度时间空间思路对于一个根节点，我们将它的右子树压进一个栈中，然后将它的左子树放到右边来。如果该节点没有左子树，说明该节点是某个左子树的最后一个节点，我们这时候把栈中最近的右子树出来接到它的右边。 Flatten Binary Tree to Linked List Given a binary tree, flatten it to a linked list in-plac...

mikyou 2019-08-14 12:32 评论0 收藏0
[LeetCode] 251. Flatten 2D Vector

Problem Implement an iterator to flatten a 2d vector. Example: Input: 2d vector = [ [1,2], [3], [4,5,6] ] Output: [1,2,3,4,5,6] Explanation: By calling next repeatedly until hasNext returns fals...

curried 2019-08-16 13:30 评论0 收藏0
Keras 对序列进行一维和二维卷积

摘要：网络结构来自固定随机数种子以复现结果创建维向量，并扩展维度适应对输入的要求，的大小为定义卷积层卷积核数量为卷积核大小为定义最大化池化层平铺层，调整维度适应全链接层定义全链接层编译模型打印层的输出打印网络结构最终输出如下卷积结果网络结 showImg(https://segmentfault.com/img/remote/1460000012731670); 网络结构来自https://...

waterc 2019-07-30 15:20 评论0 收藏0
Python学习之路28-符合Python风格的对象

摘要：本篇继续学习之路，实现更多的特殊方法以让自定义类的行为跟真正的对象一样。之所以要让向量不可变，是因为我们在计算向量的哈希值时需要用到和的哈希值，如果这两个值可变，那向量的哈希值就能随时变化，这将不是一个可散列的对象。《流畅的Python》笔记。本篇是面向对象惯用方法的第二篇。前一篇讲的是内置对象的结构和行为，本篇则是自定义对象。本篇继续Python学习之路20，实现更多的特殊方法以让...

Eric 2019-07-30 16:50 评论0 收藏0