共计 2121 个字符，预计需要花费 6 分钟才能阅读完成。
第一题 子集
题目
解题思路
长度为 n 的数组的幂集
首先咱们能够想到
长度为零的空数组和长度为一单元素解都肯定是数组的幂集
剩下的子集都能够在繁多解的根底上组合而成
例如
nums = [1,2,3]
则其多元素解
[1,2]由 [1] 和[2]组成
[1,3] 由[1]和 [3] 组成
[2,3] 由[2]和 [3] 组成
[1，2，3] 长度与 nums 等长，故只有一种可能
再看看长度为 4 的状况
nums = [1,2,3,4]
单元素解有 [1],[2],[3],[4]
双元素解有 [1,2],[1,3],[1,4],[2,3],[2,4],[3,4]
三要素解为
[1,2]+[3]=[1,2,3]
[1,2]+[4]=[1,2,4]
[1,3]+[2]=[1,3,2]
[1,3]+[4]=[1,3,4]
…….. 略
共能失去不同程序的组合四种
[1,2,3]，[1,2,4]，[1,3,4]，[2,3,4]
其中例如 [1,2,3] 与[1,3,2]实质上是反复的
这样咱们就须要退出一个对其分别筛选的函数
同时大量反复的计算也占了很大的代价
.
为了缩小反复
咱们引入一个数组用来存储元素的应用状况
鉴于元素的应用状况只有两种，应用 或者 不被应用 能够用 0 或者 1 来示意
这样存储元素应用状况的数组就变成了一串二进制数
且对应的二进制数正好从 0 到 2^n – 1，
这样
咱们只需遍历从 0 到 2^n – 1 的数，将其二进制示意时数值为 1 的位退出到数组，就失去了所有不反复的幂集
当然
咱们也能够思考标记元素的状态之后再进行递归
其中 用残余元素序列存储元素的应用状况
https://leetcode-cn.com/probl…
代码
func subsets(nums []int) (ans [][]int) {n := len(nums)
for mask := 0; mask < 1<<n; mask++ {// 从 0 到 n^2-1
set := []int{}
for i, v := range nums {
// 遍历 nums 数组，如果第 i 位为 1，则将其退出 set
if mask>>i&1 > 0 {set = append(set, v)
}
}
ans = append(ans,set)
}
return
}复杂度剖析
工夫复杂度：O(n×2^n)。一共 2^n 个状态，每种状态须要 O(n) 的工夫来结构子集。
空间复杂度：O(n)。即结构子集应用的长期数组 set 的空间代价。
第二题 单词搜寻
题目
思路
dfs+ 回溯
另外
同一个单元格内的字母不容许被重复使用。
因而，咱们须要在应用一个字母之后 将其置为非字母的元素
同时将其存储在一个长期变量
如果递归失败，再将其还原，持续下一次递归查找
代码
func exist(board [][]byte, word string) bool {var words []byte
for _,v:=range word{words=append(words,byte(v))
}
for i := 0; i < len(board); i++ {for j := 0; j < len(board[0]); j++ {// 从 [i,j] 这个坐标开始查找
if dfs(board, words, i, j, 0) {return true}
}
}
return false
}
func dfs(board [][]byte, word []byte,i int,j int,index int)bool {
// 边界的判断，如果越界间接返回 false。index 示意的是查找到字符串 word 的第几个字符，if i >= len(board) || i < 0 || j >= len(board[0]) || j < 0 {return false}
// 如果这个字符不等于 board[i][j]，阐明验证这个坐标门路是走不通的，间接返回 false
if board[i][j] != word[index] {return false}
// 如果 word 的每个字符都查找完了，间接返回 true
if index == len(word) - 1 {return true}
// 把以后坐标的值保留下来，为了在最初还原
tmp := board[i][j]
// 而后批改以后坐标的值
board[i][j] = '.'
// 走递归，沿着以后坐标的上下左右 4 个方向查找
res := dfs(board, word, i + 1, j, index + 1) || dfs(board, word, i - 1, j, index + 1) || dfs(board, word, i, j + 1, index + 1) || dfs(board, word, i, j - 1, index + 1)
// 递归之后再把以后的坐标还原
board[i][j] = tmp
return res
}后果
复杂度剖析
复杂度剖析
工夫复杂度：O(MN⋅4^L)，其中 M,N 为网格的长度与宽度，别离对网格的每个点应用一次 dfs 函
数，但绝大部分状况下调用函数只进行了一次判断 boardi != word[index] 便返回了结
果，很少有极其状况全都是相等的，因而这是一个十分宽松的上界。L 为字符串 word 的长度。dfs 每次递归调用四次 dfs，刚好搜寻到单词的工夫复杂度为 O（4^L），而咱们要执行 O(MN) 次查看。然而，真正达到 L 深度的只有胜利搜寻到单词返回 true 的一次调用。因而，理论的工夫复杂度会远远小于 Θ(MN⋅4^L)。
空间复杂度：O(L)。栈的深度最大为 O(L)，每次只申明了长期变量 tmp。