分治法解题
# 解释
顾名思义，分治问题由“分”（divide）和“治”（conquer）两部分组成，通过把原问题分为子 问题，再将子问题进行处理合并，从而实现对原问题的求解。我们在排序章节展示的归并排序就 是典型的分治问题，其中“分”即为把大数组平均分成两个小数组，通过递归实现，最终我们会得到多个长度为 1 的子数组;“治”即为把已经排好序的两个小数组合成为一个排好序的大数组， 从长度为 1 的子数组开始，最终合成一个大数组。
可以使用主定理来求解时间复杂度
# 表达式问题
# 为运算表达式设计优先级
一般这种分治法都是使用递归来进行求解。题如下
func diffWaysToCompute(expression string) []int {
var ways []int
// 遍历整个字符串
for i:=0;i< len(expression);i++ {
c:=string(expression[i])
// 首先我们判断当前的符号是否为运算符
if c=="+" || c=="-" || c=="*" {
// 如果是运算符的那么就分别计算左右两边的和
// 这里实际上就已经把左右两边所有的情况都计算进去了
left:=diffWaysToCompute(expression[:i])
right:=diffWaysToCompute(expression[i+1:])
// 下面我们就只需要依次组合计算
for _,l:=range left{
for _,r:=range right{
// 判断运算符的类型并把结果放入我们的结果数组
switch c {
case "+":
ways = append(ways, l+r)
case "-":
ways = append(ways, l-r)
case "*":
ways = append(ways, l*r)
}
}
}
}
}
// 如果结果为空，说明只有数字，我们直接转换一下即可
if len(ways)==0 {
if n,err:=strconv.Atoi(expression);err==nil{
ways=append(ways,n)
}
}
return ways
}
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
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
编辑 (opens new window)
上次更新: 2021/03/25, 23:10:37