chapter12-partition-algorithm

Posted on | In | | Visitors: ℃
Words count in article: 402 | Reading time ≈ 1

chapter12-partition-algorithm

[TOC]

分治算法
1. 给表达式加括号

Leetcode / 力扣

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
def diffWaysToCompute(input):
    # 又题意可知
    # 给表达式加括号
    # 就意味着只要有一个算术符号为一个独立板快，运算后继续组合
    # 因此每一个算法符号都可以把算术表达式分为两半
    # 如果我们把它看作一棵树的话
    # 那么算术符号就是根或者父节点，而数则是子节点
    # 一次遍历下去，就可以得到全部的算术组合了
    # 因此我们需要分治，也就是先把树给划分好
    # 然后在回溯的时候，进行求解子节点，也就是合并枝丫
    # 知道一个根节点为止，则为一个结果
    # 因此代码逻辑如下：

    ways = []
    for i in range(len(input)):
        c =input[i]
        if c in "-*+":
            left = diffWaysToCompute(input[:i])
            right = diffWaysToCompute(input[i+1:])
            for l in left:
                for r in right:
                    if c == '-':
                        ways.append(l - r)
                    elif c == '+':
                        ways.append(l + r)
                    else:
                        ways.append(l * r)
    if not ways:
        ways.append(int(input))
    return ways

input = "2*3-4*5"
# diffWaysToCompute(input)
2. 不同的二叉搜索树

Leetcode / 力扣

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
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def generateTrees(n):

    def generateSubTree(s, e):
        ways = []
        if s > e:
            ways.append(None)
            return ways
        for i in range(s, e+1):
            leftSubTrees = generateSubTree(s, i-1)
            rightSubTrees = generateSubTree(i + 1, e)
            for l in leftSubTrees:
                for r in rightSubTrees:
                    root = TreeNode(i)
                    root.left = l
                    root.right = r
                    ways.append(root)
        return ways

    def generateSubTrees2(nums, left, right):
        if left > right:
            return
        mid = left + (right - left)
        root = TreeNode(nums[mid])
        root.left = generateSubTrees2(nums, left, mid - 1)
        root.right = generateSubTrees2(nums, mid + 1, right)
        return root

    if n < 1:
        return []
    # return generateSubTree(1, n)
    return generateSubTrees2([i for i in range(1, n+1)], 0, n-1)
print(generateTrees(3))