251. Flatten 2D Vector

二刷 07/2022

Version #2 Iterator

Time amortized O(N) - N is total number of elements

Space O(L) - L is the max length of vector rows

Runtime: 12 ms, faster than 81.04% of Java online submissions for Flatten 2D Vector.

Memory Usage: 47.3 MB, less than 82.75% of Java online submissions for Flatten 2D Vector.

class Vector2D {

    int[][] vec;

    Iterator<Integer> rowIter;

    int rowNum;

    public Vector2D(int[][] vec) {

        this.vec = vec;

        if (vec.length == 0) {

            this.rowNum = -1;

            return;

        }

        this.rowNum = 0;

        this.rowIter = rowToIterator(vec[rowNum]);

    }

    

    private Iterator<Integer> rowToIterator(int[] row) {

        return Arrays.stream(row).boxed().toList().iterator();

    }

    

    public int next() {

        if (!hasNext()) {

            return 0;

        }

        return rowIter.next();

    }

    

    public boolean hasNext() {

        if (rowNum == -1) {

            return false;

        }

        while (!rowIter.hasNext() && rowNum + 1 < vec.length) {

            rowNum++;

            rowIter = rowToIterator(vec[rowNum]);

        }

        return rowIter.hasNext();

    }

}

Version #1 Two pointers

发现这个题很傻逼的地方就是有可能有有空的array

所以写了一个while保证找到的是valid的y和x

Time O(N) - N is total number of elements

Space O(1)

Runtime: 17 ms, faster than 42.03% of Java online submissions for Flatten 2D Vector.

Memory Usage: 51.9 MB, less than 7.42% of Java online submissions for Flatten 2D Vector.

class Vector2D {

    int[][] vec;

    int y, x;

    public Vector2D(int[][] vec) {

        this.vec = vec;

        this.y = 0;

        this.x = 0;

    }

    

    public int next() {

        if (!hasNext()) {

            return 0;

        }

        int n = vec[y][x];

        x++;

        return n;

    }

    

    public boolean hasNext() {

        while (y < vec.length && x == vec[y].length) {

            y++;

            x = 0;

        }

        return y < vec.length && x < vec[y].length;

    }

}

/**

 * Your Vector2D object will be instantiated and called as such:

 * Vector2D obj = new Vector2D(vec);

 * int param_1 = obj.next();

 * boolean param_2 = obj.hasNext();

 */

一刷

Version #2 Iterator
感觉自己写的这个版本继承了Version #1的思路
和discuss里面建立一个ArrayList<Iterator<Integer>>不一样
更喜欢自己的版本
在hasNext()里面debug了一阵，主要问题是colIter在call hasNext()的时候必须保证不是Null
而colIter是很有可能是null的
所以每次call hasNext() 都要先check null


*************重点****************
这种hasNext()的写法一开始写的思路很乱
后来自己总结了一个思路就是
如果没有next，先想尽办法搞出next
1.有的话就ok
2.一直没有的话，走到山穷水尽以后，再看有没有hasNext()
*************重点****************

33.36 % 
public class Vector2D implements Iterator<Integer> {
    Iterator<List<Integer>> rowIter;
    Iterator<Integer> colIter;
    public Vector2D(List<List<Integer>> vec2d) {
        rowIter = vec2d.iterator();
        colIter = null;
    }

    @Override
    public Integer next() {
        return colIter.next();
    }

    @Override
    public boolean hasNext() {
        while ((colIter == null || !colIter.hasNext()) && rowIter.hasNext()) {
            colIter = rowIter.next().iterator();
        }
        return colIter != null && colIter.hasNext();
    }
}


Version #1 Two pointers

1 points to rows, 1 points to columns

 79.92 %
public class Vector2D implements Iterator<Integer> {
    List<List<Integer>> list;
    int row;
    int col;
    public Vector2D(List<List<Integer>> vec2d) {
        this.list = vec2d;
        row = 0;
        col = 0;
    }

    @Override
    public Integer next() {
        return list.get(row).get(col++);
    }

    @Override
    public boolean hasNext() {
        /*[   col
            [1,2], <-- row
            [3],
            [4,5,6]
        ]*/
        while (row < list.size()) {
            if (col < list.get(row).size()) {
                return true;
            } else {
                row++;
                col = 0;
            }
        }
        return false;
    }
}