题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给定一个布尔表达式和一个期望的布尔结果 result，布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成。实现一个函数，算出有几种可使该表达式得出 result 值的括号方法。
示例 1:
- 输入: s = "1^0|0|1", result = 0
- 输出: 2
- 解释: 两种可能的括号方法是
- 1^(0|(0|1))
- 1^((0|0)|1)
示例 2:
- 输入: s = "0&0&0&1^1|0", result = 1
- 输出: 10
提示：
- 运算符的数量不超过 19 个
题目思考
- 增加括号等价于什么?
解决方案
思路
- 分析题目, 我们可以在任意位置加上有效的括号, 从而改变运算顺序
- 换个角度思考, 这也等价于我们改变了表达式中运算符的优先级, 这样总会有一个运算符是在最后才被计算的
- 所以我们可以只关注最后一次做运算的运算符, 先得到其左右部分的计算结果方法数, 然后根据当前运算符计算总方法数即可:
- 运算符是&, 则只有两侧结果同时是 1 时才会得到 1, 其余情况都是 0
- 运算符是|, 则只有两侧结果同时是 0 时才会得到 0, 其余情况都是 1
- 运算符是^, 则当两侧结果相同时会得到 0, 不同时会得到 1
- 以上就是典型的分治思想, 具体实现方面, 我们可以传入当前区间起点和终点, 然后遍历区间内的运算符, 依次递归调用子函数, 计算其左右两部分的结果, 并根据上述三种情况计算并累加到最终结果中
- 另外注意到区间的计算结果可能被使用多次, 但其结果本身不变, 所以我们可以采用记忆化搜索的思想, 将其结果缓存起来, 从而避免重复计算 (python 对应的就是 lru_cache, 也可以自定义一个字典来缓存)
- 下面的代码就对应了上面的整个过程, 并且有详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(N^3): 记忆化搜索共计算 N*N 个区间, 然后内部计算过程中会遍历当前区间的所有运算符 (N), 所以总时间是 N*N*N - 空间复杂度
O(N^2): 额外存储每个区间的计算结果, 区间个数是 N*N
代码
class Solution:
def countEval(self, s: str, result: int) -> int:
# 记忆化搜索+递归分治+传入区间
# count(b,e)返回当前区间[b,e]的所有计算结果为0或1的方法数
# 对于每个操作符, 分别计算其左右表达式的0和1的数目, 然后根据操作符本身得到当前操作符的对应的0和1的数目
@functools.lru_cache(None)
def count(b, e):
cnts = [0] * 2
if b >= e:
# 递归出口, 只有一个数字或没有数字
if b == e:
# 有一个数字时, 要将其对应的方法数加1
cnts[int(s[b])] += 1
return cnts
for i in range(b + 1, e, 2):
# 注意从b+1开始遍历, 且间距为2, 这样能保证遍历所有符号 (b和e都是数字)
# 当前字符不是数字, 可以将它作为最后一个运算符, 计算出左右两侧的0和1的个数后再最终计算
# lc0是左侧部分计算结果是0的方法数, lc1是计算结果是1的方法数
lc0, lc1 = count(b, i - 1)
# rc0和rc1同上, 对应右侧部分计算结果是0或1的方法数
rc0, rc1 = count(i + 1, e)
if s[i] == "&":
# 最后运算符是&, 则只有两侧结果同时是1时才会得到1, 其余情况都是0
# 将左右部分对应结果的方法数相乘, 并累加到最终结果中
cnts[0] += lc0 * rc0 + lc0 * rc1 + lc1 * rc0
cnts[1] += lc1 * rc1
elif s[i] == "|":
# 最后运算符是|, 则只有两侧结果同时是0时才会得到0, 其余情况都是1
cnts[0] += lc0 * rc0
cnts[1] += lc1 * rc1 + lc0 * rc1 + lc1 * rc0
elif s[i] == "^":
# 最后运算符是^, 则当两侧结果相同时会得到0, 不同时会得到1
cnts[0] += lc0 * rc0 + lc1 * rc1
cnts[1] += lc0 * rc1 + lc1 * rc0
return cnts
return count(0, len(s) - 1)[result] 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号