Question 1 Island 母体二刷

解题步骤

Step 1: State the problem归大类

• Actually, this is a Graph Problem

• I want to model the problem to a Graph problem.

Step 2: Build Graph

• Let me build the graph.

• In my graph

  • my node/ vertex is every "1" cell in the matrix

  • edge: horizontally or vertically each one is connected with four directions with its neightbors

Step 3: 转化问题

• 脱马甲，这个问题其实本质上就是在解决你构建的哪个图上的什么问题

• 问一下面试官：OK, do you quite follow? Do you have any questions about the graph I built?

• So the problem is asking me to find out the number of islands, which is actually asking me how many connected components are there in the graph I built

Step 4:这个问题在图论里面是个什么问题

• Therefore this is a traversal(reachable) problem in graph

Step 5: Propose 算法对比，选择最优

• DFS对点的遍历

• BFS对点的遍历

• 对比：时间空间复杂度，商讨具体实现的细节，选择一个最好的来写

Method 1: DFS对点的遍历

public Solution {
    // assumption: no duplicate edge
    private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static final char LAND = '1';
    private static final char WATER = '0';
    
    private int numberOfIsland(char[][] grid) {
       if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int connectedComponent = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == LAND && !visited[i][j]) {
                    DFSMarkVisitedOne(grid, i, j,  visited);
                    connectedComponent++;
                }
            }
        }
        return connectedComponent;
    }
    private void DFSMarkVisitedOne(char[][] grid, int i , int j, boolean[][] visited) {
        if (visited[i][j]) return;
        visited[i][j] = true;
        for (int[] dir: DIRS) {
            int neiX = i + dir[0];
            int neiY = j + dir[1];
            if (!isValid(grid, neiX, neiY) || grid[i][j] == WATER) {
                continue;
            }
            DFSMarkVisitedOne(grid, neiX, neiY, visited);
        }
    }
    private boolean isValid(char[][] grid , int i, int j) {
        return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
    }
}

思考：这样Mark Visited好么？

• boolean[][] visited = new boolean[grid.length][grid[0].length];

• space: O(m* n) for mark visited. + Call Stack: m* n

其他的mark visited 的方式

• Set<Integer> visited ==> X* Col + Y ==> 含义 + overflow

• Set<String> visited ==> X + "#" + Y

• Set<Int[]> visited ==> Set没法对数组去重

• Set<List<Integer>>visited ==> Set可以对List去重

• 好的写法：Set<Node> visited;

缺点1:

• boolean[][] visited = new boolean[grid.length][grid[0].length];

• 不管我有没有走着点，都需要mark visited， 没有必要给这些0来开空间

缺点2:

• DFS is a method of Recursion: Call Stack还是很容易爆栈

Method 2: BFS对点的遍历

Let me define in code what should a Node Object be looked like

如何让Set知道如何我们定义的两个Node Object是不是同一个Object？ Java Specific

Override两个方法：

• HashCode(unique hash value)

  • 用来知道这个item存在hashSet/Map里哪个柜子bucked(index)的

• Equals

  • 用来知道这个柜子里这么多东西有没有和你一样的

Map or Set

• What is the time to get or put or add?O(1)

• It looks like O(1) BUT in reality is that true? In Worst Case, it can be O(n) Collision

Rewrite HashCode

class Node {
    int row;
    int col;
    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }
    @Override
    public int hashCode() {
        return this.row * 31 + this.col *31 * 31;
    }
    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        if (!obj instanceof Node) {
            return false;
        }
        Node temp = (Node) obj;
        return this.row == temp.row && this.col == temp.col;
    }
 }

Space: O(E)==> O(V)

class Solution {
    int row;
    int col;
    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }
    @Override
    public int hashCode() {
        return this.row * 31 + this.col *31 * 31;
    }
    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        if (!obj instanceof Node) {
            return false;
        }
        Node temp = (Node) obj;
        return this.row == temp.row && this.col == temp.col;
    }
    private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static final char LAND = '1';
    private static final char WATER = '0';
    private int numberOfIsland(char[][] grid) {
       if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int connectedComponent = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == LAND && !visited[i][j]) {
                    BFSMarkVisitedAtGeneration(grid, i, j,  visited);
                    connectedComponent++;
                }
            }
        }
        return connectedComponent;
    }
    private void BFSMarkVisitedAtGeneration(char[][] grid, int i, int j , Set<Node> visited) {
        Deque<Node> queue = new ArrayDeque<>();
        Node node = new Node(i, j);
        queue.offer(node);
        visited.add(node);
        while (!queue.isEmpty()) {
            Ndoe cur = queue.poll();
            for (int[] dir : DIRS) {
                int neiX = cur.row + dir[0];
                int neiY = cur.col. + dir[1];
                Node neighbor = new Node(neiX, neiY);
                if (isValid(grid, neiX, neiY) && grid[i][j] == LAND && !visited.contains(nei)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    
    
    }
    private boolean isValid(char[][] grid , int i, int j) {
        return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
    }    

}

严格的 O(V+E), maximum O(V) space