Number of Islands
200. Number of Islands
def numIslands(self, grid: List[List[str]]) -> int:
if not grid: return 0
self.grid = grid
count = 0
self.m, self.n = len(grid), len(grid[0])
for i in range(self.m):
for j in range(self.n):
if grid[i][j] == '1':
self.helper(i, j)
count+=1
return count
def helper(self, i, j):
self.grid[i][j] = '0'
for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
x = i + dx
y = j + dy
if 0 <= x < self.m and 0 <= y < self.n and self.grid[x][y] == '1':
self.helper(x, y)305 Number of Islands II
A 2d grid initials with zeroes. Given a list of positions to operate, count the number of islands after each addLand operation. Example:
Input: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]] Output: [1,1,2,3]
Use UnionFind, no group in the beginning, init all father node as -1
Check if neighbor has initiated(father[x]>0)
class UnionFind{
int count;
int[] father = null;
int[] size = null;
public UnionFind(int n){
this.count = 0;
father = new int[n];
size = new int[n];
for(int i=0; i<n; i++){
father[i] = -1;
}
}
public void addIsland(int x){
father[x] = x;
size[x] = 1;
count++;
}
public int find(int x){
if(father[x] != x) father[x] = find(father[x]);
return father[x];
}
public void union(int x, int y){
int x_root = find(x);
int y_root = find(y);
if(x_root != y_root){
if(size[x_root] > size[y_root]){
father[y_root] = x_root;
size[x_root] += size[y_root];
}else{
father[x_root] = y_root;
size[y_root] += size[x_root];
}
count--;
}
}
public boolean isValid(int x){
// System.out.println(x);
return father[x] >= 0;
}
public int getCount(){
return count;
}
}
public List<Integer> numIslands2(int m, int n, int[][] positions) {
UnionFind uf = new UnionFind(m*n);
List<Integer> ans = new ArrayList<>();
for(int[] p: positions){
int num = p[0]*n + p[1];
uf.addIsland(num);
if(p[0]>0 && uf.isValid(num-n)) uf.union(num, num-n);
if(p[0]<m-1 && uf.isValid(num+n)) uf.union(num, num+n);
if(p[1]>0 && uf.isValid(num-1)){
// System.out.println("here");
uf.union(num, num-1);
}
if(p[1]<n-1 && uf.isValid(num+1)) uf.union(num, num+1);
ans.add(uf.getCount());
}
return ans;
}694. Number of Distinct Islands
Given a non-empty 2D array grid of 0's and 1's,Count the number of distinct islands. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.
Shift the nodes to original trigger point
Use Set to compare the islands
def numDistinctIslands(self, grid: List[List[int]]) -> int:
self.m, self.n = len(grid), len(grid[0])
self.grid = grid
counts = set()
for i in range(self.m):
for j in range(self.n):
if grid[i][j] == 1:
count = set()
self.helper(i, j, i, j, count)
counts.add(frozenset(count))
return len(counts)
def helper(self, i, j, i0, j0, count):
count.add((i-i0, j-j0))
self.grid[i][j] = 0
for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
x = i + dx
y = j + dy
if 0 <= x < self.m and 0 <= y < self.n and self.grid[x][y] == 1:
self.helper(x, y, i0, j0, count)463. Island Perimeter
Only has 1 island
"""
遇到 1, 判斷上下左右是不是島嶼的一部份 減去邊長
"""
def islandPerimeter(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
line = 4
if i != 0 and grid[i-1][j]:
line -= 1
if i != m-1 and grid[i+1][j]:
line -= 1
if j != 0 and grid[i][j-1]:
line -= 1
if j != n-1 and grid[i][j+1]:
line -= 1
count += line
return countImage Matching
/**
* Given two 2-D grid, find out the number of region that if grid1 can cover grid2
* For example:
*
* 101 101
* 101 100
* 100 100 return 2 cuz second region in grid1 covers the region in grid2
*
* Thought:
* 1. dfs from grid2 to search the boundary of each region.
* 2. In the process of dfs, check if the boundary goes beyond grid1
*/
public class imageMatching {
private int image(int[][] grid1, int[][] grid2){
int count=0;
int m = grid2.length;
int n = grid2[0].length;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(grid2[i][j] == 1 && dfs(grid1, grid2, i, j)) count++;
}
}
return count;
}
private boolean dfs(int[][] grid1, int[][] grid2, int i, int j){
int m = grid2.length;
int n = grid2[0].length;
grid2[i][j] = 0;
boolean up = true, down = true, left = true, right = true;
if(i>0 && grid2[i-1][j] == 1) up = dfs(grid1, grid2, i-1, j);
if(i<m-1 && grid2[i+1][j] == 1) down = dfs(grid1, grid2, i+1, j);
if(j>0 && grid2[i][j-1] == 1) left = dfs(grid1, grid2, i, j-1);
if(j<n-1 && grid2[i][j+1] == 1) right = dfs(grid1, grid2, i, j+1);
return grid1[i][j] == 1 && left && right && up && down;
}Image Matching 2
/**
* Given two 2-D grid, find out the number of identical region of 2 grids
* For example:
*
* 101 101
* 101 101
* 100 101 return 1
*
* Thought:
* 1. grid1 and grid2 make a OR operation, dfs from OrMap to search the boundary of each region.
* 2. In the process of dfs, check if grid1 and grid2 the same
*/
static int countMatches(List<String> grid1, List<String> grid2) {
int count = 0;
int m = grid1.size();
int n = grid1.get(0).length();
int[][] g1 = new int[m][n];
int[][] g2 = new int[m][n];
int[][] orMap = new int[m][n];
// create g1 and g2
for(int i=0; i<m; i++){
char[] str1 = grid1.get(i).toCharArray();
char[] str2 = grid2.get(i).toCharArray();
for(int j=0; j<n; j++){
g1[i][j] = str1[j] - '0';
g2[i][j] = str2[j] - '0';
}
}
// create orMap
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
orMap[i][j] = g1[i][j] | g2[i][j];
}
}
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(orMap[i][j] == 1 && dfs(g1, g2, orMap, i, j)) count++;
}
}
return count;
}
private static boolean dfs(int[][] g1, int[][] g2, int[][] orMap, int i, int j){
int m = orMap.length;
int n = orMap[0].length;
orMap[i][j] = 0;
boolean up = true, down = true, left = true, right = true;
if(i>0 && orMap[i-1][j] == 1) up = dfs(g1, g2, orMap, i-1, j);
if(i<m-1 && orMap[i+1][j] == 1) down = dfs(g1, g2, orMap, i+1, j);
if(j>0 && orMap[i][j-1] == 1) left = dfs(g1, g2, orMap, i, j-1);
if(j<n-1 && orMap[i][j+1] == 1) right = dfs(g1, g2, orMap, i, j+1);
return g1[i][j]==1 && g2[i][j]==1 && up && down && left && right;
}Last updated