题目
image.png
题解
题解1：dfs
Java题解
class Solution {
public int[][] next = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int rows;
public int cols;
boolean[][] visited;
public int numIslands(char[][] grid) {
if (grid.length==0 || grid[0].length==0) return 0; // grid==null不行
rows = grid.length;
cols = grid[0].length;
int res = 0;
// boolean[][] visited = new boolean[rows][cols];
visited = new boolean[rows][cols];
for (int i=0; i<rows; i++){
for (int j=0; j<cols; j++){
// if (helper(grid, visited, i, j))
// res += 1;
if (!visited[i][j] && grid[i][j]=='1'){ //
helper(grid, i, j);
res += 1;
}
}
}
return res;
}
private boolean isValid(int i, int j){
if (i>=0 && i<rows && j>=0 && j<cols)
return true;
return false;
}
private void helper(char[][] grid, int i, int j){
if (!isValid(i, j) || visited[i][j]) return;
if (grid[i][j] == '1'){
visited[i][j] = true;
for (int m=0; m<4; m++){
helper(grid, i+next[m][0], j+next[m][1]);
}
// visited[i][j] = false;
}
return;
}
}
dfs不一定要用for循环和位置数组
// dfs
// 是否visit过，1的话就往下dfs，visit状态改变
// 或者1变为0？
class Solution {
private boolean[][] visited;
private int rows;
private int cols;
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int res = 0;
rows = grid.length;
cols = grid[0].length;
visited = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (!visited[i][j] && grid[i][j] == '1') {
dfs(grid, i, j);
res += 1;
}
}
}
return res;
}
private boolean valid(int i, int j) {
if (i < 0 || i >= rows || j < 0 || j >= cols) {
return false;
}
return true;
}
private void dfs(char[][] grid, int i, int j) {
if (!valid(i, j) || visited[i][j]) {
return;
}
if (grid[i][j] == '1') {
visited[i][j] = true;
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
return;
}
}
不用visited，把1改成0
但是
解决这个问题是可以不用建立 visited 数组，但有以下的知识点需要大家知道。
1、对于算法的输入而言，很多时候是介意修改输入的，除非题目就是要我们修改输入数据；
2、再者 visited 数组没有必要节约这个空间，现在空间越来越不值钱了，而且程序执行完成以后，空间可以回收。我们写算法的时候，应该力求时间复杂度最优，并且代码可读性强。
问清楚面试官，是否可以修改传来的 nums 数组！
// dfs
// 是否visit过，1的话就往下dfs，visit状态改变
// 或者1变为0？
class Solution {
private int rows;
private int cols;
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int res = 0;
rows = grid.length;
cols = grid[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
res += 1;
}
}
}
return res;
}
private boolean valid(int i, int j) {
if (i < 0 || i >= rows || j < 0 || j >= cols) {
return false;
}
return true;
}
private void dfs(char[][] grid, int i, int j) {
if (!valid(i, j)) {
return;
}
if (grid[i][j] == '1') {
grid[i][j] = '0';
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
return;
}
}
题解2：bfs：非递归
队列
// bfs
// 队列
// visited或是替换为0
class Pos{
int i;
int j;
// public void position(int i, int j) {
Pos(int i, int j) {
this.i = i;
this.j = j;
}
}
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
// 坐标传递
int rows = grid.length;
int cols = grid[0].length;
int res = 0;
// Queue<Pos> queue= new LinkedList<new Pos()>(); // Linkedlist
Queue<Pos> queue= new LinkedList<>();
// queue.add(new Pos(0, 0));
// 队列为空是什么情况，怎么计数
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
res += 1;
queue.add(new Pos(r, c));
while (!queue.isEmpty()) {
Pos current = queue.poll();
int i = current.i;
int j = current.j;
if (valid(i, j, rows, cols)) {
if (grid[i][j] == '1') {
grid[i][j] = '0';
queue.add(new Pos(i + 1, j));
queue.add(new Pos(i - 1, j));
queue.add(new Pos(i, j + 1));
queue.add(new Pos(i, j - 1));
}
}
}
}
}
}
// while (!queue.isEmpty()) {
// Pos current = queue.poll();
// int i = current.i;
// int j = current.j;
// if (valid(i, j, rows, cols)) {
// if (grid[i][j] == '1') {
// grid[i][j] = '0';
// queue.add(new Pos(i + 1, j));
// queue.add(new Pos(i - 1, j));
// queue.add(new Pos(i, j + 1));
// queue.add(new Pos(i, j - 1));
// }
// }
// }
return res;
}
private boolean valid(int i, int j, int rows, int cols) {
if (i < 0 || i >= rows || j < 0 || j >= cols) {
return false;
}
return true;
}
}
题解3：并查集
思路1
dfs遍历找与dummy不相连的1，dfs中把所有相连的1都与dummy连起来，所以有几个新的入口，就有几个岛屿
class UF {
private int count; // 连通分量
private int[] parent; // 树
private int[] size; // 树的重量
public UF(int n) {
this.count = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
} else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
count--;
}
public boolean connected(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}
public int count() {
return count;
}
}
// 思路1
// dfs遍历找与dummy不相连的1，把1与dummy连起来，所以有几个新的入口，就有几个岛屿
class Solution {
private int rows;
private int cols;
private UF uf;
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
rows = grid.length;
cols = grid[0].length;
// 把1的都连起来，找到几个1的入口就是res
uf = new UF(rows * cols + 1);
int res = 0;
int dummy = rows * cols;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1' && !uf.connected(dummy, (i * cols + j))) { // 是1，且与dummy不连接
// uf.union(i * j, dummy);
// 还是要用dfs去把与1连接的都连起来
dfs(grid, i, j, dummy);
res += 1;
}
}
}
return res;
}
private boolean valid(int i, int j) {
if (i < 0 || i >= rows || j < 0 || j >= cols) {
return false;
}
return true;
}
private void dfs(char[][] grid, int i, int j, int dummy) {
if (!valid(i, j)) {
return;
}
if (grid[i][j] == '1' && !uf.connected(dummy, (i * cols + j))) {
uf.union(dummy, (i * cols + j));
dfs(grid, i + 1, j, dummy);
dfs(grid, i - 1, j, dummy);
dfs(grid, i, j + 1, dummy);
dfs(grid, i, j - 1, dummy);
}
return;
}
}
思路2
class UF {
private int count; // 连通分量
private int[] parent; // 树
private int[] size; // 树的重量
public UF(int n) {
this.count = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
} else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
count--;
}
public boolean connected(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}
public int count() {
return count;
}
}
// 思路1
// 把0和dummy连接，把1的都连起来，最后计数连通分量-1，减去的1是指dummy那个
class Solution {
private int rows;
private int cols;
private UF uf;
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
rows = grid.length;
cols = grid[0].length;
uf = new UF(rows * cols + 1);
int dummy = rows * cols;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '0') {
uf.union(dummy, (i * cols + j));
}
// 向下向右遍历1的周边
if (grid[i][j] == '1') {
if (valid(i + 1, j)) { // 向下
if (grid[i + 1][j] == '1') {
uf.union((i * cols + j), ((i + 1) * cols + j));
}
}
if (valid(i, j + 1)) {
if (grid[i][j + 1] == '1') {
uf.union((i * cols + j), (i * cols + (j + 1)));
}
}
}
}
}
return uf.count() - 1;
}
private boolean valid(int i, int j) {
if (i < 0 || i >= rows || j < 0 || j >= cols) {
return false;
}
return true;
}
}
参考
image.png
