二维网格图中探测环
难度:
标签:
题目描述
给你一个二维字符网格数组 grid
,大小为 m x n
,你需要检查 grid
中是否存在 相同值 形成的环。
一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子,你可以移动到它上、下、左、右四个方向相邻的格子之一,可以移动的前提是这两个格子有 相同的值 。
同时,你也不能回到上一次移动时所在的格子。比方说,环 (1, 1) -> (1, 2) -> (1, 1)
是不合法的,因为从 (1, 2)
移动到 (1, 1)
回到了上一次移动时的格子。
如果 grid
中有相同值形成的环,请你返回 true
,否则返回 false
。
示例 1:
输入:grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]] 输出:true 解释:如下图所示,有 2 个用不同颜色标出来的环:![]()
示例 2:
输入:grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]] 输出:true 解释:如下图所示,只有高亮所示的一个合法环:![]()
示例 3:
输入:grid = [["a","b","b"],["b","z","b"],["b","b","a"]] 输出:false
提示:
m == grid.length
n == grid[i].length
1 <= m <= 500
1 <= n <= 500
grid
只包含小写英文字母。
代码结果
运行时间: 163 ms, 内存: 58.8 MB
/*
* The goal is to check if there's a cycle formed by the same character in a 2D grid using Java Streams.
* While Java Streams are not typically used for DFS, we will still leverage lambdas and functional interfaces for a more modern approach.
*/
import java.util.function.BiFunction;
public class Solution {
private int rows, cols;
private char[][] grid;
private boolean[][] visited;
private final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public boolean containsCycle(char[][] grid) {
this.rows = grid.length;
this.cols = grid[0].length;
this.grid = grid;
this.visited = new boolean[rows][cols];
BiFunction<Integer, Integer, Boolean> dfs = new BiFunction<>() {
@Override
public Boolean apply(Integer x, Integer y) {
if (visited[x][y]) {
return length >= 4;
}
visited[x][y] = true;
for (int[] dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && !(nx == px && ny == py) && grid[nx][ny] == ch) {
if (dfs.apply(nx, ny)) {
return true;
}
}
}
visited[x][y] = false;
return false;
}
};
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (!visited[i][j] && dfs.apply(i, j)) {
return true;
}
}
}
return false;
}
}
解释
方法:
这个题解使用了并查集(Union-Find)的数据结构来解决问题。并查集是一种用于处理一些不相交集合的合并及查询问题的数据结构。这里,我们将二维网格中的每个格子视为一个节点,节点的编号可以通过行号和列号转换得到,即 i * n + j(i为行号,j为列号,n为列数)。当两个相邻的格子具有相同的值时,我们将它们所在的集合进行合并。如果在尝试合并两个集合时发现它们已经在同一个集合中,说明存在一个环。这是因为我们只有在发现两个相同的字符时才进行合并操作,所以如果两个已经在同一个集合中的节点尝试合并,意味着这两个节点是通过同一种字符相连的,因此形成了环。
时间复杂度:
O(m*n)
空间复杂度:
O(m*n)
代码细节讲解
🦆
在题解中,并查集的`find`函数使用了路径压缩技术,请问这是如何帮助提高并查集操作效率的?
▷🦆
题解中提到,如果两个格子已经在同一个集合中还尝试进行合并,就表示存在环。能否详细解释为什么这种情况下一定形成了环?
▷🦆
并查集中的`unite`函数直接将一个节点的父节点设置为另一个节点,这是否意味着并查集使用的是按秩合并优化?如果不是,这种做法可能有什么潜在问题?
▷