第一题 子集
题目
解题思路
长度为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。