关于golang:golangleetcode中级子集单词搜索

30次阅读

共计 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。

正文完
 0