-
回溯算法——好的开始
0、前言和模板
前言：
第一次刷回溯算法，大概刷了8，9道
说真，起初以为上来就怼回溯会不会起点太高，后来，发现按照类型刷算法题真的会比一会一个二叉树一个贪心，一个动态好，毕竟会有一种拿捏感成就感
实践费曼学习法——咱先去理论学习了两个小时，基本在理论上拿捏了回溯，目前感觉回溯不就是个递归吗，只是给他增加了别的东西而已，最本质的就是递归
关于理论学习部分，看这个就够了回溯法，动态规划，贪心的区别
然后是一个好的刷题顺序，这部分我是从这个回溯刷题开始开始，有八道题，目前已经刷完,算是一个循序渐进的排序，包含了经典的子集问题，全排列问题等
当然了你可以直接看我的就行
下一个阶段打算跟着代码随想录的的刷题顺序刷题，但是不打算看他的长篇大论了
一点总结：
回溯算法，自上而下，遍历枚举每一种过程，从而判断是否满足
动态规划，自下而上，从已知的结果往上追溯，从而判断
贪心算法，这个根据经验做，比较难，是从局部最优得到整体最优结
回溯算法模板：
result = [] func backtrack(选择列表，路径) if 满足条件 result.add(路径) return for 选择 in 选择列表 做选择 backtrack(选择列表，路径) 撤销选择- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
1、子集问题
给你一个整数数组
nums，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
func subsets(nums []int) [][]int { result := make([][]int, 0) list := make([]int, 0) backtrack(nums, 0, list, &result) return result } func backtrack(nums []int, pos int, list []int, result *[][]int){ ans := make([]int,len(list)) copy(ans,list) *result = append(*result,ans) for i := pos; i < len(nums); i++ { list = append(list,nums[i]) // 所谓选择就是树下走一步 backtrack(nums, i+1, list, result) // 所谓处理就是对，backtrack函数里的值更新 list = list[0 : len(list)-1] // 所谓撤销，就是使得中间list回到原来状态 } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
func subsetsWithDup(nums []int) [][]int { result := make([][]int, 0) list := make([]int, 0) sort.Ints(nums) // 多了个排序，为了后续去重需要 backtrack(nums,0,list,&result) return result } func backtrack(nums []int, pos int, list []int, result *[][]int){ ans := make([]int, len(list)) copy(ans,list) *result = append(*result, ans) for i := pos; i < len(nums); i++ { if i != pos && nums[i] == nums[i-1] { // 做到了去重，例如当pos为0时候，就不要1 2 2这个了，因为后边会再次出现一次。 continue } list = append(list,nums[i]) backtrack(nums,i+1,list,result) list = list[0 : len(list)-1] } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
2、全排列问题
给定一个不含重复数字的数组
nums，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。一定要带入实例，刚开始会绕的晕晕的，但是多晕几次，就会一次比一次清楚。
func permute(nums []int) [][]int { result := make([][]int, 0) list := make([]int, 0) visited := make([]bool, len(nums)) backtrack(nums,visited,list,&result) return result } func backtrack(nums []int, visited []bool, list []int, result *[][]int){ if len(list) == len(nums) { ans := make([]int, len(list)) copy(ans,list) *result = append(*result, ans) return } for i := 0; i < len(nums); i++ { if visited[i] { continue } list = append(list, nums[i]) visited[i] = true backtrack(nums, visited, list, result) visited[i] = false list = list[0 : len(list)-1] } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
给定一个可包含重复数字的序列
nums，按任意顺序 返回所有不重复的全排列。func permuteUnique(nums []int) [][]int { result := make([][]int, 0) list := make([]int, 0) visited := make([]bool, len(nums)) sort.Ints(nums) backtrack(nums, visited, list, &result) return result } func backtrack(nums []int, visited []bool, list []int, result *[][]int){ if len(list) == len(nums) { ans := make([]int, len(list)) copy(ans,list) *result = append(*result,ans) return } for i := 0; i < len(nums); i++ { if visited[i] { // 不要忘了，注意位置 continue } if i != 0 && nums[i] == nums[i-1] && !visited[i-1] { // 注意条件 continue } list = append(list,nums[i]) visited[i] = true backtrack(nums, visited, list, result) visited[i] = false list = list[0 : len(list)-1] } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
3、提升
func combinationSum(candidates []int, target int) [][]int { result := make([][]int, 0) list := make([]int, 0) backtrack(0, 0, target, candidates, list, &result) return result } func backtrack(startIndex,sum,target int, candidates,list []int, result *[][]int){ //目标_自下向上 if sum == target { ans := make([]int, len(list)) copy(ans, list) *result = append(*result,ans) return } if sum > target {return} // 开始正主 for i := startIndex; i < len(candidates); i++ { list = append(list, candidates[i]) sum += candidates[i] backtrack(i, sum, target, candidates,list,result) list = list[0 : len(list)-1] sum -= candidates[i] } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
func letterCombinations(digits string) []string { // 先把数字变成字母数组。 length := len(digits) if length == 0{ return nil } digitsMap := [10]string { "", //0 "", //1 "abc", //2 "def", //3 "ghi", //4 "jkl", //5 "mno", //6 "pqrs", //7 "tuv", //8 "wxyz", //9 } result := make([]string, 0) list := "" //中间暂存值 backtrack(0, list, digits, digitsMap, &result) return result } func backtrack(Index int, list,digits string, digitsMap [10]string, result *[]string){ // Index代表digits的当前下标 if len(list) == len(digits) { // ans string // copy(ans, list) *result = append(*result, list) return } listK := digits[Index] - '0' dm := digitsMap[listK] for i := 0; i < len(dm); i++ { list = list + string(dm[i]) backtrack(Index+1,list,digits,digitsMap,result) //index代表下一个选择 list = list[ : len(list)-1] } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
给你一个字符串
s，请你将s分割成一些子串，使每个子串都是 回文串 。返回s所有可能的分割方案。回文串 是正着读和反着读都一样的字符串。
func partition(s string) [][]string { //判断空 // if len(s) == 0 { // return nil // } // 判断条件变成了-是否回文 result := make([][]string, 0) list := make([]string, 0) backtrack(0, s, list, &result) return result } //需要一个字符串变量 func backtrack(Index int, s string, list []string, result *[][]string){ //结束条件看最后一个字符是否用了_出现最后一个字符 if Index == len(s) { ans := make([]string, len(list)) copy(ans, list) *result = append(*result, ans) //return } //选择列表是下一个字符,回文的方法是关键 for i := Index; i < len(s); i++ { if huiwen(s,Index,i) { //是回文的话，就确定切割区间切割 list = append(list,s[Index:i+1]) backtrack(i+1,s,list,result) //记着，是i+1不是index+1 list = list[:len(list)-1] } } } // 判断一个字符串是否为字符串,和我写的不一样 func huiwen(s string,Index,end int) bool { left := Index right := end for ; left < right; { if s[left] != s[right]{ return false } //移动左右指针 left++ right-- } return true }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
代码随想录的
func restoreIpAddresses(s string) []string { var res,path []string backTracking(s,path,0,&res) return res } func backTracking(s string,path []string,startIndex int,res *[]string){ //终止条件 if startIndex==len(s)&&len(path)==4{ tmpIpString:=path[0]+"."+path[1]+"."+path[2]+"."+path[3] *res=append(*res,tmpIpString) } for i:=startIndex;i<len(s);i++{ //处理 path:=append(path,s[startIndex:i+1]) if i-startIndex+1<=3&&len(path)<=4&&isNormalIp(s,startIndex,i){ //递归 backTracking(s,path,i+1,res) }else {//如果首尾超过了3个，或路径多余4个，或前导为0，或大于255，直接回退 return } //回溯 path=path[:len(path)-1] } } func isNormalIp(s string,startIndex,end int)bool{ checkInt,_:=strconv.Atoi(s[startIndex:end+1]) if end-startIndex+1>1&&s[startIndex]=='0'{//对于前导 0的IP（特别注意s[startIndex]=='0'的判断，不应该写成s[startIndex]==0，因为s截取出来不是数字） return false } if checkInt>255{ return false } return true }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
第一次自己写，写成如下，感觉很接近了
func restoreIpAddresses(s string) []string { result := make([]string, 0) backtrack(0, 0, "", s, &result) return result } func backtrack(Index,ds int,list,s string, result *[]string) { if len(list) == len(s)+3 && ds == 3{ //结束条件，就是用了s的最后一个字符 *result = append(*result, list) } //点数只能有三个 for i := Index; i < len(s) && ds <= 3; i++ { //整数，没有前导0，没有其他符号,不能大于255， // 这个切割区间，前导不为零，继续下层bacetrack（特例子，只有一位数手，不算是前导） // 思考如何找到这个区间用于判断 str := s[Index:i+1] s1, _ := strconv.Atoi(str) if s1 > 255 || s1 < 0{ // 有效区间是0~255，不满足的话直接跳过这个情况 break } //前置不为零时候，长度是大于1的,当只有一个数是0的情况也满足 if (str[0] != 0 && len(str) > 1) || len(str) == 1 { list = list + str if len(list) < len(s)+3 && ds < 3{ list += "." ds++ } backtrack(i+1, ds, list, s, result) list = list[:len(list)-1] // 应该不只是len-1了 } } } //果然，回溯法最难的还是，判断条件的难找啊- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
看过代码随想录的再去改正，发现及其相似了，唯独最关键的path就是我的list没有用[]string类型，导致越想越头疼。真可谓点睛之笔，但是为啥我就没想出来呢。
func restoreIpAddresses(s string) []string { list := make([]string, 0) // 作为路径，就是中间暂存值 result := make([]string, 0) backtrack(0,list,s,&result) return result } func backtrack(Index int,list []string,s string, result *[]string) { if Index == len(s) && len(list) == 4{ //结束条件，就是用了s的最后一个字符 list长度只能为4 ans := list[0] + "." + list[1] + "." + list[2] + "." + list[3] *result = append(*result, ans) } for i := Index; i < len(s); i++ { //前置不为零时候，长度是大于1的,当只有一个数是0的情况也满足 list := append(list, s[Index:i+1]) //数字截取的有效长度为3, list路径<=4个,正常IP, if i-Index+1 <= 3 && len(list) <= 4 && isIP(s,Index,i) { backtrack(i+1, list, s, result) }else { //否则，这种不存在直接return这种结果，不必再执行for循环 return } list = list[:len(list)-1] } } //判断ip条件,函数抽离 func isIP (s string, startIndex,end int) bool { str := s[startIndex:end+1] s1, _ := strconv.Atoi(str) //转化为数字了 //当这个数，长度大于一位，前导不能为零，不能大于255 if end - startIndex+1 > 1 && str[0] == '0' { return false } if s1 > 255 { return false } return true }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
-
相关阅读:
Python基础语法2与常见问题
使用canal实现数据实时同步
Rockland丨Rockland重组 VhH 抗体解决方案
Java扩展Nginx之六：两大filter
1758. 生成交替二进制字符串的最少操作数
1.ODBC连接Postgresql
PMI-ACP练习题(19)
有必要给猫吃罐头吗？“合适的”比“贵的”更重要！
Vue2与Vue3：深度剖析核心差异与升级亮点
排序-快排算法对数组进行排序
- 原文地址：https://blog.csdn.net/EGXXM/article/details/126906630
