第一题 岛屿数量
题目
解题思路
代码
//dfs函数通过深搜遍历一个岛屿，并将岛屿的1全都置0func 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][c] == '0' { return } grid[r][c] = '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][c] == '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 []stringfunc 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