关于golang:golangleetcode中级岛屿数量电话号码的字母组合

第一题 岛屿数量

题目

解题思路

代码

//dfs 函数通过深搜遍历一个岛屿，并将岛屿的 1 全都置 0
func dfs(grid [][]byte,r int,c int) {nr := len(grid)
    nc := len(grid[0])

    if r < 0 || c < 0 || r >= nr || c >= nc || grid[r] == '0' {return}

    grid[r] = '0'
    dfs(grid, r - 1, c)
    dfs(grid, r + 1, c)
    dfs(grid, r, c - 1)
    dfs(grid, r, c + 1)
}
func numIslands(grid [][]byte) int {if grid == nil || len(grid)== 0 {return 0}

    nr := len(grid)
    nc := len(grid[0])
    numIslands := 0
    // 遍历 gird 数组为岛屿计数
    for  r := 0; r < nr; r++ {
        for c := 0; c < nc; c++ {if grid[r] == '1' {
            numIslands++
            dfs(grid, r, c)
            }
        }
    }
        return numIslands
}

复杂度剖析

复杂度剖析

工夫复杂度：O(MN)，其中 M 和 N 别离为行数和列数。

空间复杂度：O(MN)，在最坏状况下，整个网格均为海洋，深度优先搜寻的深度达到 MN。

第二题 电话号码的字母组合

题目

解题思路

首先咱们先将题目所给出的信息存储入哈希表中

var phoneMap map[string]string = map[string]string{
    "2": "abc",
    "3": "def",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz",
}

https://leetcode-cn.com/probl…

代码

var phoneMap map[string]string = map[string]string{
    "2": "abc",
    "3": "def",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz",
}

var combinations []string

func letterCombinations(digits string) []string {
    // 如果为零间接返回
    if len(digits) == 0 {return []string{}}
    // 返回的字符串数组切片
    combinations = []string{}
    // 从第 0 个数开始遍历电话号码
    backtrack(digits, 0, "")
    return combinations
}

func backtrack(digits string, index int, combination string) {if index == len(digits) {
        // 实现其中一种可能性的查找，将其退出数组
        combinations = append(combinations, combination)
    } else {digit := string(digits[index])
        letters := phoneMap[digit]
        lettersCount := len(letters)
        for i := 0; i < lettersCount; i++ {
            // 别离将 3 个字母或者 4 个字母的后果退出到字符串切片中
            backtrack(digits, index + 1, combination + string(letters[i]))
        }
    }
}

复杂度剖析

工夫复杂度：O(3^m × 4^n)，其中 m 是输出中对应 3 个字母的数字个数（包含数字 2、3、4、5、6、8），n 是输出中对应 4 个字母的数字个数（包含数字 7、9），m+n 是输出数字的总个数。当输出蕴含 m 个对应 3 个字母的数字和 n 个对应 4 个字母的数字时，不同的字母组合一共有 3^m × 4^n 种，须要遍历每一种字母组合。

空间复杂度：O(m+n)，其中 m 是输出中对应 3 个字母的数字个数，n 是输出中对应 4 个字母的数字个数，m+n 是输出数字的总个数。除了返回值以外，空间复杂度次要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输出无关，能够看成常数，递归调用层数最大为 m+n