LeetCode题解1020.number-of-enclaves

题目地址

https://leetcode-cn.com/problems/number-of-enclaves/

题目描述

给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。

移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。

返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。

 

示例 1：

输入：[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：
有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
示例 2：

输入：[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：
所有 1 都在边界上或可以到达边界。
 

提示：

1 <= A.length <= 500
1 <= A[i].length <= 500
0 <= A[i][j] <= 1
所有行的大小都相同

解法一 (暴力法)

思路

这是一个典型的可以使用 DFS 进行解决的一类题目， LeetCode 相关的题目有很多。

对于这种题目不管是思路还是代码都有很大的相似性，我们来看下。

暴力法的思路很简单，我们遍历整个矩阵：

• 如果遍历到 0，我们不予理会
• 如果遍历到 1. 我们将其加到 temp
• 我们不断拓展边界（上下左右）
• 如果 dfs 过程中碰到了边界，说明我们可以逃脱，我们将累加的 temp 清空
• 如果 dfs 过程之后没有碰到边界，说明我们无法逃脱。我们将 temp 加到 cnt
• 最终返回 cnt 即可

关键点解析

• visited 记录访问过的节点，防止重复计算

代码

Python Code:

class Solution:
    temp = 0
    meetEdge = False

    def numEnclaves(self, A: List[List[int]]) -> int:
        cnt = 0
        m = len(A)
        n = len(A[0])
        visited = set()

        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or (i, j) in visited:
                return
            visited.add((i, j))
            if A[i][j] == 1:
                self.temp += 1
            else:
                return
            if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                self.meetEdge = True
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)
        for i in range(m):
            for j in range(n):
                dfs(i, j)
                if not self.meetEdge:
                    cnt += self.temp
                self.meetEdge = False
                self.temp = 0
        return cnt

解法二 (消除法)

思路

上面的解法时间复杂度和空间复杂度都很差，我们考虑进行优化， 这里我们使用消除法。

• 从矩阵边界开始 dfs
• 如果碰到 1 就将其变成 0
• 如果碰到 0 则什么都不做
• 最后我们遍历整个矩阵，数一下 1 的个数即可。

关键点解析

• dfs 消除法

代码

Python Code:

#
# @lc app=leetcode.cn id=1020 lang=python3
#
# [1020] 飞地的数量
#

# @lc code=start


class Solution:

    def numEnclaves(self, A: List[List[int]]) -> int:
        cnt = 0
        m = len(A)
        n = len(A[0])

        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or A[i][j] == 0:
                return
            A[i][j] = 0

            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)
        for i in range(m):
            dfs(i, 0)
            dfs(i, n - 1)
        for j in range(1, n - 1):
            dfs(0, j)
            dfs(m - 1, j)
        for i in range(m):
            for j in range(n):
                if A[i][j] == 1:
                    cnt += 1
        return cnt

        # @lc code=end

参考

• 200.number-of-islands

可以在没有操作系统的情况下运行Java程序吗？ - java

我知道所有Java程序都由JVM执行。这使Java与所有操作系统兼容（一次编写，可在任何地方运行）。但是我可以在没有操作系统的情况下运行Java程序吗？也许只运行JVM？并且，如果可能，功能是否会受到任何影响？注意：我的主要问题是，java程序可以直接在硬件上运行（通过JVM）吗？我可以在计算机中“启动”任何低级别的JVM吗？ java大神给出的解决方案 实…

查看抽象类的方法是否未被扩展类之一覆盖的方法 - java

我有一个抽象类，比如AbstractClass和扩展该抽象类的多个其他类（700多个）。 AbstractClass有一个方法，比方说baseMethod()，它不是抽象方法。许多类（500+）覆盖该方法并具有自己的实现。现在，通过eclipse，我可以很容易地看到通过Ctrl+Shift+G覆盖该方法的方法，但是除了手动以外，还有其他方法可以看到不覆盖该方…

USB设备发行 - python

我目前正在使用PyUSB。由于我不熟悉USB，所以我不知道如何执行以下操作。我已经从Python PyUSB成功连接到我的USB设备硬件。在代码中，我需要重置USB设备硬件。通过向硬件发送命令来完成。现在，在硬件重置后，我想从Python PyUSB释放当前的USB设备。然后，我想在重置后将其重新连接到USB设备硬件。请让我知道，如何释放USB设备连接和接口…

使用Java检测用户计算机上是否安装了某些软件 - java

我有一个Java应用程序，它需要某些软件（其中一个是Perl）才能运行。我用来检测Perl的方法是：Runtime.getRuntime().exec("perl Test.pl"); 如果存在IOException，则声明不存在Perl。但是，我的一位用户抱怨该应用程序不断失败，因为他没有将Perl放在其路径变量中。所以这就是为什么我要…

如何修改休眠的SQL查询？ - java

我有点好奇，有没有办法修改hibernate的核心，以便我可以自定义生成的SQL query。例如，在生成的查询中添加功能以使用connect by prior（oracle）或我要自定义的任何其他子句。 java大神给出的解决方案 起初，这样的问题总是在我心中敲响警钟。你被警告了...AFAIK，hibernate使用所谓的dialects进行特定的优化。…