likes
comments
collection
share

代码随想录day23|39组合总数40组合总数II131分割回文串|01笔记

作者站长头像
站长
· 阅读数 4

  • 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

  • 讲解观后感

  • 这题的去重操作十分巧妙。关于树形结构中树层与树枝的讨论十分形象。 代码随想录day23|39组合总数40组合总数II131分割回文串|01笔记

  • 解题代码

  • 使用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
    }