时间戳

首页 > 解决方案 > 为什么算法问题的实现不起作用？

python - 为什么算法问题的实现不起作用？

问题描述

问题是找出岛屿的数量。https://leetcode.com/problems/number-of-islands/

解决方案1：

class Solution:    
    def dfs(self, row, column, grid):
        if row < 0 or column < 0 or row>= len(grid) or column >= len(grid[0]):
            return 0
        if grid[row][column] == '0':
            return 0
        grid[row][column] = '0'                    
        self.dfs(row+1, column, grid)
        self.dfs(row-1, column, grid)
        self.dfs(row, column+1, grid)
        self.dfs(row, column-1, grid)
    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        for row in range(len(grid)):
            for column in range(len(grid[0])):
                if grid[row][column] == '1':
                    self.dfs(row, column, grid)
                    count += 1

        return count

解决方案2（不起作用）

class Solution:
    def dfs(self, row, column, grid):
        if row < 0 or column < 0 or row>= len(grid) or column >= len(grid[0]):
            return 0
        if grid[row][column] == '0':
            return 0
        grid[row][column] = '0'                    
        for i in range(-1, 2):
            for j in range(-1, 2):
                if i!=0 or j!=0:
                    self.dfs(row+i, column+j, grid)

    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        for row in range(len(grid)):
            for column in range(len(grid[0])):
                if grid[row][column] == '1':
                    self.dfs(row, column, grid)
                    count += 1
        return count

谁能解释一下为什么 2 不起作用。我正在运行一个循环，其中每个语句都进行递归调用。

但是这个逻辑在 Java 中有效，为什么呢？ https://www.youtube.com/watch?v=R4Nh-EgWjyQ

标签： pythonalgorithmdepth-first-search

解决方案

第二个代码也认为对角线是有效的。这就是它与第一个不同的原因。

11000
11000
00100
00011

两者都是有效代码，但它们不回答相同的问题。上面的输入，第一个会返回 1，第二个会返回 3。

推荐阅读