三刷 06/2022
Version #2 Union Find
有两个比答案写的好的地方
一个就是在Union的时候只向右和向下看，这样可以少搜两个方向
第二个就是不需要一开始用M * N的时间先算出grid==1的count，可以一边搜一边加->又想了一下这里其实没有extra的时间消耗，因为initialize id和size array本来就需要MN的时间，所以这里怎么implement都无所谓
一个可以提高的地方是看到之前一刷的时候写了一个getLabel函数来计算y* cols + x，感觉写的很好这次可以借鉴
Time O(MN)
Space O(MN)
Runtime: 13 ms, faster than 15.14% of Java online submissions for Number of Islands.
Memory Usage: 57.9 MB, less than 21.91% of Java online submissions for Number of Islands.
class Solution {
class UnionFind {
private int[] size;
private int[] id;
private int count;
public UnionFind(int N) {
size = new int[N];
id = new int[N];
for (int i = 0; i < N; i++) {
size[i] = 1;
id[i] = i;
}
}
public int root(int i) {
while (id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}
public void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) {
return;
}
count--;
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
}
public int count() {
return count;
}
public void addCount(int n) {
count += n;
}
}
public int numIslands(char[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int N = rows * cols;
UnionFind uf = new UnionFind(N);
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (grid[y][x] != '1') {
continue;
}
uf.addCount(1);
if (x + 1 < cols && grid[y][x + 1] == '1') {
uf.union(y * cols + x, y * cols + x + 1);
}
if (y + 1 < rows && grid[y + 1][x] == '1') {
uf.union(y * cols + x, (y + 1) * cols + x);
}
}
}
return uf.count();
}
}
二刷 05/2022
Version #3 BFS
Time O(MN)
Space O(MN)
Runtime: 8 ms, faster than 25.92% of Java online submissions for Number of Islands.
Memory Usage: 57.1 MB, less than 54.74% of Java online submissions for Number of Islands.
class Solution {
public int numIslands(char[][] grid) {
// create a visited matrix
// iterate over all (x, y) values
// if a grid is a island and has never been visited, add the land number by 1 and expand that island by bfs
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
return 0;
}
int cnt = 0;
boolean[][] visited = new boolean[grid.length][grid[0].length];
for (int y = 0; y < grid.length; y++) {
for (int x = 0; x < grid[0].length; x++) {
if (!visited[y][x] && grid[y][x] == '1') {
cnt++;
expandIsland(grid, y, x, visited);
}
}
}
return cnt;
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private void expandIsland(char[][] grid, int y, int x, boolean[][] visited) {
Queue<int[]> que = new ArrayDeque<>();
que.offer(new int[]{y, x});
visited[y][x] = true;
while (!que.isEmpty()) {
int[] curr = que.poll();
// y = curr[0], x = curr[1]
for (int i = 0; i < 4; i++) {
int ny = curr[0] + dy[i];
int nx = curr[1] + dx[i];
if (ny < 0 || ny >= grid.length || nx < 0 || nx >= grid[0].length) {
continue;
}
if (grid[ny][nx] == '1' && !visited[ny][nx]) {
visited[ny][nx] = true;
que.offer(new int[]{ny, nx});
}
}
}
}
}
一刷
Version #2 Union Find
14.61 %
class Solution {class UF {
private int[] id;
private int[] size;
private int N;
public int count;
public UF(char[][] grid) {
this.count = 0;
this.N = grid.length * grid[0].length;
id = new int[N];
size = new int[N];
for (int y = 0; y < grid.length; y++) {
for (int x = 0; x < grid[0].length; x++) {
if (grid[y][x] == '1') {
count++;
}
int currLabel = getLabel(y, x);
id[currLabel] = currLabel;
size[currLabel] = 1;
}
}
}
private int root(int i) {
while (id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}
public void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) {
return;
}
this.count--;
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
}
public boolean connected(int p, int q) {
return root(p) == root(q);
}
}
private int rows;
private int cols;
public int numIslands(char[][] grid) {
if(grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
return 0;
}
this.rows = grid.length;
this.cols = grid[0].length;
UF uf = new UF(grid);
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (grid[y][x] == '1') {
if (y != rows - 1 && grid[y + 1][x] == '1') {
uf.union(getLabel(y, x), getLabel(y + 1, x));
}
if (x != cols - 1 && grid[y][x + 1] == '1') {
uf.union(getLabel(y, x), getLabel(y, x + 1));
}
}
}
}
return uf.count;
}
private int getLabel(int y, int x) {
return y * cols + x;
}
}
Version #1 DFS
Explanation from LeetCode:
"The algorithm works as follow:
- Scan each cell in the grid.
- If the cell value is '1' explore that island.
- Mark the explored island cells with 'x'.
- Once finished exploring that island, increment islands counter.
The arrays dx[], dy[] store the possible moves from the current cell. Two land cells ['1'] are considered from the same island if they are horizontally or vertically adjacent (possible moves (-1,0),(0,1),(0,-1),(1,0)). Two '1' diagonally adjacent are not considered from the same island."
41.53 %
public class Solution {
private int count = 0;
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
for (int x = 0; x < rows; x++) {
for (int y = 0; y < cols; y++) {
if (grid[x][y] == '1') {
dfs(grid, x, y);
count++;
}
}
}
return count;
}
private int[] dx = {1, 0, -1, 0};
private int[] dy = {0, 1, 0, -1};
private void dfs(char[][] grid, int x, int y) {
grid[x][y] = 'x';
int nx, ny;
for (int k = 0; k < 4; k++) {
nx = x + dx[k];
ny = y + dy[k];
if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length) {
if (grid[nx][ny] == '1') dfs(grid, nx, ny);
}
}
}
}
No comments:
Post a Comment