岛屿类型的问题 -- 主要是 bfs + 一些处理方式
在这个问题中，几个关键点 **四联通 沉岛思想 bfs dfs **累加和沉岛的操作台 offer() 后开始操作，代表已经进队了
class Solution {
int[] dx = new int[]{1, 0, 0, -1};
int[] dy = new int[]{0, 1, -1, 0};
public int maxAreaOfIsland(int[][] grid) {
int ans = 0, cur = 1;
int m = grid.length, n = grid[0].length;
Queue<int[]> que = new LinkedList<>();
for (int i = 0; i < m; i ++) {
for (int j = 0; j < n; j ++) {
if (grid[i][j] == 1) {
que.offer(new int[]{i, j});
// 进行累加和沉岛的处理
cur ++;
grid[i][j] = 0;
// BFS
while (! que.isEmpty()) {
int[] cell = que.poll();
int x = cell[0], y = cell[1];
for (int k = 0; k < 4; k ++) {
int mx = x + dx[k], my = y + dy[k];
// 边界条件
if (mx >= 0 && mx < m && my >= 0 && my < n && grid[mx][my] == 1) {
que.offer(new int[]{mx, my});
// 累加 沉岛
cur ++;
grid[mx][my] = 0;
}
}
}
}
ans = Math.max(ans, cur);
cur = 1;
}
}
return ans;
}
}
还有 dfs 的方法，两个方法主要区别就是一个栈 队 的不同，LILO 和LIFO
class Solution {
int[] dx = new int[]{1, 0, 0, -1};
int[] dy = new int[]{0, 1, -1, 0};
public int maxAreaOfIsland(int[][] grid) {
int ans = 0, cur = 1;
int m = grid.length, n = grid[0].length;
Queue<int[]> que = new LinkedList<>();
for (int i = 0; i < m; i ++) {
for (int j = 0; j < n; j ++) {
ans = Math.max(ans, dfs(grid, i, j));
}
}
return ans;
}
// 递归函数，由函数隐含的维护了一个栈
private int dfs(int[][] grid, int i, int j) {
int ans = 0;
if (i >= grid.length || i < 0 || j >= grid[0].length || j < 0 || grid[i][j] == 0) {
return 0;
}
ans ++;
grid[i][j] = 0;
for (int k = 0; k < 4; k ++) {
ans += dfs(grid, i + dx[k], j + dy[k]);
}
return ans;
}
}
这里由于函数递归，隐含维护了一个栈，所以它所用的内存空间要大一些，时间复杂度是一样的。
在第二道题里面有一个细节就是 队里面的元素需要操作 这样每一层要有具体的操作
class Solution {
public Node connect(Node root) {
Queue<Node> que = new LinkedList<>();
if (root == null) return root;
que.offer(root);
while (!que.isEmpty()) {
int size = que.size();
for (int i = 0; i < size; i ++) {
// 取出节点
Node node = que.poll();
// 连接节点
if (i < size - 1) {
node.next = que.peek();
}
// 填充节点到队列
if (node.left != null) {
que.offer(node.left);
}
if (node.right != null) {
que.offer(node.right);
}
}
}
return root;
}
}