背景图

递归算法原理剖析(一次算法面试)

最近看到了一家比较出名的区块链项目,觉得挺好玩的,所以就投了一份简历去面试,后来因为其他原因;我放弃了对方给的很高薪资的offer。但是我觉得他们还是比较靠谱的团队。由于这里是面试题,我就不透露这家公司的名字了。也许以后我会考虑加入也未可知。

题目

他们首先考了一道算法题,需要你写代码,这道题目不是很难,大概意思如下:

随意给定一组数字(个数不限),例如:2 4 5 7,然后使用(+ - * /)在数字中随意组合,然后给出最终所有可能的结果。注意:括号在这里也是操作符号哈。

解决方法

思路一:这里我原来的思路是排列组合操作符,这个思路有点像编译原理中的表达式拆解,分为操作符栈和数据栈,两个结合起来运算就会得出结果,但是这种方式的缺点是实现起来比较复杂。主要就是要对操作符进行递归,如果没有括号还简单一些,有了括号之后递归就变得有些复杂,但是这里的递归条件还是蛮好处理的,看个数即可;其二就是要写表达式运算的代码;虽说不复杂,但是这是面试哪有时间去写这些东西。

方法二:将数字拆分,拆分的数字就是加括号的地方,比如将[2 4 5 7]拆分成[[2 4 5] [7]]。这里括号是加在了前3个元素上面。以此循环往替。然后[7]与[2 4 5]之间可以随意使用+ - * /,下面的问题就是求解[2 4 5]的结果即可。

代码实现

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.*;

public class Demo {
/**
* 主体用于处理的方法
* @param numbers 输入的一组数字
* @return
*/
public Set<Double> list(List<Double> numbers) {
Set<Double> result = new LinkedHashSet<>();

// 递归条件
if (numbers.size() == 1) {
result.addAll(numbers);
return result;
}

for (int i = 0; i < numbers.size() - 1; i++) {
List<Double> right = numbers.subList(i + 1, numbers.size());
List<Double> left = numbers.subList(0, i + 1);

result.addAll(combine(left, right));
}

return result;
}

/**
* 数据的两组数据的组装
* @param left 左侧数组
* @param right 右侧数组
* @return
*/
public Set<Double> combine(List<Double> left, List<Double> right) {
Set<Double> result = new HashSet<>(left.size() * right.size());

Set<Double> leftValue = list(left);
Set<Double> rightValue = list(right);
leftValue.forEach(l -> rightValue.forEach(r -> {
result.add(l + r);
result.add(l - r);
result.add(l * r);
result.add(l / r);
}));

return result;
}

public static void main(String[] args) {
List<Double> arrays = new ArrayList<>();
arrays.add(4d);
arrays.add(6d);
arrays.add(5d);

new Demo().list(arrays).forEach(i -> System.out.print(i + " "));
}
}

运行的结果如下:

1
2.8 4.8 3.3333333333333335 34.0 44.0 3.0 15.0 4.0 0.13333333333333333 5.0 5.2 -26.0 -7.0 0.36363636363636365 120.0 3.333333333333333 2.0 -0.4 -10.0 -4.333333333333333 50.0 19.0 29.0 5.666666666666667

更多思考

注意这里我们关注的是运算符的排序,为何我们只去关注括号,而不关注没有加括号的情况呢?

这是因为我们把所有的操作符都当成了平级的操作符,对没有错,+-*/在这里我们认为是相同级别的。然后我们使用了括号来保证*的优先级高于+操作符。

比如:a + b * c这样的,在我们的算法中认为这个格式是这样的(a) + ((b) * (c)).

你没有看错算法的核心思想就是这样的,我们是括号的嵌套,哪怕是只有一个元素,这也是递归思想的核心。我相信通过这个示例,大家对于递归的理解应该能够更上一个台阶。

0%