写在前面

前几天华为一面，算法题华为一面算法题：打印螺旋三角形没有写出来，这次二面的算法题写出来了，过程很顺利，花了20分钟左右，调试过一次。

一面是面试后把题目文字发到聊天框内，这次是之间扔过来一个leetcode链接 241. 为运算表达式设计优先级 , 中等难度的题目

题目描述

思路

首先，盯着示例2看了一两分钟, 看看有没有什么规律，并且理解题意。

输入：expression = "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

从示例2的解释中可以很明显的看出，这个题目可以用递归。

第一个乘号*，两边表达式是”2”和”3-4*5”,可能的结果是[2]和[-5,-17],然后用[2]和[-5,-17]中的每个结果两两相乘，所以最终结果是[-10,-34]
第二个减号-，两边表达式是”23”和”45”,可能的结果是[6]和[20],然后用[6]和[20]中的每个结果两两相减，所以最终结果是[-14]
第三个乘号*，两边表达式是”2*3-4”和”5”,可能的结果是[2，-2]和[5],然后用[2，-2]和[5]中的每个结果两两相减，所以最终结果是[10，-10]

最终结果是[-10,-34,-14,10,-10]

代码

type Calc func(x, y int) int

var express = map[byte]Calc{
	'+': add,
	'-': sub,
	'*': mult,
}

func add(x, y int) int {
	return x + y
}

func mult(x, y int) int {
	return x * y
}

func sub(x, y int) int {
	return x - y
}

func isExpress(b byte) bool {
	_, ok := express[b]
	return ok
}

// expression缓存，其他优化
func DiffWaysToCompute(expression string) []int {
	n := len(expression)
	result := make([]int, 0)
	// 是否是纯数字
	isNumber := true
	for i := 0; i < n; i++ {
		if !isExpress(expression[i]) {
			continue
		}
		isNumber = false
		left := DiffWaysToCompute(expression[:i])
		right := DiffWaysToCompute(expression[i+1:])
		for idxLeft := range left {
			for idxRight := range right {
				tmp := express[expression[i]](left[idxLeft], right[idxRight])
				result = append(result, tmp)
			}
		}
	}
	if isNumber {
		return []int{strToI(expression)}
	}
	return result
}

// 字符串转换成数字。“234” -> 234
func strToI(s string) int {
	result := 0
	flag := 1
	count := len(s)
	for i := count - 1; i >= 0; i-- {
		result += convert(s[i]) * flag
		flag *= 10
	}
	return result
}

// 字符转换成数字
func convert(b byte) int {
	return int(b - '0')
}

面试官问题

解题过程中全程共享桌面，面试官会时不时截图。告知面试官答完之后，给他讲了一下思路。讲完思路，他问了一个问题。

有没有可以优化的地方

我看了一下leetcode上的时间复杂的和空间复杂的提示

然后觉得空间复杂的应该可以优化一下，但是看半天不知道如何优化，后面面试官提示说：可以将DiffWaysToCompute函数的入参expression缓存起来，这样后面如果有相同的表达式就可以直接用了，不用再递归调用。

面试官说的很对，这里确实可以做个缓存，递归调用确实很容易出现重复计算

(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

看这个示例就可以发现，单个字符2,3,4,5 每个值都会计算一次，结果是5个值，就会计算5次，如果缓存起来了就只需要计算一次。

23,45,3-4等等这些表达式都重复出现了，如果缓存起来就只需要计算一次。

总结：这种递归调用的场景，大多数情况都可以做类似缓存，因为递归调用必然会出现重复计算的情况。

优化之后

var expressionCache = map[string][]int{}

// expression缓存，其他优化
func DiffWaysToCompute(expression string) []int {
	// 判断缓存中是否存在，如果存在则直接返回
	if v, ok := expressionCache[expression]; ok {
		return v
	}
	n := len(expression)
	result := make([]int, 0)
	// 是否是纯数字
	isNumber := true
	for i := 0; i < n; i++ {
		if !isExpress(expression[i]) {
			continue
		}
		isNumber = false
		left := DiffWaysToCompute(expression[:i])
		right := DiffWaysToCompute(expression[i+1:])
		for idxLeft := range left {
			for idxRight := range right {
				tmp := express[expression[i]](left[idxLeft], right[idxRight])
				result = append(result, tmp)
			}
		}
	}

	if isNumber {
		result = []int{strToI(expression)}
	}
    // 放入缓存
	expressionCache[expression] = result
	return result
}

结果