leetcode 回溯题目 golang语言

努力的C · · 449 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就 “回溯” 返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为 “回溯点”。许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。
回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。

 链接:https://leetcode-cn.com/tag/backtracking/
 来源:力扣(LeetCode)
 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

本文主要总结一下回溯算法的一些题目。语言主要是Golang。

78.子集,不含重复元素

第一种是比较常规的回溯解法。

func subsets(nums []int) [][]int {
    result := make([][]int, 0)
    subsetsBT(&result, nums, []int{}, 0)
    return result
}
func subsetsBT(result *[][]int, nums []int, temp []int, start int) {
    //此处深拷贝temp,避免回溯的时候temp被修改后会影响之前保存的结果
    c := make([]int, len(temp))
    copy(c, temp)
    *result = append(*result, c)

    for i := start; i < len(nums); i++ {
        temp = append(temp, nums[i])
        subsetsBT(result, nums, temp, i+1)//不包含重复值
        temp = temp[:len(temp)-1]
    }
}

第二章方法就比较牛逼了,具体解释参考此处。用二进制位的0,1表示是否选中当前位置的数。

func subsets(nums []int) [][]int {
    result := make([][]int, 0)
    n := 1 << uint(len(nums))
    for i := 0; i < n; i++ {
        temp := make([]int, 0)
        for j := 0; j < len(nums); j++ {
            if uint(i)>>uint(j)&1 == 1 {
                temp = append(temp, nums[j])
            }
        }
        result = append(result, temp)
    }

    return result
}

77.组合

常规解法。当temp里的元素个数等于给定的K时,找到一个满足条件的解。

func combine(n int, k int) [][]int {
    var result = make([][]int, 0)
    combineBT(n, k, 1, []int{}, &result)
    return result
}
func combineBT(n, k, start int, temp []int, result *[][]int) {
    if len(temp) == k {
        c := make([]int, len(temp))
        copy(c, temp)
        *result = append(*result, c)
        return
    }

    for i := start; i <= n; i++ {
        temp = append(temp, i)
        combineBT(n, k, i+1, temp, result)
        temp = temp[0 : len(temp)-1]
    }
}

39. 组合总和,不包含重复元素,可多次使用

常规解法,要先排序一下。每次先尝试减去当前元素,要是减去后还大于0,则表示可以继续往下走。然后因为可以重复使用元素,所以回溯的时候从i开始继续下一次。直到目标值减到0后,找到一个满足条件的解空间。


func combinationSum(candidates []int, target int) [][]int {
    var result = make([][]int, 0)
    sort.Ints(candidates)
    combinationSumBT(&result, candidates, []int{}, target, 0)
    return result
}
func combinationSumBT(result *[][]int, candidates []int, temp []int, target int, start int) {
    if target == 0 {
        c := make([]int, len(temp))
        copy(c, temp)
        *result = append(*result, c)
        return
    }
    for i := start; i < len(candidates); i++ {
        if target-candidates[i] >= 0 {
            target -= candidates[i]
            temp = append(temp, candidates[i])
            combinationSumBT(result, candidates, temp, target, i)//可以包含已经用过的值,所以从i开始,
            temp = temp[0 : len(temp)-1]//回溯
            target += candidates[i]//得把当前用过的值再加回去。
        } else {
            return
        }
    }
}

40. 组合总和2,只能使用一次且解空间不能包含重复

和第一个很像,但是每个数字只能用一次且解空间不能包含重复解。

func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    var result = make([][]int, 0)
    combinationSumBT2(&result, candidates, []int{}, target, 0)
    return result
}
func combinationSumBT2(result *[][]int, candidates []int, temp []int, target int, start int) {
    if target == 0 {
        c := make([]int, len(temp))
        copy(c, temp)
        *result = append(*result, c)
        return
    }
    for i := start; i < len(candidates); i++ {
        if target-candidates[i] >= 0 {
        //比如[10,1,2,7,6,1,5], target = 8
        //排好序后[1,1,2,5,6,7,10]
        //在第一个for循环里,先遍历到第一个1,经过一系列操作,得到解集[1,7]
        //然后还是第一个for循环里,又遍历到后面的1,现在是不需要[第二个1,7]这个解集了,所以跳过。
            if i != start && candidates[i] == candidates[i-1] { //因为解空间不能有重复
                continue
            }
            target -= candidates[i]
            temp = append(temp, candidates[i])
            combinationSumBT2(result, candidates, temp, target, i+1)//因为不能重复使用,所以从i+1开始
            temp = temp[0 : len(temp)-1]
            target += candidates[i]
        } else {
            return
        }
    }
}

216. 组合总和3,只有1-9,且每个组合中不能有重复且最后的解空间不能包含重复

func combinationSum3(k int, n int) [][]int {
    var result = make([][]int, 0)
    combinationSumBT3(&result, []int{}, k, n, 1)
    return result
}
func combinationSumBT3(result *[][]int, temp []int, k int, target int, start int) {
    //和第一个很像,在target的基础上增加了一个k的限制。
    if target == 0 && k == 0 {
        c := make([]int, len(temp))
        copy(c, temp)
        *result = append(*result, c)
        return
    }
    for i := start; i <= 9; i++ {
        if target-i >= 0 {
            target -= i
            k--
            temp = append(temp, i)
            combinationSumBT3(result, temp, k, target, i+1)//每个组合不能有重复
            temp = temp[0 : len(temp)-1]
            target += i
            k++
        } else {
            return
        }
    }
}

17.电话号码的字母组合

方法一是常规的回溯。

var wordsMap = map[int]string{2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"}
func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }
    answer := make([]string, 0)
    letterCombinationsBT(&answer, digits, "", 0)
    return answer
}
func letterCombinationsBT(answer *[]string, digits string, temp string, index int) {
    if len(temp) == len(digits) {
        *answer = append(*answer, temp)
        return
    }

    char := digits[index] - '0'
    letter := wordsMap[int(char)]
    //fmt.Println(int(char), letter)
    for i := 0; i < len(letter); i++ {
        letterCombinationsBT(answer, digits, temp+string(letter[i]), index+1)
    }

    return
}

方法二就比较牛逼了,把按的数字对应的字母依次放到队列中,然后和下一个数字的字母挨个拼,拼完再扔到队尾。
比如我按了 "23" 对应 abc 和 def
我先在队列[从左到右表示队首到队尾]初始化一个空字符串。
" "
然后遍历第一个数字 2 ,对应的字母是 abc,然后用队列头部的空字符串 "" 依次和abc做拼接,得到 "a", "b", "c",
然后依次从队尾扔到队列,现在队列是
a b c
遍历完2对应的字母再继续遍历3的。3对应def。取出队首的"a",依次和后面的def拼接,得到 "ad", "ae", "af",然后扔到队尾,现在队列里是
b c ad ae af
继续重复这个操作即可完成最后的遍历,很方便。

c ad ae af bd be bf

ad ae af bd be bf cd ce cf


func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }
    var words = [8]string{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
    queue := make([]string, 0)
    queue = append(queue, "")
    for i := 0; i < len(digits); i++ {
        n := digits[i] - '2'
        size := len(queue)
        for j := 0; j < size; j++ {
            st := queue[0]
            queue = queue[1:]
            for _, ch := range words[n] {
                temp := st + string(ch)
                queue = append(queue, temp)
            }
        }
    }
    return queue
}

有疑问加站长微信联系(非本文作者)

本文来自:51CTO博客

感谢作者:努力的C

查看原文:leetcode 回溯题目 golang语言

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

449 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传