算法(6): 贪心算法

分治的思想为将大问题分解为子问题，子问题再分解为更小的子问题，直到不能再拆分，然后再合并子问题的结果，通常需要用到递归。关键是要找对如何拆解问题。

5.1 不同的二叉搜索树

问题描述：给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

思路：根据二叉搜索树的特点，左子树的所有节点值均小于根节点，右子树的所有节点值均大于根节点，同时对于每一个子树也要满足以上条件。1…n有序序列，假设对于每一个值i作为根节点，可以先求的[1，i - 1]构成的二叉搜索左子树，[i + 1, n]构成的二叉搜索右子树，然后从左右子树中各选一个作为当前根节点的左右子树。

示例代码：

func generateTrees(n int) []*TreeNode {
    return _generateTrees(1, n)
}

func _generateTrees(start, end int) []*TreeNode {
    if start > end {
        return []*TreeNode{nil}
    }
    res := []*TreeNode{}
    for i := start; i <= end; i++ {
        left := _generateTrees(start, i - 1)
        right := _generateTrees(i + 1, end)
        for _, l := range left {
            for _, r := range right {
                tmp := &TreeNode{
                    Val: i,
                    Left: l,
                    Right: r,
                }
                res = append(res, tmp)
            }
        }
    }
    return res
}

5.2 为运算表达式设计优先级

LeetCode No.241

题目描述：给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

思路：对于每个预算式形如x op y，其左右表达式也可以看做一个形如x op y的运算式，对左右两边的运算式的所有结果进行计算，就可以得到最终的结果。

示例代码：

func diffWaysToCompute(expression string) []int {
    num, err := strconv.Atoi(expression)
    // 如果为纯数字，直接返回数字
    if err == nil {
        return []int{num}
    }
    res := []int{}
    for i, ch := range expression {
        // 跳过非运算符
        if ch != '+' && ch != '-' && ch != '*' {
            continue
        }
        // 计算运算符左右两边子表达式的结果
        left := diffWaysToCompute(expression[ : i])
        right := diffWaysToCompute(expression[i + 1 : ])
        for _, l := range left {
            for _, r := range right {
                var tmp int
                switch ch {
                case '+': tmp = l + r
                case '-': tmp = l - r
                case '*': tmp = l * r
                }
                res = append(res, tmp)
            }
        }
    }
    return res
}