Number Of Island
lc 200
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.
思路很简单就是找到一个land1，就一路dfs一路往下走，并且全都标称0，，最后越到几个1就count＋＋
public void removeIsLand(char[][] grid, int i, int j){
if ( i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] == '0' ) return;
grid[i][j] = '0';
removeIsLand(grid, i + 1, j);
removeIsLand(grid, i, j + 1);
removeIsLand(grid, i - 1, j);
removeIsLand(grid, i, j - 1);
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0 ) return 0;
int count = 0;
for ( int i = 0 ; i < grid.length; i++ ){
for ( int j = 0 ; j < grid[0].length; j++ ) {
if (grid[i][j] == '1' ){
count++;
removeIsLand(grid, i, j);
}
}
}
return count;
}
lc 305 Number of Island II
A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. 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.
Example:
Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]. Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).
0 0 0
0 0 0
0 0 0
Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.
1 0 0
0 0 0 Number of islands = 1
0 0 0
Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.
1 1 0
0 0 0 Number of islands = 1
0 0 0
Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.
1 1 0
0 0 1 Number of islands = 2
0 0 0
Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.
1 1 0
0 0 1 Number of islands = 3
0 1 0
We return the result as an array: [1, 1, 2, 3]
题意： 很明显，union find 秒这一道题
容易理解的做法，就是建uniton find class，然后每当遇到1的时候，先＋＋，就看上下左右四个防线，看看father相同否，不同的话，就union father就好了,这个时候要记得count--;
Time complexity: O(m \times n + L)O(m×n+L) where LL is the number of operations, mm is the number of rows and nn is the number of columns. it takes O(m \times n)O(m×n) to initialize UnionFind, and O(L)O(L) to process positions. Note that Union operation takes essentially constant time[1] when UnionFind is implemented with both path compression and union by rank.
Space complexity : O(m \times n)O(m×n) as required by UnionFind data structure.
public class Solution {
/**
* @param n an integer
* @param m an integer
* @param operators an array of point
* @return an integer array
*/
int converttoId(int x, int y, int m){
return x*m + y;
}
class UnionFind{
HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();
UnionFind(int n, int m){
for(int i = 0 ; i < n; i++) {
for(int j = 0 ; j < m; j++) {
int id = converttoId(i,j,m);
father.put(id, id);
}
}
}
int compressed_find(int x){
int parent = father.get(x);
while(parent!=father.get(parent)) {
parent = father.get(parent);
}
int temp = -1;
int fa = x;
while(fa!=father.get(fa)) {
temp = father.get(fa);
father.put(fa, parent) ;
fa = temp;
}
return parent;
}
void union(int x, int y){
int fa_x = compressed_find(x);
int fa_y = compressed_find(y);
if(fa_x != fa_y)
father.put(fa_x, fa_y);
}
}
public List<Integer> numIslands2(int n, int m, int[][] operators) {
// Write your code here
List<Integer> ans = new ArrayList<Integer>();
if(operators == null) {
return ans;
}
int []dx = {0,-1, 0, 1};
int []dy = {1, 0, -1, 0};
int [][]island = new int[n][m];
UnionFind uf = new UnionFind(n, m);
int count = 0;
for(int i = 0; i < operators.length; i++) {
count ++;
int x = operators[i][0];
int y = operators[i][1];
if(island[x][y] != 1){
island[x][y] = 1;
int id = converttoId(x,y , m);
for(int j = 0 ; j < 4; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
if(0 <= nx && nx < n && 0 <= ny && ny < m && island[nx][ny] == 1)
{
int nid = converttoId(nx, ny, m);
int fa = uf.compressed_find(id);
int nfa = uf.compressed_find(nid);
if(fa != nfa) {
count--;
//uf.union(nid, id);
uf.union(fa, nfa);
}
}
}
}
ans.add(count);
}
return ans;
}
}
public class Solution {
public List<Integer> numIslands2(int m, int n, int[][] positions) {
boolean[][] map = new boolean[m][n];// check whcih position is open;
int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};// direction
List<Integer> list = new ArrayList<Integer>();// ans
int island = 0;// ans
int[] fa = new int[m * n];// root
////////////////////////////////////
int[] rank = new int[m*n];// rank
Arrays.fill(rank, 1);
////////////////////////////////
//initialization
for (int i = 0; i < m * n; i++) {
fa[i] = i;
}
for (int i = 0; i < positions.length; i++) {
island++;
map[positions[i][0]][positions[i][1]] = true;
int x, y;
//int root = positions[i][0] * n + positions[i][1];
int root = getfather(fa, positions[i][0] * n + positions[i][1]);
for (int k = 0; k < 4; k++) {
x = positions[i][0] + dir[k][0];
y = positions[i][1] + dir[k][1];
//int curRoot = getfather(fa, x*n+y);
if (x >= 0 && x < m && y >=0 && y < n && map[x][y] && getfather(fa, x*n+y) != getfather(fa, root)) {
//fa[getfather(fa, x * n + y)] = root;
int curRoot = getfather(fa, x*n+y);
union(root, curRoot, rank, fa);
island--;
}
}
list.add(island);
}
return list;
}
// i, j is the roots;
public void union(int p, int q, int[] rank, int[] fa) {
int i = getfather(fa,p), j = getfather(fa,q);
if (rank[i] < rank[j]) { //weighted quick union
fa[i] = j; rank[j] += rank[i];
} else {
fa[j] = i;
rank[i] += rank[j];
}
}
//disjoint-set and path compression
public int getfather(int[] fa, int i) {
if (fa[i] == i) {
return i;
}
fa[i] = getfather(fa, fa[i]);//path compression here
return fa[i];
}
}