305. Number of Islands II

Version# 1 Union Find

[2ND TRY]

1 defect that I didn't fix
-> the initial size for all nodes should be 0 since initially they are not added to the graph
-> When the coming position is added, set size[label] = 1, id[label] = label

39.25 %
class Solution {
    private int getLabel(int y, int x) {
return y * cols + x;
}

private int rows;
private int cols;
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private int[] id;
private int[] size;

public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> result = new ArrayList<>();
rows = m;
cols = n;
if (positions == null || positions.length == 0 || positions[0] == null || positions[0].length == 0) {
return result;
}

id = new int[m * n];
size = new int[m * n];
Arrays.fill(id, -1);
Arrays.fill(size, 1);
int count = 0;
for (int[] position : positions) {
// Assume a new node is added
count++;
int currLabel = getLabel(position[0], position[1]);
id[currLabel] = currLabel;
for (int i = 0; i < 4; i++) {
int y = position[0] + dy[i];
int x = position[1] + dx[i];
int nextLabel = getLabel(y, x);
if (x < 0 || y < 0 || x >= cols || y >= rows || id[nextLabel] == -1) {
continue;
}
if (union(currLabel, nextLabel)) {
count--;
}
}
            result.add(count);
}
return result;
}

private void union() {

}

private int root(int i) {
while (i != id[i]) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}

private boolean union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) {
return false;
}
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
return true;
}
}

[1ST TRY]
在LintCode上面做的，和leetcode的interface不太一样
完全自己写的，没有优化过
有空再做一下

有两个问题
1.在用dx, dy进行bfs的时候，一定要检查是不是出界！！！！！
  因为我用一维array表示的二维matrix，所以在这里犯了一个错误
  要在原始的二维matrix里面check valid 而不是只要在一维里不出界就可以了

2.算是题目的一个坑吧，就是同一个点重复加入
  改正方法很简单，如果当前点已经是island了的话就不用count++了


/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    /**
     * @param n an integer
     * @param m an integer
     * @param operators an array of point
     * @return an integer array
     */
    private int[] dx = {1, 0, -1, 0};
    private int[] dy = {0, 1, 0, -1};
    private int[] father;
    private boolean[] isIsland;
    private int count;
    public List<Integer> numIslands2(int n, int m, Point[] operators) {
        // Write your code here
        List<Integer> result = new ArrayList<>();
        if (n <= 0 || m <= 0 || operators == null || operators.length == 0) return result;
        father = new int[n * m];
        isIsland = new boolean[n * m];
        count = 0;
        for (int i = 0 ; i < father.length; i++) {
            father[i] = i;
        }
        for (int j = 0; j < operators.length; j++) {
            Point curr = operators[j];
            int x = curr.x, y = curr.y;
            int hash = x * m + y;
            int newHash;
            if (!isIsland[hash]) {
                isIsland[hash] = true;
                count++;
            }
         
            for (int k = 0; k < 4; k++) {
                newHash = (x + dx[k]) * m + y + dy[k];
                if (isValid(n, m, x + dx[k], y + dy[k]) && isIsland[newHash]) union(hash, newHash);
            }
            result.add(count);
            /*
            if (j >= 21) {
                System.out.println("(" + x + ", " + y + ")" + count);
            for (int row = 0; row < n; row++) {
                for (int col = 0; col < m; col++) {
                    int value = isIsland[row * m + col] ? 1 : 0;
                    System.out.print(value + " ");
                }
                System.out.println();
            }
            System.out.println();
            }
            */
         
         
        }
        return result;
    }
    private boolean isValid(int rows, int cols, int x, int y) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
    private int find(int x) {
        if (father[x] == x) return x;
        father[x] = find(father[x]);
        return father[x];
    }
    private void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            father[rootA] = rootB;
            count--;
        }
    }
}