200. 岛屿数量

原始写的是这段代码，虽然能执行成功，但是不是很优雅

import "fmt"
var cnt int

func numIslands(grid [][]byte) int {
    cnt=0
    used := map[[2]int]bool{}

    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[i]); j++ {
            dfs(i,j,grid, used, 0)
            // fmt.Println(i,j)
        }
    }

    return cnt
}

func dfs(i int, j int, grid [][]byte, used map[[2]int]bool, depth int) {
    if used[[2]int{i,j}] {
        return
    }

    if grid[i][j] == 48 {
        return
    }
    
    if depth == 0 {
        cnt++
        // fmt.Println(cnt)
    }

    used[[2]int{i,j}] = true

    depth++

    // 上
    if i> 0 {
        dfs(i-1, j, grid, used, depth)
    }

    // 下
    if i < len(grid)-1 {
        dfs(i+1,j,grid,used, depth)
    }

    // 左
    if j>0 {
        dfs(i, j-1, grid, used, depth)
    }

    // 右
    if j < len(grid[i])-1 {
        dfs(i, j+1, grid, used, depth)
    }
}

优化这段代码：

这段代码的目的是计算一个二维 grid 中的岛屿数量（岛屿由值为 1 的相邻单元格组成）。优化点主要在于减少冗余逻辑和提升代码可读性。我们可以进行以下几个优化：

1. 移除不必要的 depth 参数：depth 仅用于判断是否递归的第一层，可以通过直接判断当前格子是否已经访问过和是否为岛屿来增加 cnt。
2. 减少重复的 used 判断：在 dfs 中每次递归之前判断是否已经访问过，可以减少逻辑冗余。
3. 直接在 numIslands 函数中判断是否需要调用 dfs：如果当前格子已经访问或不是岛屿，则不需要调用 dfs。

以下是优化后的代码：

import "fmt"

var cnt int

func numIslands(grid [][]byte) int {
    cnt = 0
    used := map[[2]int]bool{}

    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[i]); j++ {
            // 如果当前格子是岛屿并且没有被访问过，才进行 DFS
            if grid[i][j] == '1' && !used[[2]int{i, j}] {
                cnt++
                dfs(i, j, grid, used)
            }
        }
    }

    return cnt
}

func dfs(i, j int, grid [][]byte, used map[[2]int]bool) {
    if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[i]) || grid[i][j] == '0' || used[[2]int{i, j}] {
        return
    }

    used[[2]int{i, j}] = true

    // 上
    dfs(i-1, j, grid, used)
    // 下
    dfs(i+1, j, grid, used)
    // 左
    dfs(i, j-1, grid, used)
    // 右
    dfs(i, j+1, grid, used)
}

优化细节：

1. 简化了 dfs 函数调用的逻辑：通过提前判断边界和条件来减少递归深度的传递，不需要再维护 depth。
2. 减少了冗余的判断：在 numIslands 中，只有当当前格子是 1 并且没有被访问过时，才开始深度优先搜索，避免了不必要的 dfs 调用。
3. 代码更简洁可读：直接通过坐标来判断上下左右的格子，没有再单独去处理 depth 相关的逻辑。

这样，代码运行效率会更高，并且可读性也更好。

进一步优化

在进一步优化这段代码时，可以考虑以下几个方面：

1. 移除 used 变量：由于我们可以直接修改 grid，将访问过的岛屿格子改为 '0'，这样不需要额外维护一个 used 哈希表来记录访问状态。这样还能减少空间复杂度。

2. 减少递归开销：由于递归调用可能在深度较大时导致栈溢出，可以使用非递归的方式实现深度优先搜索 (DFS)。但为了简单起见，保持递归的实现并优化它。

3. 整合重复代码：可以将上、下、左、右的逻辑整合成方向数组，以减少重复的代码行。

优化后的代码如下：

import "fmt"

func numIslands(grid [][]byte) int {
    cnt := 0

    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[i]); j++ {
            if grid[i][j] == '1' {
                cnt++
                dfs(i, j, grid)
            }
        }
    }

    return cnt
}

func dfs(i, j int, grid [][]byte) {
    if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[i]) || grid[i][j] == '0' {
        return
    }

    // 标记已访问
    grid[i][j] = '0'

    // 定义方向数组，上下左右
    directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

    // 遍历四个方向
    for _, dir := range directions {
        ni, nj := i+dir[0], j+dir[1]
        dfs(ni, nj, grid)
    }
}

进一步优化后的改进点：

1. 移除了 used 变量：我们直接修改 grid 来标记已经访问过的节点，这样节省了空间复杂度，不需要额外维护一个哈希表。
2. 方向数组简化代码：用一个方向数组代替上下左右的手动递归调用，代码更加简洁，易于扩展到其他问题。
3. 递归更加直观：去掉了不必要的条件检查，将条件判断直接放在 dfs 开头，逻辑更加简洁。

时间和空间复杂度：

• 时间复杂度: O(M * N)，其中 M 和 N 分别是 grid 的行数和列数，每个元素最多访问一次。
• 空间复杂度: O(M * N)，最坏情况下，递归深度可能达到 M * N。

这段代码的性能已经比较接近理论最优，并且代码结构更加简洁，维护和理解成本更低。

总结：

最大的优化，通过 grid 中的1改成0，直接省略掉used或者叫visited数组。时间直接从超越5%升到80%

一个小技巧，方向遍历时定义方向数组：

// 定义方向数组，上下左右
directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
// 遍历四个方向
for _, dir := range directions {
	ni, nj := i+dir[0], j+dir[1]
	dfs(ni, nj, grid)
}

感慨一下，现在的chatgpt真的好用，学习东西时非常有用