目录
  1. 1. 前言
  2. 2. 分治
  3. 3. 241-为运算表达式设计优先级
    1. 3.1. 题目
    2. 3.2. 题解
  4. 4. 95-不同的二叉搜索树II
    1. 4.1. 题目
    2. 4.2. 题解
leetcode-分治

前言

回顾一下分治思想和leetcode上分治思想的经典题。

  • 241-为运算表达式设计优先级
  • 95-不同的二叉搜索树II

分治

分治的思想总结,下面两篇文章写的蛮详细的:

  1. https://zhuanlan.zhihu.com/p/45986027
  2. https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741370.html

这里就简单列举,可使用分治法求解的一些经典问题:

  1. 二分搜索
  2. 大整数乘法
  3. Strassen矩阵乘法
  4. 棋盘覆盖
  5. 合并排序
  6. 快速排序
  7. 线性时间选择
  8. 最接近点对问题
  9. 循环赛日程表
  10. 汉诺塔
  • 注意:分治的子问题独立,动态的子问题重叠

241-为运算表达式设计优先级

题目

  • 难度:中等

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

  • 示例:

    输入: "2-1-1"
    输出: [0, 2]
    解释:
    ((2-1)-1) = 0
    (2-(1-1)) = 2

    输入: "2*3-4*5"
    输出: [-34, -14, -10, -10, 10]
    解释:
    (2*(3-(4*5))) = -34
    ((2*3)-(4*5)) = -14
    ((2*(3-4))*5) = -10
    (2*((3-4)*5)) = -10
    (((2*3)-4)*5) = 10

题解

  • 参考:https://leetcode-cn.com/problems/different-ways-to-add-parentheses/solution/pythongolang-fen-zhi-suan-fa-by-jalan/

  • 思路:

    • 对于一个形如 x op y(op为运算符,x和y为数)的算式而言,它的结果组合取决于x和y的结果组合数,而x和y又可以写成形如x op y的算式。
    • 因此,该问题的子问题就是 x op y 中的 xy以运算符分隔的左右两侧算式解
    • 然后我们来进行分治算法三步走
      1. 分治:按运算符分成左右两部分,分别求解
      2. 求解:实现一个递归函数,输入算式,返回算式解
      3. 合并:根据运算符合并左右两部分的解,得出最终解
class Solution(object):
def diffWaysToCompute(self, input):
"""
:type input: str
:rtype: List[int]
"""
if input.isdigit():
return [int(input)]
if not input:
return []

res = []
for i, char in enumerate(input):
if char in ['+', '-', '*']:
# 1.分解:遇到运算符,计算左右两侧的结果集
# 2.解决:diffWaysToCompute 递归函数求出子问题的解
left = self.diffWaysToCompute(input[:i])
right = self.diffWaysToCompute(input[i+1:])
# 3.合并:根据运算符合并子问题的解
for l in left:
for r in right:
if char == '+':
res.append(l + r)
elif char == '-':
res.append(l - r)
else:
res.append(l * r)

return res
  • 时间复杂度:O(Catalan(N)) = O((2n!)/n!(n-1)!)
  • 空间复杂度:O(n)

95-不同的二叉搜索树II

题目

  • 难度:中等

  • 题目:给定一个整数 n,生成所有由 1 … n 为节点所组成的 二叉搜索树

  • 示例:

    输入:3
    输出:
    [
      [1,null,3,2],
      [3,2,null,1],
      [3,1,null,null,2],
      [2,1,3],
      [1,null,2,null,3]
    ]
    解释:
    以上的输出对应以下 5 种不同结构的二叉搜索树:

    1 3 3 2 1
    \ / / / \ \
    3 2 1 1 3 2
    / / \ \
    2 1 2 3
  • 提示:0 <= n <= 8

题解

# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
#根节点为0,表示不存在,返回[]
if n == 0:
return []
#定义生成树函数,表示生成[left,...,right]的所有可能的二叉搜索树
def build_Trees(left, right):
#初始化所有可能的二叉搜索树列表
all_trees = []
#left>right,说明无法构成二叉搜索树,返回[None]
if(left > right):
return [None]
#遍历每一种可能的节点i,遍历区间[left,right + 1)
for i in range(left, right + 1):
#所有可能的左子树列表
left_trees = build_Trees(left, i - 1)
#所有可能的右子树列表
right_trees = build_Trees(i + 1, right)
#组合所有方式,遍历左子树列表,遍历右子树列表
for l in left_trees:
for r in right_trees:
#建立当前树节点
cur_tree = TreeNode(i)
#将左子树置为l
cur_tree.left = l
#将右子树置为r
cur_tree.right = r
#将构造好的树加入树列表
all_trees.append(cur_tree)
return all_trees
res = build_Trees(1, n)
return res
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n<1: return []
def gen(l,r):
return [TreeNode(root, left, right) for root in range(l,r+1) for left in gen(l,root-1) for right in gen(root+1, r)] or [None]
return gen(1,n)
  • 时间复杂度:O(Catalan(N)) ,卡特兰数以4nn32\frac{4^n}{n^{\frac{3}{2}}}增长,因此,总的时间复杂度为O(4nn12)O(\frac{4^n}{n^{\frac{1}{2}}})
  • 空间复杂度:O(4nn12)O(\frac{4^n}{n^{\frac{1}{2}}})
文章作者: Lesy
文章链接: https://lesylin.com/2020/07/03/leetcode-%E5%88%86%E6%B2%BB/
文章声明: 转载请注明文章链接
打赏
  • 微信
  • 支付宝

Comment