-
39组合总数
- 代码随想录 (programmercarl.com)
-
第一印象
- 本题的元素能够重复，那么回来条件便是是大于等于目标值。依旧是运用path和result存储值。
-
讲解观后感
- sum值能够不作为参数传入递归函数中，直接用target -。但是保有sum值能够便利剪枝。
- 剪枝操作能够先经过排序使数组单调递加。再运用当时sum与当时值的和来提早停止for循环.
-
解题代码
-
func combinationSum(candidates []int, target int) [][]int { ans := make([][]int, 0) if len(candidates)==0 { return ans } path := []int{} sum := 0 var dfs func(candidates []int, idx int, sum int, target int) dfs = func(candidates []int, idx int, sum int, target int) { if sum > target { return } if sum == target { temp := make([]int, len(path)) copy(temp, path) ans = append(ans, temp) return } for i:=idx;i<len(candidates);i++ { sum += candidates[i] path = append(path, candidates[i]) dfs(candidates, i, sum, target) path = path[:len(path)-1] sum -= candidates[i] } } dfs(candidates, 0, sum, target) return ans } - 剪枝：
-
func combinationSum(candidates []int, target int) [][]int { ans := make([][]int, 0) if len(candidates)==0 { return ans } path := []int{} sum := 0 sort.Ints(candidates) //排序操作 var dfs func(candidates []int, idx int, sum int, target int) dfs = func(candidates []int, idx int, sum int, target int) { if sum == target { temp := make([]int, len(path)) copy(temp, path) ans = append(ans, temp) return } for i:=idx;i<len(candidates)&&sum+candidates[i]<=target;i++ { //剪枝操作 sum += candidates[i] path = append(path, candidates[i]) dfs(candidates, i, sum, target) path = path[:len(path)-1] sum -= candidates[i] } } dfs(candidates, 0, sum, target) return ans } -
40组合总数II
- 代码随想录 (programmercarl.com)
-
第一印象
- 本题每个数字只能运用一次，那么递归传参就得+1
-
讲解观后感
- 这题的去重操作非常巧妙。关于树形结构中树层与树枝的评论非常形象。
-
解题代码
- 运用used数组
-
func combinationSum2(candidates []int, target int) [][]int { ans := make([][]int, 0) if len(candidates)==0 { return ans } path := []int{} sum := 0 sort.Ints(candidates) //排序操作 used := make([]bool, len(candidates)) var dfs func(candidates []int, target int,idx int, sum int) dfs = func(candidates []int, target int,idx int, sum int) { // if sum > target { // return // } if sum == target { temp := make([]int, len(path)) copy(temp, path) ans = append(ans, temp) return } for i:=idx;i<len(candidates)&&sum+candidates[i]<=target;i++ { // used[i - 1] == true，阐明同一树枝candidates[i - 1]运用过 // used[i - 1] == false，阐明同一树层candidates[i - 1]运用过 if i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false { continue } sum += candidates[i] path = append(path, candidates[i]) used[i] = true dfs(candidates, target, i+1, sum) used[i] = false path = path[:len(path)-1] sum -= candidates[i] } } dfs(candidates, target, 0, sum) return ans } - 不运用used数组
-
func combinationSum2(candidates []int, target int) [][]int { ans := make([][]int, 0) if len(candidates)==0 { return ans } path := []int{} sum := 0 sort.Ints(candidates) //排序操作 var dfs func(candidates []int, target int,idx int, sum int) dfs = func(candidates []int, target int,idx int, sum int) { if sum == target { temp := make([]int, len(path)) copy(temp, path) ans = append(ans, temp) return } for i:=idx;i<len(candidates)&&sum+candidates[i]<=target;i++ { // i != start 约束了这不对深度遍历抵达的此值去重 if i != idx && candidates[i] == candidates[i-1] { // 去重 continue } sum += candidates[i] path = append(path, candidates[i]) dfs(candidates, target, i+1, sum) path = path[:len(path)-1] sum -= candidates[i] } } dfs(candidates, target, 0, sum) return ans } - 不运用sum传参
-
var ( res [][]int path []int ) func combinationSum2(candidates []int, target int) [][]int { res, path = make([][]int, 0), make([]int, 0, len(candidates)) sort.Ints(candidates) // 排序，为剪枝做准备 dfs(candidates, 0, target) return res } func dfs(candidates []int, start int, target int) { if target == 0 { // target 不断减小，假如为0阐明达到了目标值 tmp := make([]int, len(path)) copy(tmp, path) res = append(res, tmp) return } for i := start; i < len(candidates); i++ { if candidates[i] > target { // 剪枝，提早回来 break } // i != start 约束了这不对深度遍历抵达的此值去重 if i != start && candidates[i] == candidates[i-1] { // 去重 continue } path = append(path, candidates[i]) dfs(candidates, i+1, target - candidates[i]) path = path[:len(path) - 1] } -
131切开回文串
- 代码随想录 (programmercarl.com)
-
讲解观后感
- 本题也是经典的运用回溯算法的标题。而关于回溯的用法中，首要遇到的难点便是切开终究应该怎么表示。只要把index和i构成的区间是切开后的区间了解明白，就能解决了。
- 卡尔也帮我们列出了这道题的几个难点，协助我们了解。
-
切开问题能够抽象为组合问题 怎么模拟那些切开线 切开问题中递归怎么停止 在递归循环中怎么截取子串 怎么判断回文 -
解题代码
-
var ( path []string // 放已经回文的子串 res [][]string ) func partition(s string) [][]string { path, res = make([]string, 0), make([][]string, 0) dfs(s, 0) return res } func dfs(s string, start int) { if start == len(s) { // 假如开始位置等于s的巨细，阐明已经找到了一组切开计划了 tmp := make([]string, len(path)) copy(tmp, path) res = append(res, tmp) return } for i := start; i < len(s); i++ { str := s[start : i+1] if isPalindrome(str) { // 是回文子串 path = append(path, str) dfs(s, i+1) // 寻找i+1为开始位置的子串 path = path[:len(path)-1] // 回溯过程，弹出本次已经填在的子串 } } } func isPalindrome(s string) bool { for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 { if s[i] != s[j] { return false } } return true }
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
