问题1：求电话号码的字母组合 //
这是一个树类问题，可借组树天然的递归性质求解，结构如下图：
// 字符串查询表
var m []string = []string{
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz",
}
// 时间复杂度为3^n=O(2^n)
func letterCombinations(digits string) []string {
length := len(digits)
if length == 0 {
return nil
}
res := []string{}
combination(digits, length-1, 0, &res, "")
return res
}
// 深度优先遍历方式,从上而下添加字符方式
func combination(digits string, endI int, index int, res *[]string, str string) {
// 递归终止条件
if index == endI {
// 每次遍历到底部,在底部把str加到res里面
for _, v := range m[digits[index]-'2'] {
*res = append(*res, str+string(v))
}
} else {
// 递归过程
for _, v := range m[digits[index]-'2'] {
// 每次遍历到底部,在底部把str加到res里面
combination(digits, endI, index+1, res, str+string(v))
}
}
}
提交leetcode，通过
问题2：求全排列 //
一样是树问题，树的结构如下图示：
递归结构:perms(nums[0...n-1]) = {取出1个数字} + perms(nums[{0...n-1} - 这个数字])
func permute(nums []int) [][]int {
n := len(nums)
if n == 0 {
return nil
}
res := [][]int{} //组合集合
arr := make([]int, n) //组合
visited := make([]bool, n) //是否已经访问过
flashBack(nums, 0, n, visited, arr, &res)
return res
}
// 深度优先遍历方式,自上而下添加元素
// 向arr[0...index-1]末尾添加第index位元素,获得arr[0...index]元素的组合
func flashBack(nums []int, index, n int, visited []bool, arr []int, res *[][]int) {
// 递归终止条件
if index == n {
// 因为arr加在res里面后,arr修改,res里面也会被修改
// 所以这里做1次复制
buf := append([]int{}, arr...)
*res = append(*res, buf)
} else {
// 递归过程
for i := 0; i < n; i++ {
if !visited[i] {
visited[i] = true
// 推进元素,用完不同推出元素,下次循环重新覆盖
arr[index] = nums[i]
flashBack(nums, index+1, n, visited, arr, res)
// 用完重置为false,下次循环得用
visited[i] = false
}
}
}
}
提交leetcode，通过
问题3：求全排列2，和问题2对比 //
由上图可以看出，每次取出元素i后，只需从i之后的区间寻找下一个可填充的元素，即在[i+1,n]区间里寻找
方法1：未优化版本，理解未优化版本有助于理解优化版本
func combine(n int, k int) [][]int {
if n <= 0 || k > n || k <= 0 {
return nil
}
res := [][]int{} //组合集合
arr := make([]int, k) //长度k的组合
generateCombinations(n, k, 0, 1, arr, &res)
return res
}
// index: arr[index]位元素赋值
// start: 从[start...n]开始寻找下一个可以填充的元素
// 函数功能：从[start...n]里寻找下一位可以填充的元素,填充在arr[index]位置
func generateCombinations(n, k, index, start int, arr []int, res *[][]int) {
// 递归终止条件
if index == k {
// 做一次复制
buf := append([]int{}, arr...)
*res = append(*res, buf)
} else {
// 递归过程
for i := start; i <= n; i++ {
arr[index] = i
generateCombinations(n, k, index+1, i+1, arr, res)
}
}
}
方法1提交leetcode，通过
优化：arr[0...index-1]的元素已经填充，剩下k-index个空位，
因此[start...n]至少要有k-index个元素
即 k-index<=n-start+1，推导出 start<=n+1-(k-index)
// 优化1
func generateCombinations2(n, k, index, start int, arr []int, res *[][]int) {
// 递归终止条件
if index == k {
// 做一次复制
buf := append([]int{}, arr...)
*res = append(*res, buf)
} else {
// 优化：arr[0...index-1]的元素已经填充，剩下k-index个空位，
// 因此[start...n]至少要有k-index个元素
// 即 k-index<=n-start+1，推导出 start<=n+1-(k-index)
// 递归过程
for i := start; i <= n+1-(k-index); i++ {
arr[index] = i
generateCombinations2(n, k, index+1, i+1, arr, res)
}
}
}
在优化1的基础上进一步优化：每次arr加1个元素，令k-1，即剩下k-1个位置，
递归终止条件变成k==0
func generateCombinations3(n, k, index, start int, arr []int, res *[][]int) {
if k == 0 {
buf := append([]int{}, arr...)
*res = append(*res, buf)
} else {
// 每次arr加1个元素,k-1,即剩下k-1个空位置
for i := start; i <= n+1-k; i++ {
arr[index] = i
generateCombinations3(n, k-1, index+1, i+1, arr, res)
}
}
}
方法3提交leetcode，通过
有bug欢迎指出
网友评论