leetcode
leetcode 1401 ~ 1450
二维网格图中探测环

二维网格图中探测环

难度:

标签:

题目描述

给你一个二维字符网格数组 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`函数使用了路径压缩技术,请问这是如何帮助提高并查集操作效率的?
路径压缩是并查集优化技术中的一种,它可以显著减少在查找节点的根节点时所需的时间。具体来说,当我们在执行`find`函数寻找某个元素的根节点时,路径压缩技术会使得这个元素及其所有祖先节点直接或间接地指向根节点。这样,下一次再查找这些节点或它们的任何子节点时,可以更快地直接到达根节点。因此,路径压缩减少了树的高度,有效地减少了查询和合并操作的时间复杂度,从而提高了并查集的整体效率。
🦆
题解中提到,如果两个格子已经在同一个集合中还尝试进行合并,就表示存在环。能否详细解释为什么这种情况下一定形成了环?
在并查集中,每个集合表示一组互相连接的节点。当尝试合并两个已处于同一集合中的节点时,意味着这两个节点可以通过集合内的其他节点间接连接。这种情况下,如果再通过一个直接的连接尝试将它们合并,实际上在这两个节点之间就形成了至少两条不同的路径连接它们,从而形成了一个环。因此,当并查集检测到两个已经在同一个集合中的节点尝试合并时,我们可以确信在这个集合中存在至少一个环。
🦆
并查集中的`unite`函数直接将一个节点的父节点设置为另一个节点,这是否意味着并查集使用的是按秩合并优化?如果不是,这种做法可能有什么潜在问题?
在这个题解中,`unite`函数简单地将一个节点的父节点设置为另一个节点,并没有使用按秩合并优化。按秩合并是另一种优化技术,其中“秩”通常代表集合的大小或树的深度。在按秩合并中,我们通常将较小或较浅的树合并到较大或较深的树上,这样可以防止树的深度快速增加,从而保持操作的效率。没有使用按秩合并的潜在问题是,合并操作可能导致树的深度增加,尤其是在频繁合并时,可能会形成较深的树结构,从而增加后续操作的时间复杂度。

相关问题