为什么算法问题的实现不起作用? [英] Why does an implementation of an algorithmic problem not work?

问题描述

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

The question is to find the number of islands. 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不起作用.我正在运行一个循环，其中每个语句都进行递归调用.

Can anyone please explain why 2 doesn't work. I'm running a loop in which every statement gives a recursive call.

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

But this logic works in Java, why? https://www.youtube.com/watch?v=R4Nh-EgWjyQ

推荐答案

第二个代码也将对角线视为有效.这就是为什么它与第一个不同的原因.

The second code also consider diagonals as valid. This is why it differs from the first one.

11000
11000
00100
00011

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

Both are valid codes but they do not answer the same question. The above input, first will return 1 and second 3.

这篇关于为什么算法问题的实现不起作用?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！