LeetCode(64) -- 341, 200

P341. Flatten Nested List Iterator (Medium)

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false,
             the order of elements returned by next should be: [1,1,2,1,1].

我的思路

在constructor里，通过递归把list变成一个整数的list，然后用这个list的iterator来遍历。

我的代码

public class NestedIterator {

    List<Integer> integerList;
    Iterator<Integer> iterator;

    public NestedIterator(List<NestedInteger> nestedList) {
        integerList = new ArrayList<>();
        for (NestedInteger nestedInteger : nestedList) {
            if (nestedInteger.isInteger()) {
                integerList.add(nestedInteger.getInteger());
            } else {
                NestedIterator nestedIterator = new NestedIterator(nestedInteger.getList());
                while (nestedIterator.hasNext()) {
                    integerList.add(nestedIterator.next());
                }
            }
        }
        iterator = integerList.iterator();
    }

    public Integer next() {
        return iterator.next();
    }

    public boolean hasNext() {
        return iterator.hasNext();
    }
}

68%

最优解

public class NestedIterator implements Iterator<Integer> {
    NestedInteger innerInteger = null;
    Iterator<Integer> inner = null;
    Iterator<NestedInteger> out;
    public NestedIterator(List<NestedInteger> nestedList) {
        out = nestedList.iterator();
    }

    @Override
    public Integer next() {
        if (null != innerInteger) {
            Integer r = innerInteger.getInteger();
            innerInteger = null;
            return r;
        }
        return inner.next();
    }

    @Override
    public boolean hasNext() {
        if (null != innerInteger && innerInteger.isInteger()) return true;
        if (null != inner && inner.hasNext()) return true;
        while(out.hasNext()) {
            NestedInteger next = out.next();
            if (next.isInteger()) {
                innerInteger = next;
                inner = null;
                return true;
            } else {
                innerInteger = null;
                inner = new NestedIterator(next.getList());
                if(inner.hasNext()) return true;
            }
        }
        inner = null;
        return false;
    }
}

读这个答案时，需要先读hasNext()方法，否则说不通。该方法用了list的iterator方法来遍历，如果是整数，就不新建任何东西了，直接把inner设置为null。可能这就是比我的方法快的原因。

P200. Number of Islands (Medium)

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Input:
11000
11000
00100
00011

Output: 3

我的思路

每遇到一个未访问过的1，就延着它的四个方向扩散递归dfs，直到把相邻的1全部访问为止。

我的代码

class Solution {
    int count = 0;
    boolean[][] visited;

    public int numIslands(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;
        int height = grid.length;
        int width = grid[0].length;
        visited = new boolean[height][width];

        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    count++;
                    dfs(i, j, grid, visited);
                }
            }
        }
        return count;
    }

    private void dfs(int r, int c, char[][] grid, boolean[][] visited) {
        if (visited[r][c]) return;
        visited[r][c] = true;
        if (r > 0 && grid[r - 1][c] == '1') {
            dfs(r - 1,c, grid, visited);
        }
        if (r < grid.length - 1 && grid[r + 1][c] == '1') {
            dfs(r + 1, c, grid, visited);
        }
        if (c > 0 && grid[r][c - 1] == '1') {
            dfs(r, c - 1, grid, visited);
        }
        if (c < grid[0].length - 1 && grid[r][c + 1] == '1') {
            dfs(r, c + 1, grid, visited);
        }
    }
}

100%

最优解

class Solution {
    public int numIslands(char[][] grid) {
        int result = 0;
        if(grid == null || grid.length == 0) return 0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j] == '1'){
                    result++;
                    findPath(grid,i,j);
                }
            }
        }
        return result;
    }

    void findPath(char[][] grid,int i,int j){
        if(i<0 || i>=grid.length || j<0 || j>=grid[0].length) return;
        if(grid[i][j] == '0') return;
        grid[i][j] = '0';
        findPath(grid,i+1,j);
        findPath(grid,i-1,j);
        findPath(grid,i,j+1);
        findPath(grid,i,j-1);
        return;
    }
}